Vecino uniéndose

Método de agrupación ascendente para crear árboles filogenéticos

En bioinformática , la unión de vecinos es un método de agrupación ascendente (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 (p. ej., especies o secuencias) para crear el árbol filogenético. ^[2]

el algoritmo

Comenzando con un árbol en estrella (A), se calcula la matriz Q y se usa para elegir un par de nodos para unir, en este caso f y g. Estos se unen a un nodo recién creado, u, como se muestra en (B). La parte del árbol que se muestra como líneas continuas ahora está fija y no se cambiará en los pasos de unión posteriores. Las distancias desde el nodo u hasta los nodos ae se calculan a partir de la ecuación ( 3 ). Luego, este proceso se repite, utilizando una matriz de solo las distancias entre los nodos, a,b,c,d,e y u, y una matriz Q derivada de ella. En este caso, u y e se unen a la v recién creada, como se muestra en (C). Dos iteraciones más conducen primero a (D) y luego a (E), momento en el que el algoritmo finaliza, ya que el árbol está completamente resuelto.

La unión de vecinos toma como entrada una matriz de distancia , 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 está completamente resuelto y se conocen todas las longitudes de las ramas:

1. Con base en la matriz de distancia actual, calcule una matriz (definida a continuación). ${\displaystyle 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. Calcule la distancia desde cada uno de los taxones del par hasta este nuevo nodo.
4. Calcule 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 usando las distancias calculadas en el paso anterior.

La matriz Q

Con base en una matriz de distancias que relaciona los taxones, calcule la matriz x de la siguiente manera: ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle Q}$

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

Distancia desde los miembros del par hasta el nuevo nodo

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

y:

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

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

Distancia de los otros taxones desde el nuevo nodo

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

donde está el nuevo nodo, es el nodo al que queremos calcular la distancia y son los miembros del par que se acaba de unir. ${\displaystyle u}$ ${\displaystyle k}$ ${\displaystyle f}$ ${\displaystyle g}$

Complejidad

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

Ejemplo

Vecino que se une con 5 taxones. En este caso, dos pasos vecinos que se unen dan un árbol con una topología completamente resuelta. Las ramas del árbol resultante están etiquetadas con sus longitudes.

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

Primer paso

Primera incorporación

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 elementos y . ${\displaystyle Q_{1}(a,b)=-50}$ ${\displaystyle Q_{1}}$ ${\displaystyle a}$ ${\displaystyle b}$

Estimación de la longitud de la primera rama.

Denotemos el nuevo nodo. Por la ecuación ( 2 ), anterior, las ramas que se unen y luego tienen longitudes: ${\displaystyle u}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle u}$

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

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

Primera actualización de la matriz de distancias

Luego procedemos a actualizar la matriz de distancia inicial en una nueva matriz de distancia (ver más abajo), reducida en tamaño en una fila y una columna debido a la unión de with con su vecino . Usando la ecuación ( 3 ) anterior, calculamos la distancia desde cada uno de los otros nodos además de y . En este caso obtenemos: ${\displaystyle D}$ ${\displaystyle D_{1}}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle u}$ ${\displaystyle u}$ ${\displaystyle a}$ ${\displaystyle 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 distancias resultante es: ${\displaystyle 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 que no participan en la primera unión de taxones. ${\displaystyle D_{1}}$

Segundo paso

Segunda incorporación

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

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

Estimación de la longitud de la segunda rama.

Las longitudes de las ramas que se unen y se pueden calcular: ${\displaystyle u}$ ${\displaystyle c}$ ${\displaystyle v}$

${\displaystyle \delta (u,v)={\frac {1}{2}}d(u,c)+{\frac {1}{2(4-2)}}\left[\sum _{k=1}^{4}d(u,k)-\sum _{k=1}^{4}d(c,k)\right]\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 las ramas ayudan a dibujar el árbol de unión vecino como se muestra en la figura.

Segunda actualización de la matriz de distancias

Ahora se calcula la matriz de distancia actualizada para los 3 nodos restantes, , y : ${\displaystyle D_{2}}$ ${\displaystyle v}$ ${\displaystyle d}$ ${\displaystyle 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}$

Último paso

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, unámonos y llamemos al último nodo . Se pueden calcular las longitudes de las tres ramas restantes: ${\displaystyle v}$ ${\displaystyle d}$ ${\displaystyle 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 ya está completo, como se muestra en la figura.

Conclusión: distancias aditivas

Este ejemplo representa un caso ideal: observe que si nos movemos de cualquier taxón a cualquier otro a lo largo de las ramas del árbol y sumamos las longitudes de las ramas atravesadas, el resultado es igual a la distancia entre esos taxones en la matriz de distancias de entrada. Por ejemplo, pasando 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 poco común en la práctica. No obstante, es importante señalar que, dada una matriz de distancia aditiva como entrada, se garantiza que la unión de vecinos encontrará el árbol cuyas distancias entre taxones concuerden con ella. ${\displaystyle d}$ ${\displaystyle b}$ ${\displaystyle 2+2+3+3=10}$

Incorporación de vecinos como mínima evolución

La unión de vecinos puede verse como una heurística codiciosa 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, y los pesos dependen de la topología. La topología óptima de BME es la que minimiza la longitud de este árbol. NJ en cada paso se une con avidez al par de taxones que darán la mayor disminución en la longitud estimada del árbol. Este procedimiento no garantiza encontrar el óptimo para el criterio BME, aunque a menudo lo hace y suele estar bastante cerca. ^[5]

Ventajas y desventajas

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 arranque , 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 distancias de entrada es correcta, el árbol de salida será correcto. Además, la exactitud de la topología del árbol de salida está garantizada siempre que la matriz de distancias sea "casi aditiva", específicamente si cada entrada en la matriz de distancias difiere de la distancia real en menos de la mitad de la longitud de la rama más corta del á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 exactitud de la unión de vecinos para matrices de distancias casi aditivas implica que es estadísticamente consistente en 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 supone que todos los linajes evolucionen 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 necesaria ]} La unión de vecinos tiene la característica indeseable de que a menudo asigna longitudes negativas a algunas de las ramas.

Implementaciones y variantes

Hay muchos programas disponibles que implementan la unión de vecinos. Entre las implementaciones de NJ canónico (es decir, que utilizan los criterios de optimización clásicos de NJ, 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 aproximadamente al cuadrado del número de taxones.

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

• BIONJ (1997) ^[11] y Weighbor (2000), ^[12] mejoran la precisión haciendo uso del hecho de que las distancias más cortas en la matriz de distancias son generalmente mejor conocidas que las distancias más largas. Los dos métodos se han ampliado para ejecutarse 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 escalada y conserva la complejidad del peor de los casos de O(n^3). Rapid NJ es más rápido que NJ simplemente relajado. ^[14]
• FastME es una implementación del método de evolución mínima equilibrada (BME) estrechamente relacionado (consulte § Unión de vecinos como evolución mínima). Es tan rápido y más preciso que NJ. 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 aproximadamente NJ, lo reorganiza en BME y luego lo reorganiza en un árbol de máxima verosimilitud aproximado. ^[dieciséis]

Ver también

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

Referencias

1. Saitou, N.; Nei, M. (1 de julio de 1987). "El método de unión de vecinos: un nuevo método para reconstruir árboles filogenéticos". Biología Molecular y Evolución . 4 (4): 406–425. doi : 10.1093/oxfordjournals.molbev.a040454 . PMID  3447015.
2. Xavier Didelot (2010). "Análisis basado en secuencias de estructuras de poblaciones bacterianas". En D. Ashley Robinson; Daniel Falush; Edward J. Feil (eds.). Genética de poblaciones bacterianas en enfermedades infecciosas . John Wiley e hijos. págs. 46–47. ISBN 978-0-470-42474-2.
3. Estudiante, JA; Keppler, KJ (noviembre de 1988). "Una nota sobre el algoritmo de unión de vecinos de Saitou y Nei". Biología Molecular y Evolución . 5 (6): 729–31. doi : 10.1093/oxfordjournals.molbev.a040527 . ISSN  1537-1719. PMID  3221794.
4. Mailund, Thomas; Brodal, GerthS; Fagerberg, Rolf; Pedersen, ChristianNS; Phillips, Derek (2006). "Reelaboración del método de unión de vecinos". Bioinformática BMC . 7 (1): 29. doi : 10.1186/1471-2105-7-29 . PMC 3271233 . PMID  16423304. 
5. Gascuel O, Acero M (2006). "Se revela la unión de vecinos". Mol Biol Evol . 23 (11): 1997–2000. doi : 10.1093/molbev/msl072 . PMID  16877499.
6. Kuhner, MK; Felsenstein, J. (1 de mayo de 1994). "Una comparación de simulación de algoritmos de filogenia en tasas evolutivas iguales y desiguales". Biología Molecular y Evolución . 11 (3): 459–468. doi : 10.1093/oxfordjournals.molbev.a040126 . ISSN  0737-4038. PMID  8015439.
7. Atteson K (1997). "El rendimiento de los algoritmos de reconstrucción de filogenia de unión de vecinos", págs. En Jiang, T. y Lee, D., eds., Lecture Notes in Computer Science, 1276 , Springer-Verlag, Berlín. CAPULLO '97.
8. Mihaescu R, Levy D, Pachter L (2009). "Por qué funciona la unión de vecinos". Algorítmica . 54 (1): 1–24. arXiv : cs/0602041 . doi :10.1007/s00453-007-9116-4. S2CID  2462145.{{cite journal}}: CS1 maint: multiple names: authors list (link)
9. "RapidNueva Jersey". birc.au.dk.​
10. "NINJA: una herramienta para la inferencia de filogenia de unión de vecinos a gran escala - Inicio". wheelerlab.org .
11. "ATGC: BioNJ". www.atgc-montpellier.fr .
12. "Página de inicio de PESAJE". 5 de marzo de 2015. Archivado desde el original el 5 de marzo de 2015.
13. Criscuolo, Alexis; Gascuel, Olivier (diciembre de 2008). "Algoritmos rápidos similares a NJ para tratar matrices de distancias incompletas". Bioinformática BMC . 9 (1): 166. doi : 10.1186/1471-2105-9-166 . PMC 2335114 . PMID  18366787. 
14. Simonsen, Martín; Mailund, Thomas; Pedersen, Christian NS (2008). Unión rápida de vecinos (PDF) . Apuntes de conferencias sobre informática. vol. 5251, págs. 113-122. doi :10.1007/978-3-540-87361-7_10. ISBN 978-3-540-87360-0. {{cite book}}: |journal=ignorado ( ayuda )
15. "ATGC: FastME". www.atgc-montpellier.fr .
16. "FastTree 2.1: árboles de probabilidad aproximadamente máxima para alineaciones grandes". www.microbesonline.org .

Otras fuentes

• Studier JA, Keppler KJ (1988). "Una nota sobre el algoritmo de unión de vecinos de Saitou y Nei". Mol Biol Evol . 5 (6): 729–731. doi : 10.1093/oxfordjournals.molbev.a040527 . PMID  3221794.
• Martín Simonsen; Thomas Mailund; Christian NS Pedersen (2008). "Unión rápida de vecinos". Algoritmos en Bioinformática . Apuntes de conferencias sobre informática. vol. 5251, págs. 113-122. CiteSeerX  10.1.1.218.2078 . doi :10.1007/978-3-540-87361-7_10. ISBN 978-3-540-87360-0.

enlaces externos

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