Vecino uniéndose

En bioinformática , la unión de vecinos es un método de agrupamiento de abajo hacia arriba (aglomerativo) para la creación de árboles filogenéticos , creado por Naruya Saitou y Masatoshi Nei en 1987. ^[1] Generalmente basado en datos de secuencias de ADN o proteínas , el algoritmo requiere conocimiento de la distancia entre cada par de taxones (por ejemplo, especies o secuencias) para crear el árbol filogenético. ^[2]

La unión de vecinos toma como entrada una matriz de distancias , que especifica 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 repite los siguientes pasos hasta que el árbol se resuelve por completo y se conocen todas las longitudes de las ramas:

1. Basándose en la matriz de distancia actual, calcule una matriz (definida a continuación).${\estilo de visualización Q}$
2. Encuentre el par de taxones distintos i y j (es decir, con ) para el cual es más pequeño. Haga un nuevo nodo que una los taxones i y j, y conecte el nuevo nodo al nodo central. Por ejemplo, en la parte (B) de la figura de la derecha, se crea el nodo u para unir f y g.${\displaystyle i\neq j}$${\displaystyle Q(i,j)}$
3. Calcula la distancia desde cada uno de los taxones del par hasta este nuevo nodo.
4. Calcula la distancia desde cada uno de los taxones fuera de este par hasta el nuevo nodo.
5. Inicie el algoritmo nuevamente, reemplazando el par de vecinos unidos con el nuevo nodo y utilizando las distancias calculadas en el paso anterior.

A partir de una matriz de distancias que relaciona los taxones, calcule la matriz x de la siguiente manera:${\estilo de visualización n}$${\estilo de visualización n}$${\estilo de visualización n}$${\estilo de visualización Q}$

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

( 1 )

¿Dónde está la distancia entre taxones y ?${\displaystyle d(i,j)}$${\estilo de visualización i}$${\estilo de visualización j}$

Para cada uno de los taxones del par que se va a unir, utilice la siguiente fórmula para calcular la distancia al nuevo nodo:

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

( 2 )

y:

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

Los taxones y son los taxones emparejados y es el nodo recién creado. Las ramas que unen y y y , y sus longitudes, y son parte del árbol que se está creando gradualmente; no afectan ni son afectadas por los pasos posteriores de unión de vecinos.${\estilo de visualización f}$${\estilo de visualización g}$${\estilo de visualización u}$${\estilo de visualización f}$${\estilo de visualización u}$${\estilo de visualización g}$${\estilo de visualización u}$${\displaystyle \delta(f,u)}$${\displaystyle \delta(g,u)}$

Para cada taxón no considerado en el paso anterior, calculamos la distancia al nuevo nodo de la siguiente manera:

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

( 3 )

donde está el nuevo nodo, es el nodo al que queremos calcular la distancia y y son los miembros del par recién unido.${\estilo de visualización u}$${\estilo de visualización k}$${\estilo de visualización f}$${\estilo de visualización g}$

La unión de vecinos en un conjunto de taxones requiere iteraciones. En cada paso, se debe construir y buscar una matriz. Inicialmente, la matriz tiene un tamaño de , luego, en el siguiente paso, es de , etc. Implementar esto de manera sencilla conduce a un algoritmo con una complejidad temporal de ; ^[3] existen implementaciones que usan heurísticas para hacerlo mucho mejor que esto en promedio. ^[4]${\estilo de visualización n}$${\estilo de visualización n-3}$${\estilo de visualización Q}$${\estilo de visualización Q}$${\displaystyle n\veces n}$${\displaystyle (n-1)\times (n-1)}$${\displaystyle O(n^{3})}$

Supongamos que tenemos cinco taxones y la siguiente matriz de distancias :${\estilo de visualización (a,b,c,d,e)}$${\estilo de visualización D}$

Calculamos los valores mediante la ecuación ( 1 ). Por ejemplo:${\displaystyle Q_{1}}$

${\displaystyle Q_{1}(a,b)=(n-2)d(a,b)-\sum _{k=1}^{5}d(a,k)-\sum _{k=1}^{5}d(b,k)}$

${\displaystyle =(5-2)\times 5-(5+9+9+8)-(5+10+10+9)=15-31-34=-50}$

Obtenemos los siguientes valores para la matriz (los elementos diagonales de la matriz no se utilizan y se omiten aquí):${\displaystyle Q_{1}}$

En el ejemplo anterior, . Este es el valor más pequeño de , por lo que unimos los elementos y .${\displaystyle Q_{1}(a,b)=-50}$${\displaystyle Q_{1}}$${\estilo de visualización a}$${\estilo de visualización b}$

Sea el nuevo nodo el que se indica. Por la ecuación ( 2 ), anterior, las ramas que se unen a y tienen entonces longitudes:${\estilo de visualización u}$${\estilo de visualización a}$${\estilo de visualización b}$${\estilo de visualización u}$

${\displaystyle \delta(a,u)={\frac {1}{2}}d(a,b)+{\frac {1}{2(5-2)}}[\sum _{k=1}^{5}d(a,k)-\sum _{k=1}^{5}d(b,k)]\quad ={\frac {5}{2}}+{\frac {31-34}{6}}=2}$

${\displaystyle \delta(b,u)=d(a,b)-\delta(a,u)\quad =5-2=3}$

Luego procedemos a actualizar la matriz de distancia inicial en una nueva matriz de distancia (ver abajo), reducida en tamaño en una fila y una columna debido a la unión de con en su vecino . Usando la ecuación ( 3 ) anterior, calculamos la distancia desde a cada uno de los otros nodos además de y . En este caso, obtenemos:${\estilo de visualización D}$$Estilo de visualización D_{1}$${\estilo de visualización a}$${\estilo de visualización b}$${\estilo de visualización u}$${\estilo de visualización u}$${\estilo de visualización a}$${\estilo de visualización b}$

${\displaystyle d(u,c)={\frac {1}{2}}[d(a,c)+d(b,c)-d(a,b)]={\frac {9+10-5}{2}}=7}$

${\displaystyle d(u,d)={\frac {1}{2}}[d(a,d)+d(b,d)-d(a,b)]={\frac {9+10-5}{2}}=7}$

${\displaystyle d(u,e)={\frac {1}{2}}[d(a,e)+d(b,e)-d(a,b)]={\frac {8+9 -5}{2}}=6}$

La matriz de distancia resultante es:$Estilo de visualización D_{1}$

Los valores en negrita corresponden a las distancias recién calculadas, mientras que los valores en cursiva no se ven afectados por la actualización de la matriz, ya que corresponden a distancias entre elementos no involucrados en la primera unión de taxones.$Estilo de visualización D_{1}$

La matriz correspondiente es:${\displaystyle Q_{2}}$

Podemos elegir unir y , o unir y ; ambos pares tienen el valor mínimo de , y cualquiera de las dos opciones conduce al mismo resultado. Para ser más concretos, unamos y y llamemos al nuevo nodo .${\estilo de visualización u}$${\estilo de visualización c}$${\estilo de visualización d}$${\estilo de visualización e}$${\displaystyle Q_{2}}$${\estilo de visualización -28}$${\estilo de visualización u}$${\estilo de visualización c}$${\estilo de visualización v}$

Las longitudes de las ramas que unen a y se pueden calcular:${\estilo de visualización u}$${\estilo de visualización c}$${\estilo de visualización v}$

${\displaystyle \delta (u,v)={\frac {1}{2}}d(u,c)+{\frac {1}{2(4-2)}}[\sum _{k=1}^{4}d(u,k)-\sum _{k=1}^{4}d(c,k)]\quad ={\frac {7}{2}}+{\frac {20-22}{4}}=3}$

${\displaystyle \delta(c,v)=d(u,c)-\delta(u,v)\quad =7-3=4}$

La unión de los elementos y el cálculo de la longitud de la rama ayudan a dibujar el árbol de unión de vecinos como se muestra en la figura.

Ahora se calcula la matriz de distancia actualizada para los 3 nodos restantes, , , y :$Estilo de visualización D_{2}$${\estilo de visualización v}$${\estilo de visualización d}$${\estilo de visualización e}$

${\displaystyle d(v,d)={\frac {1}{2}}[d(u,d)+d(c,d)-d(u,c)]={\frac {7+8-7}{2}}=4}$

${\displaystyle d(v,e)={\frac {1}{2}}[d(u,e)+d(c,e)-d(u,c)]={\frac {6+7 -7}{2}}=3}$

La topología del árbol está completamente resuelta en este punto. Sin embargo, para mayor claridad, podemos calcular la matriz. Por ejemplo:${\displaystyle Q_{3}}$

${\displaystyle Q_{3}(v,e)=(3-2)d(v,e)-\sum _{k=1}^{3}d(v,k)-\sum _{k= 1}^{3}d(e,k)=3-7-6=-10}$

Para ser más concretos, uniremos y y llamaremos al último nodo . Las longitudes de las tres ramas restantes se pueden calcular:${\estilo de visualización v}$${\estilo de visualización d}$${\estilo de visualización w}$

${\displaystyle \delta (v,w)={\frac {1}{2}}d(v,d)+{\frac {1}{2(3-2)}}\left[\sum _{k=1}^{3}d(v,k)-\sum _{k=1}^{3}d(d,k)\right]\quad ={\frac {4}{2}}+{\frac {7-7}{2}}=2}$

${\displaystyle \delta (w,d)=d(v,d)-\delta (v,w)=4-2=2}$

${\displaystyle \delta (w,e)=d(v,e)-\delta (v,w)=3-2=1}$

El árbol de unión de vecinos ahora está completo, como se muestra en la figura.

Este ejemplo representa un caso idealizado: nótese que si nos movemos de un taxón a otro a lo largo de las ramas del árbol, y sumamos las longitudes de las ramas recorridas, el resultado es igual a la distancia entre esos taxones en la matriz de distancias de entrada. Por ejemplo, al pasar de a tenemos . Una matriz de distancias cuyas distancias concuerdan de esta manera con algún árbol se dice que es "aditiva", una propiedad que es rara en la práctica. No obstante, es importante notar que, dada una matriz de distancias aditiva como entrada, la unión vecinal garantiza encontrar el árbol cuyas distancias entre taxones concuerdan con ella.${\displaystyle d}$${\displaystyle b}$${\displaystyle 2+2+3+3=10}$

La unión de vecinos puede considerarse una heurística voraz para el criterio de evolución mínima equilibrada ^[5] (BME). Para cada topología, BME define la longitud del árbol (suma de las longitudes de las ramas) como una suma ponderada particular de las distancias en la matriz de distancias, con pesos que dependen de la topología. La topología óptima de BME es la que minimiza esta longitud del árbol. NJ en cada paso une vorazmente ese par de taxones que dará la mayor disminución en la longitud estimada del árbol. Este procedimiento no garantiza encontrar el óptimo para el criterio de BME, aunque a menudo lo hace y suele ser bastante cercano. ^[5]

La principal virtud de NJ es que es rápido ^{[6] : 466} en comparación con los métodos de mínimos cuadrados , máxima parsimonia y máxima verosimilitud . ^[6] Esto lo hace práctico para analizar grandes conjuntos de datos (cientos o miles de taxones) y para el bootstrap , para cuyos fines otros medios de análisis (por ejemplo, máxima parsimonia , máxima verosimilitud ) pueden ser computacionalmente prohibitivos.

La unión de vecinos tiene la propiedad de que si la matriz de distancia de entrada es correcta, entonces el árbol de salida será correcto. Además, la corrección de la topología del árbol de salida está garantizada siempre que la matriz de distancia sea "casi aditiva", específicamente si cada entrada en la matriz de distancia difiere de la distancia verdadera en menos de la mitad de la longitud de la rama más corta en el árbol. ^[7] En la práctica, la matriz de distancia rara vez satisface esta condición, pero la unión de vecinos a menudo construye la topología de árbol correcta de todos modos. ^[8] La corrección de la unión de vecinos para matrices de distancia casi aditivas implica que es estadísticamente consistente bajo muchos modelos de evolución; dados datos de longitud suficiente, la unión de vecinos reconstruirá el árbol verdadero con alta probabilidad. En comparación con UPGMA y WPGMA , la unión de vecinos tiene la ventaja de que no asume que todos los linajes evolucionan al mismo ritmo ( hipótesis del reloj molecular ).

Sin embargo, la unión de vecinos ha sido reemplazada en gran medida por métodos filogenéticos que no se basan en medidas de distancia y ofrecen una precisión superior en la mayoría de las condiciones. ^{[ cita requerida ]} La unión de vecinos tiene la característica indeseable de que a menudo asigna longitudes negativas a algunas de las ramas.

Hay muchos programas disponibles que implementan la unión de vecinos. Entre las implementaciones de NJ canónica (es decir, que utilizan los criterios de optimización de NJ clásicos, por lo que dan los mismos resultados), RapidNJ (iniciado en 2003, actualización importante en 2011, aún actualizado en 2023) ^[9] y NINJA (iniciado en 2009, última actualización en 2013) ^[10] se consideran de última generación. Tienen tiempos de ejecución típicos proporcionales a aproximadamente el cuadrado del número de taxones.

Las variantes que se desvían del canónico incluyen:

• BIONJ (1997) ^[11] y Weighbor (2000), ^[12] mejoraron la precisión aprovechando el hecho de que las distancias más cortas en la matriz de distancias generalmente se conocen mejor que las distancias más largas. Los dos métodos se han ampliado para que funcionen en matrices de distancias incompletas. ^[13]
• "Fast NJ" recuerda el mejor nodo y siempre es O(n^2); "relax NJ" realiza una búsqueda de ascenso de colina y conserva la complejidad del peor caso de O(n^3). Rapid NJ es más rápido que el simple NJ relajado. ^[14]
• FastME es una implementación del método de evolución mínima equilibrada (BME), estrechamente relacionado (véase § Unión de vecinos como evolución mínima). Es casi tan rápido como NJ y más preciso que éste. Comienza con un árbol aproximado y luego lo mejora utilizando un conjunto de movimientos topológicos como los intercambios de vecinos más cercanos (NNI). ^[15] FastTree es un método relacionado. Funciona en "perfiles" de secuencia en lugar de una matriz. Comienza con un árbol aproximado a NJ, lo reorganiza en BME y luego lo reorganiza en un árbol de máxima verosimilitud aproximado. ^[16]

• Búsqueda de vecino más cercano
• UPGMA y WPGMA
• Evolución mínima

• El método de unión de vecinos: un tutorial