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] Usualmente utilizado para árboles basados 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 formar el árbol. [2]
El algoritmo
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 , e itera sobre los siguientes pasos hasta que el árbol está completamente resuelto y se conocen todas las longitudes de las ramas:
- Basado en la matriz de distancia actual calcular la matriz (definido a continuación).
- Encuentre el par de taxones distintos i y j (es decir, con ) para cual tiene su valor más bajo. Estos taxones se unen a un nodo recién creado, que está conectado al nodo central. En la figura de la derecha, fyg se unen al nuevo nodo u.
- Calcule la distancia desde cada uno de los taxones del par hasta este nuevo nodo.
- Calcule la distancia desde cada uno de los taxones fuera de este par al nuevo nodo.
- 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
Basado en una matriz de distancias que relaciona el taxones, calcular como sigue:
( 1 )
dónde es la distancia entre taxones y .
Distancia de los miembros de la pareja al nuevo nodo
Para cada uno de los taxones del par que se está uniendo, use la siguiente fórmula para calcular la distancia al nuevo nodo:
( 2 )
y:
Taxa y son los taxones emparejados y es el nodo recién creado. Las ramas que se unen y y y , y sus longitudes, y son parte del árbol que se está creando gradualmente; no afectan ni se ven afectados por los pasos posteriores de unión de vecinos.
Distancia de los otros taxones del nuevo nodo
Para cada taxón no considerado en el paso anterior, calculamos la distancia al nuevo nodo de la siguiente manera:
( 3 )
dónde es el nuevo nodo, es el nodo al que queremos calcular la distancia y y son los miembros de la pareja que se acaban de unir.
Complejidad
Vecino que se une a un conjunto de taxa requiere iteraciones. En cada paso uno tiene que construir y buscar unmatriz. Inicialmente el la matriz es el tamaño , entonces el siguiente paso es , etc. Implementar esto de una manera sencilla conduce a un algoritmo con una complejidad de tiempo de ; [3] existen implementaciones que usan heurística para hacer mucho mejor que esto en promedio. [4]
Ejemplo
Supongamos que tenemos cinco taxones y la siguiente matriz de distancias :
a | B | C | D | mi | |
---|---|---|---|---|---|
a | 0 | 5 | 9 | 9 | 8 |
B | 5 | 0 | 10 | 10 | 9 |
C | 9 | 10 | 0 | 8 | 7 |
D | 9 | 10 | 8 | 0 | 3 |
mi | 8 | 9 | 7 | 3 | 0 |
Primer paso
Primera unión
Calculamos el valores por ecuación ( 1 ). Por ejemplo:
Obtenemos los siguientes valores para el matriz (los elementos diagonales de la matriz no se utilizan y se omiten aquí):
a | B | C | D | mi | |
---|---|---|---|---|---|
a | −50 | −38 | −34 | −34 | |
B | −50 | −38 | −34 | −34 | |
C | −38 | −38 | −40 | −40 | |
D | −34 | −34 | −40 | −48 | |
mi | −34 | −34 | −40 | −48 |
En el ejemplo anterior, . Este es el valor más pequeño de, entonces unimos elementos y .
Estimación de la longitud de la primera rama
Dejar denotar el nuevo nodo. Por la ecuación ( 2 ), arriba, las ramas que unen y a luego tener longitudes:
Actualización de la primera matriz de distancias
Luego procedemos a actualizar la matriz de distancias inicial en una nueva matriz de distancia (ver más abajo), reducido 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 y . En este caso obtenemos:
La matriz de distancia resultante es:
tu | C | D | mi | |
---|---|---|---|---|
tu | 0 | 7 | 7 | 6 |
C | 7 | 0 | 8 | 7 |
D | 7 | 8 | 0 | 3 |
mi | 6 | 7 | 3 | 0 |
Valores audaces en 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.
Segundo paso
Segunda unión
El correspondiente matriz es:
tu | C | D | mi | |
---|---|---|---|---|
tu | −28 | −24 | −24 | |
C | −28 | −24 | −24 | |
D | −24 | −24 | −28 | |
mi | −24 | −24 | −28 |
Podemos elegir unirnos y , o para unirse y ; ambos pares tienen el mínimo valor de , y cualquiera de las dos opciones conduce al mismo resultado. Para concreción, unámonos y y llama al nuevo nodo .
Estimación de la longitud de la segunda rama
Las longitudes de las ramas que se unen y a se puede calcular:
La unión de los elementos y el cálculo de la longitud de la rama ayudan a dibujar el árbol de unión vecino como se muestra en la figura .
Actualización de la segunda matriz de distancia
La matriz de distancia actualizada para los 3 nodos restantes, , , y , ahora se calcula:
v | D | mi | |
---|---|---|---|
v | 0 | 4 | 3 |
D | 4 | 0 | 3 |
mi | 3 | 3 | 0 |
Último paso
La topología del árbol está completamente resuelta en este punto. Sin embargo, para mayor claridad, podemos calcular elmatriz. Por ejemplo:
v | D | mi | |
---|---|---|---|
v | −10 | −10 | |
D | −10 | −10 | |
mi | −10 | −10 |
Para concreción, unámonos y y llama al último nodo . Se pueden calcular las longitudes de las tres ramas restantes:
El árbol de unión vecino ahora está completo, como se muestra en la figura .
Conclusión: distancias aditivas
Este ejemplo representa un caso idealizado: observe 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 atravesadas, el resultado es igual a la distancia entre esos taxones en la matriz de distancia 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 rara en la práctica. No obstante, es importante señalar que, dada una matriz de distancias aditiva como entrada, la unión de vecinos está garantizada para encontrar el árbol cuyas distancias entre taxones concuerden con ella.
Unión de vecinos como evolución mínima
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, con los pesos dependiendo de la topología. La topología óptima de BME es la que minimiza esta longitud de árbol. El vecino que se une en cada paso se une con avidez a ese 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 de BME, aunque a menudo lo hace y suele estar bastante cerca.
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 hace que sea práctico para analizar grandes conjuntos de datos (cientos o miles de taxones) y para el bootstrapping , para los cuales otros medios de análisis (por ejemplo, máxima parsimonia , máxima probabilidad ) 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 distancias 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 suficiente longitud, 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.
Implementaciones y variantes
Hay muchos programas disponibles que implementan la unión de vecinos. RapidNJ y NINJA son implementaciones rápidas con tiempos de ejecución típicos proporcionales a aproximadamente el cuadrado del número de taxones. BIONJ y Weighbor son variantes de uniones vecinas que mejoran su precisión al hacer uso del hecho de que las distancias más cortas en la matriz de distancias son generalmente más conocidas que las distancias más largas. FastME es una implementación del método de evolución mínima equilibrada estrechamente relacionado.
Ver también
- Búsqueda de vecino más cercano
- UPGMA y WPGMA
- Evolución mínima
Referencias
- ^ 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 .
- ^ Xavier Didelot (2010). "Análisis basado en secuencia de estructuras de población bacteriana" . 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.
- ^ Studier, 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 .
- ^ Mailund, Thomas; Brodal, GerthS; Fagerberg, Rolf; Pedersen, ChristianNS; Phillips, Derek (2006). "Reestructuración del método de unión de vecinos" . BMC Bioinformática . 7 (1): 29. doi : 10.1186 / 1471-2105-7-29 . PMC 3271233 . PMID 16423304 .
- ^ Gascuel O, Steel M (2006). "Vecino-unión revelada" . Mol Biol Evol . 23 (11): 1997–2000. doi : 10.1093 / molbev / msl072 . PMID 16877499 .
- ^ a b Kuhner, MK; Felsenstein, J. (1 de mayo de 1994). "Una comparación de simulación de algoritmos de filogenia bajo 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 .
- ^ Atteson K (1997). "El rendimiento de los algoritmos de unión de vecinos de la reconstrucción de la filogenia", págs. 101-110. En Jiang, T. y Lee, D., eds., Lecture Notes in Computer Science, 1276 , Springer-Verlag, Berlín. COCOON '97.
- ^ Mihaescu R, Levy D, Pachter L (2009). "Por qué funciona la unión de vecinos". Algoritmica . 54 (1): 1–24. arXiv : cs / 0602041 . doi : 10.1007 / s00453-007-9116-4 . S2CID 2462145 .CS1 maint: varios nombres: lista de autores ( enlace )
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 .
- Martin Simonsen; Thomas Mailund; Christian NS Pedersen (2008). Unión rápida de vecinos (PDF) . Actas de WABI . Apuntes de conferencias en Ciencias de la Computación. 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.[ enlace muerto permanente ]
enlaces externos
- El método de unión de vecinos : un tutorial