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.
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 con el taxón
d ( i , j )
es cualquier otro nodo no
Para cada vecino del par que acaba de unirse, utilice la siguiente fórmula para calcular la distancia al nodo nuevo.
son los taxones emparejado y
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
es el nodo para el que se desea calcular la distancia y
son los miembros del par acaba de unirse.
En cada paso hay que construir y buscar una matriz
, de manera que el siguiente paso es
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.
serían, respectivamente, 6 y 1, por la fórmula anterior.
Se procede a la actualización de la matriz de distancias, calculando
de acuerdo con la fórmula anterior para cada nodo
En este caso se obtiene
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.