Métrica de Robinson-Foulds

La métrica de diferencia simétrica o de Robinson-Foulds , a menudo abreviada como distancia 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 primero (aunque algunas implementaciones de software dividen la métrica RF por 2 ^[2] y otras escalan la distancia RF para tener un valor máximo de 1). Las particiones se calculan para cada árbol eliminando cada rama. Por lo tanto, el número de particiones elegibles para cada árbol es igual al número de ramas en ese árbol.

Las distancias RF han sido criticadas por estar 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 2700 veces en 2023 según Google Scholar ). Sin embargo, los sesgos inherentes a las distancias RF sugieren que los investigadores deberían considerar el uso de métricas de Robinson-Foulds "generalizadas" ^[4] que pueden tener un mejor desempeño 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ían estar vacíos, pero solo los nodos con grado mayor o igual a tres pueden etiquetarse con un conjunto vacío), la métrica de Robinson-Foulds encuentra el número de operaciones y para convertir uno en el otro. El número de operaciones define su distancia. Los árboles con raíz se pueden examinar adjuntando una hoja ficticia al nodo raíz. ^[5] ${\displaystyle \alpha }$ ${\displaystyle \alpha ^{-1}}$

Los autores definen que dos árboles son 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 una arista (combinando los nodos, creando una unión de sus conjuntos). Por el contrario, expande una arista (descontracción), donde el conjunto se puede dividir de cualquier manera. ${\displaystyle \alpha }$ ${\displaystyle \alpha ^{-1}}$

La función elimina todas las aristas de que no están en , creando , y luego se utiliza para agregar las aristas descubiertas únicamente en al árbol para construir . La cantidad de operaciones en cada uno de estos procedimientos es equivalente a la cantidad de aristas en que no están en más la cantidad de aristas en que no están en . La suma de las operaciones es equivalente a una transformación de a , o viceversa. ${\displaystyle \alpha }$ ${\displaystyle T_{1}}$ ${\displaystyle T_{2}}$ ${\displaystyle T_{1}\wedge T_{2}}$ ${\displaystyle \alpha ^{-1}}$ ${\displaystyle T_{2}}$ ${\displaystyle T_{1}\wedge T_{2}}$ ${\displaystyle T_{2}}$ ${\displaystyle T_{1}}$ ${\displaystyle T_{2}}$ ${\displaystyle T_{2}}$ ${\displaystyle T_{1}}$ ${\displaystyle T_{1}}$ ${\displaystyle T_{2}}$

Propiedades

La distancia RF corresponde a una métrica de similitud equivalente que refleja la resolución del consenso estricto de dos árboles, utilizada por primera vez para comparar árboles en 1980. ^[6]

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 presentó un algoritmo basado en un hash perfecto que calcula esta distancia y que tiene una complejidad lineal únicamente 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 aproxima la distancia de Robinson-Foulds con un error acotado en tiempo sublineal.

Aplicaciones específicas

En filogenética , la métrica se utiliza a menudo para calcular la distancia entre dos árboles. El programa treedist de la suite PHYLIP ofrece esta función, al igual que el paquete RAxML_standard, la biblioteca Python DendroPy (con el nombre de "métrica de diferencia simétrica") y los paquetes R TreeDist (función `RobinsonFoulds()`) y phangorn (función `treedist()`). 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 RF sigue utilizándose ampliamente 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 RF y la razón de su uso continuo en filogenética. 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 RF para que oscilen entre cero y uno.

Sin embargo, la métrica RF también adolece de una serie de deficiencias teóricas y prácticas: ^{[7] [5]}

• 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. ^{[7] [5]}
• Se satura rápidamente; a árboles muy similares se les puede asignar el valor máximo de distancia. ^[7]
• Su valor puede ser contraintuitivo. Un ejemplo es que mover una punta y su vecina a un punto particular en un árbol genera un valor de diferencia menor que si solo una de las dos puntas se moviera al mismo lugar. ^[7]
• Su rango de valores puede depender de la forma del árbol: los árboles que contienen muchas particiones desiguales alcanzarán distancias relativamente más bajas, en promedio, que los árboles con muchas particiones pares. ^[7]
• Su rendimiento es peor que el de muchas medidas alternativas en entornos prácticos, basados ​​en árboles simulados. ^[5]

Otro aspecto a tener en cuenta al utilizar distancias 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á en lo profundo del árbol y define dos subgrupos fundamentales, como mamíferos y aves). Sin embargo, este aspecto no es un problema de las distancias RF en sí, es una crítica más general a las distancias entre árboles. Independientemente del comportamiento de cualquier distancia entre árboles específica, un biólogo evolutivo en ejercicio puede considerar algunos reordenamientos entre árboles como "importantes" y otros como "triviales". Las distancias entre á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 RF generalizadas" reconocen la similitud entre divisiones similares, pero no idénticas; la distancia Robinson-Foulds original no tiene en cuenta cuán similares son dos agrupaciones; si no son idénticas, se descartan. ^[4]

Las distancias de 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). ^[5] La distancia de información de agrupamiento (implementada en el paquete R TreeDist) se recomienda como la alternativa más adecuada a la distancia de Robinson-Foulds. ^[5]

Un enfoque alternativo para calcular la distancia entre árboles es utilizar la distancia de cuarteto , en lugar de divisiones, como base para la comparación de árboles. ^[7]

Implementaciones de software

Referencias

1. Robinson, DF; Foulds, LR (febrero de 1981). "Comparación de árboles filogenéticos". Ciencias biológicas matemáticas . 53 (1–2): 131–147. doi :10.1016/0025-5564(81)90043-2.
2. Kuhner, Mary K.; Yamato, Jon (1 de marzo de 2015). "Rendimiento práctico de las 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.
3. Y. Lin, V. Rajan, BM Moret Una métrica para árboles filogenéticos basada en la correspondencia IEEE/ACM Trans. Comput. Biol. Bioinform., 9 (4) (2012), págs. 1014-1022
4. *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. págs. 156–169.
   • Bogdanowicz D., Giaro K. 2012. Distancia de división coincidente para árboles filogenéticos binarios sin raíz. IEEE/ACM Trans. Comput. Biol. Bioinforma. 9:150–160.
   • Bogdanowicz D., Giaro K. 2013. Sobre la distancia de coincidencia entre árboles filogenéticos enraizados. Int. J. Appl. Math. Comput. Sci. 23:669–684.
   • Nye TMW, Liò P., Gilks ​​WR 2006. Un nuevo algoritmo y una herramienta basada en la web para comparar dos árboles filogenéticos alternativos. Bioinformática. 22:117–119.
5. Smith, Martin R. (2020). "Métricas generalizadas de Robinson-Foulds basadas en la teoría de la información para comparar árboles filogenéticos" (PDF) . Bioinformática . 36 (20): 5007–5013. doi :10.1093/bioinformatics/btaa614. PMID  32619004.
6. 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.
7. Smith, Martin R. (2019). "Los enfoques bayesianos y de parsimonia reconstruyen árboles informativos a partir de conjuntos de datos morfológicos simulados" (PDF) . Biology Letters . 15 (2). 20180632. doi : 10.1098/rsbl.2018.0632 . PMC 6405459 . PMID  30958126. 

Lectura adicional

• M. Bourque, Arbres de Steiner et reseaux no tienen ciertas variables como variables de localización. Tesis doctoral, 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". Ciencias biológicas 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 utilizando ó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). "Computación eficiente de 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.; Holder, Mark T. (2010). "DendroPy: una biblioteca Python para computación filogenética". Bioinformática . 26 (12): 1569–1571. doi : 10.1093/bioinformatics/btq228 . PMID  20421198.