La métrica de Robinson-Foulds o diferencia simétrica , a menudo abreviada como distancia de RF , es una forma sencilla de calcular la distancia entre árboles filogenéticos . [1] Se define como ( A + B ) donde A es el número de particiones de datos implícitas en el primer árbol pero no en el segundo árbol y B es el número de particiones de datos implícitas en el segundo árbol pero no en el primer árbol. (aunque algunas implementaciones de software dividen la métrica de RF entre 2 [2]y otros escalan la distancia de RF para tener un valor máximo de 1). Las particiones se calculan para cada árbol quitando cada rama. Por lo tanto, el número de particiones elegibles para cada árbol es igual al número de ramas de ese árbol. Las distancias de RF han sido criticadas como sesgadas, [3] pero representan una medida relativamente intuitiva de las distancias entre árboles filogenéticos y, por lo tanto, siguen siendo ampliamente utilizadas (el artículo original de 1981 que describe las distancias de Robinson-Foulds [1] fue citado más de 200 veces en 2019 basado en Google Scholar ). Sin embargo, los sesgos inherentes a las distancias de RF sugieren que los investigadores deberían considerar el uso de métricas Robinson-Foulds "generalizadas" [4] que pueden tener un mejor rendimiento teórico y práctico y evitar los sesgos y los atributos engañosos de la métrica original.
Explicación
Dados dos árboles de nodos sin raíz y un conjunto de etiquetas (es decir, taxones ) para cada nodo (que podría estar vacío, pero solo los nodos con un grado mayor o igual a tres pueden etiquetarse con un conjunto vacío), la métrica Robinson-Foulds encuentra el número de y operaciones para convertir una en otra. El número de operaciones define su distancia. Los árboles enraizados se pueden examinar asignando una etiqueta al nodo de la hoja.
Los autores definen dos árboles como iguales si son isomorfos y el isomorfismo conserva el etiquetado. La construcción de la prueba se basa en una función llamada, que contrae un borde (combinando los nodos, creando una unión de sus conjuntos). En cambio, expande un borde (descontracción), donde el conjunto se puede dividir de cualquier manera.
La función elimina todos los bordes de que no estan en , creando , y entonces se usa para agregar los bordes que solo se descubren en al árbol para construir . El número de operaciones en cada uno de estos procedimientos es equivalente al número de aristas en que no estan en más el número de aristas en que no estan en . La suma de las operaciones equivale a una transformación de a , o viceversa.
Propiedades
La distancia de RF corresponde a una métrica de similitud equivalente que refleja la resolución del consenso estricto de dos árboles, que se utilizó por primera vez para comparar árboles en 1980. [5]
En su artículo de 1981 [1] Robinson y Foulds demostraron que la distancia es de hecho una métrica .
Algoritmos para calcular la métrica
En 1985, Day dio un algoritmo basado en hash perfecto que calcula esta distancia que tiene solo una complejidad lineal en el número de nodos de los árboles. Se ha demostrado que un algoritmo aleatorio que utiliza tablas hash que no son necesariamente perfectas se aproxima a la distancia de Robinson-Foulds con un error acotado en el tiempo sublineal.
Aplicaciones especificas
En filogenética , la métrica se usa a menudo para calcular una distancia entre dos árboles. El programa treedist de la suite PHYLIP ofrece esta función, al igual que el paquete RAxML_standard , la biblioteca DendroPy Python (bajo el nombre "métrica de diferencia simétrica") y los paquetes R TreeDist (función `RobinsonFoulds ()`) y phangorn (`treedist ( ) `función). Para comparar grupos de árboles, las implementaciones más rápidas incluyen HashRF y MrsRF.
La métrica de Robinson-Foulds también se ha utilizado en lingüística comparativa cuantitativa para calcular distancias entre árboles que representan cómo se relacionan las lenguas entre sí.
Fortalezas y debilidades
La métrica de RF sigue siendo ampliamente utilizada porque la idea de utilizar el número de divisiones que difieren entre un par de árboles es una forma relativamente intuitiva de evaluar las diferencias entre árboles para muchos sistemáticos. Esta es la principal fortaleza de la distancia de RF y la razón de su uso continuo en filogenia. Por supuesto, el número de divisiones que difieren entre un par de árboles depende del número de taxones en los árboles, por lo que se podría argumentar que esta unidad no es significativa. Sin embargo, es sencillo normalizar las distancias de RF para que oscilen entre cero y uno.
Sin embargo, la métrica de RF también adolece de una serie de deficiencias teóricas y prácticas: [6] [7]
- En relación con otras métricas, carece de sensibilidad y, por lo tanto, es impreciso; puede tomar dos valores distintos menos que taxones en un árbol. [6] [7]
- Se satura rápidamente; a árboles muy similares se les puede asignar el valor máximo de distancia. [6]
- Su valor puede ser contrario a la intuición. Un ejemplo es que mover una punta y su vecino a un punto particular en un árbol genera un valor de diferencia más bajo que si solo una de las dos puntas se moviera al mismo lugar. [6]
- Su rango de valores puede depender de la forma del árbol: los árboles que contienen muchas particiones desiguales tendrán distancias relativamente más bajas, en promedio, que los árboles con muchas particiones uniformes. [6]
- Funciona peor que muchas otras medidas alternativas en entornos prácticos, basadas en árboles simulados. [7]
Otro tema a considerar cuando se usan distancias de RF es que las diferencias en un clado pueden ser triviales (quizás si el clado resuelve tres especies dentro de un género de manera diferente) o pueden ser fundamentales (si el clado está profundamente en el árbol y define dos subgrupos fundamentales, tales como como mamíferos y aves). Sin embargo, este problema no es un problema con las distancias de RF per se, es una crítica más general de las distancias de los árboles. Independientemente del comportamiento de cualquier distancia de árbol específica, un biólogo evolutivo en ejercicio podría ver algunos reordenamientos de árboles como "importantes" y otros como "triviales". Las distancias de los árboles son herramientas; son más útiles en el contexto de otra información sobre los organismos en los árboles.
Estos problemas se pueden abordar utilizando métricas menos conservadoras. Las "distancias de RF generalizadas" reconocen la similitud entre divisiones similares, pero no idénticas; a la distancia original de Robinson Foulds no le importa cuán similares sean dos agrupaciones, si no son idénticas, se descartan. [4]
Las distancias Robinson-Foulds generalizadas de mejor rendimiento tienen una base en la teoría de la información y miden la distancia entre árboles en términos de la cantidad de información que las divisiones de los árboles tienen en común (medida en bits). [7] La distancia de información de agrupación en clústeres (implementada en el paquete R TreeDist ) se recomienda como la alternativa más adecuada a la distancia de Robinson-Foulds. [7]
Un enfoque alternativo para el cálculo de la distancia del árbol es utilizar la distancia Cuarteto , en lugar de las divisiones, como base para la comparación de árboles. [6]
Implementaciones de software
Idioma / Programa | Función | Notas |
---|---|---|
R | dist.dendlist(dendlist(x,y)) de dendextend | Ver [1] |
R | RobinsonFoulds(x, y) de TreeDist | Implementación más rápida que phangorn; ver [2] |
Pitón | tree_1.robinson_foulds(tree_2) desde ete3 | Ver [3] |
Referencias
- ↑ a b c Robinson, DF; Foulds, LR (febrero de 1981). "Comparación de árboles filogenéticos" . Biociencias matemáticas . 53 (1-2): 131-147. doi : 10.1016 / 0025-5564 (81) 90043-2 .
- ^ Kuhner, Mary K .; Yamato, Jon (1 de marzo de 2015). "Rendimiento práctico de métricas de comparación de árboles" . Biología sistemática . 64 (2): 205–214. doi : 10.1093 / sysbio / syu085 . ISSN 1076-836X . PMID 25378436 .
- ^ Y. Lin, V. Rajan, BM Moret Una métrica para árboles filogenéticos basada en la correspondencia IEEE / ACM Trans. Computación. Biol. Bioinform., 9 (4) (2012), págs. 1014-1022
- ^ a b * Böcker S., Canzar S., Klau GW 2013. La métrica generalizada de Robinson-Foulds. En: Darling A., Stoye J., editores. Algoritmos en Bioinformática. WABI 2013. Lecture Notes in Computer Science, vol 8126. Berlín, Heidelberg: Springer. pag. 156–169.
- Bogdanowicz D., Giaro K. 2012. Distancia de división coincidente para árboles filogenéticos binarios sin raíces. IEEE / ACM Trans. Computación. Biol. Bioinforma. 9: 150-160.
- Bogdanowicz D., Giaro K. 2013. Sobre una distancia coincidente entre árboles filogenéticos enraizados. En t. J. Appl. Matemáticas. Computación. Sci. 23: 669–684.
- Nye TMW, Liò P., Gilks WR 2006. Un algoritmo novedoso y una herramienta web para comparar dos árboles filogenéticos alternativos. Bioinformática. 22: 117-119.
- ^ Schuh, RT y Polhemus, JT (1980). "Análisis de la congruencia taxonómica entre conjuntos de datos morfológicos, ecológicos y biogeográficos para Leptopodomorpha (Hemiptera)". Biología sistemática . 29 (1): 1–26. doi : 10.1093 / sysbio / 29.1.1 . ISSN 1063-5157 .
- ^ a b c d e f Smith, Martín R. (2019). "Los enfoques bayesianos y parsimonia reconstruyen árboles informativos a partir de conjuntos de datos morfológicos simulados" (PDF) . Cartas de biología . 15 (2). 20180632. doi : 10.1098 / rsbl.2018.0632 . PMC 6405459 . PMID 30958126 .
- ^ a b c d e Smith, Martín R. (2020). "Métricas de Robinson-Foulds generalizadas teóricas de la información para comparar árboles filogenéticos". Bioinformática . 36 (20): 5007–5013. doi : 10.1093 / bioinformatics / btaa614 . PMID 32619004 .
Otras lecturas
- M. Bourque, Arbres de Steiner et reseaux no ciertos aspectos son una variable de localización. Tesis de doctorado, Universidad de Montreal, Montreal, Quebec, 1978 http://www.worldcat.org/title/arbres-de-steiner-et-reseaux-dont-certains-sommets-sont-a-localisation-variable/oclc/ 053538946
- Robinson, DR; Foulds, LR (1981). "Comparación de árboles filogenéticos". Biociencias matemáticas . 53 (1-2): 131-147. doi : 10.1016 / 0025-5564 (81) 90043-2 .
- William HE Day, "Algoritmos óptimos para comparar árboles con hojas etiquetadas", Journal of Classification , Número 1, diciembre de 1985. doi : 10.1007 / BF01908061
- Makarenkov, V y Leclerc, B. Comparación de árboles aditivos usando órdenes circulares, Journal of Computational Biology, 7,5,731-744,2000, "Mary Ann Liebert, Inc."
- Pattengale, Nicholas D .; Gottlieb, Eric J .; Moret, Bernard ME (2007). "Calcular eficientemente la métrica de Robinson-Foulds". Revista de Biología Computacional . 14 (6): 724–735. CiteSeerX 10.1.1.75.3338 . doi : 10.1089 / cmb.2007.R012 . PMID 17691890 .
- Sukumaran, J .; Titular, Mark T. (2010). "DendroPy: una biblioteca de Python para la computación filogenética" . Bioinformática . 26 (12): 1569-1571. doi : 10.1093 / bioinformatics / btq228 . PMID 20421198 .