Método de uniéndose de vecinos

En bioinformática, el método de unión de vecinos es un método de agrupación de abajo hacia arriba para la creación de árboles fenéticos (fenogramas), creado por Naruya Saitou y Masatoshi Nei en 1987.​ Por lo general, se utiliza para árboles de secuencias de ADN o de proteína, para lo cual, el algoritmo requiere del conocimiento de la distancia que existe entre cada par de taxones (por ejemplo, especies o secuencias) para formar el árbol.​

El algoritmo

El método de "Unión de vecinos" parte de una matriz de distancias, que indica la distancia entre cada par de taxones. El algoritmo comienza con un árbol completamente sin resolver, cuya topología corresponde a la de una red en estrella, y aplica los siguientes pasos hasta que el árbol está completamente resuelto y las longitudes de sus ramas se conocen:

1. Basándose en la matriz de distancias actual calcula la matriz ${\displaystyle Q}$ (definida abajo).
2. A continuación, busca el par de taxones para los que ${\displaystyle Q(i,j)}$ tiene su valor más bajo. Estos taxones se unen para formar un nuevo nodo que se une al resto del árbol. «F» y «G» se unen al árbol por el nodo nuevo «U».
3. Se calcula la distancia desde cada uno de los taxones del par a este nodo nuevo.
4. Se calcula la distancia desde cada uno de los taxones que no pertenecen a este nuevo par al nodo nuevo.
5. Se ejecuta el algoritmo otra vez, sustituyendo el par de taxones recién unidos por el nodo nuevo utilizando las distancias calculadas en el paso anterior.

La matriz Q

Basado en una matriz de distancia en relación con el taxón ${\displaystyle r}$, se calcula ${\displaystyle Q}$ como sigue:

${\displaystyle Q(i,j)=(r-2)d(i,j)-\sum _{k=1}^{r}d(i,k)-\sum _{k=1}^{r}d(j,k)}$

donde ${\displaystyle d(i,j)}$ es la distancia entre taxones ${\displaystyle i}$ y ${\displaystyle j}$, y ${\displaystyle k}$ es cualquier otro nodo no ${\displaystyle i}$ ni ${\displaystyle j}$ respectivamente.

Distancia de los miembros del par al nodo nuevo

Para cada vecino del par que acaba de unirse, utilice la siguiente fórmula para calcular la distancia al nodo nuevo. (Taxones ${\displaystyle f}$ y ${\displaystyle g}$ son los taxones emparejado y ${\displaystyle u}$ es el nodo recién generado):

${\displaystyle d(f,u)={\frac {1}{2}}d(f,g)+{\frac {1}{2(r-2)}}\left[\sum _{k=1}^{r}d(f,k)-\sum _{k=1}^{r}d(g,k)\right]\quad }$

y, por la reflexión:

${\displaystyle d(g,u)=d(f,g)-d(f,u)\quad }$

Distancia de los otros taxones al nuevo nodo

Para cada taxón no analizado en el paso anterior, se calcula la distancia hasta el nodo nuevo como sigue:

${\displaystyle d(u,k)={\frac {1}{2}}[d(f,k)+d(g,k)-d(f,g)]}$

donde ${\displaystyle u}$ es el nodo nuevo, ${\displaystyle k}$ es el nodo para el que se desea calcular la distancia y ${\displaystyle f}$ y ${\displaystyle g}$ son los miembros del par acaba de unirse.

Complejidad

El cálculo del método de Unión de vecinos para un conjunto de ${\displaystyle r}$ taxones requiere ${\displaystyle r-3}$ iteraciones. En cada paso hay que construir y buscar una matriz ${\displaystyle Q}$.

Inicialmente la matriz ${\displaystyle Q}$ tiene un tamaño ${\displaystyle r\times r}$, de manera que el siguiente paso es ${\displaystyle (r-1)\times (r-1)}$, etcétera. Esto conduce a un algoritmo con una complejidad de tiempo de ${\displaystyle O(r^{3})}$.

Ejemplo

Se supone que tenga cuatro taxones (A, B, C, D) y la matriz de distancias como sigue:

Se obtenía los siguientes valores para la matriz Q:

En el ejemplo anterior, dos pares de taxones tienen el valor más bajo de −40. Se puede seleccionar cualquiera de ellos para la segunda paso del algoritmo. Se sigue el ejemplo, en el supuesto de que unimos los taxones A y B juntos. Si ${\displaystyle u}$ indique el nodo nuevo, entonces las longitudes de las ramas de los bordes de la ${\displaystyle \{A,u\}}$ y de la ${\displaystyle \{B,u\}}$ serían, respectivamente, 6 y 1, por la fórmula anterior.

Se procede a la actualización de la matriz de distancias, calculando ${\displaystyle d(u,k)}$ de acuerdo con la fórmula anterior para cada nodo ${\displaystyle k}$. En este caso se obtiene ${\displaystyle d(u,C)=5}$ y ${\displaystyle d(u,D)=8}$. La matriz de distancias resultante es:

La topología del árbol se resuelve completamente en este punto, así que Q no necesita ser calculada ni es necesario buscar nuevos nodos. Sin embargo, estas distancias pueden ser utilizadas para obtener las longitudes restantes de las 3 ramas, como se muestra en la figura.