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.^[1]​ 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.^[2]​

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:

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

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.

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):

y, por la reflexión:

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

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.

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 imes r}$, de manera que el siguiente paso es ${displaystyle (r-1) imes (r-1)}$, etcétera. Esto conduce a un algoritmo con una complejidad de tiempo de ${displaystyle O(r^{3})}$.

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.