Robinson-Foulds-Metrik

Die Robinson-Foulds- oder symmetrische Differenzmetrik , oft abgekürzt als RF-Distanz , ist eine einfache Methode zur Berechnung der Distanz zwischen phylogenetischen Bäumen . ^{[ 1 ]}

Sie ist definiert als ( A + B ), wobei A die Anzahl der Datenpartitionen ist, die sich aus dem ersten, aber nicht aus dem zweiten Entscheidungsbaum ergeben, und B die Anzahl der Datenpartitionen, die sich aus dem zweiten, aber nicht aus dem ersten Entscheidungsbaum ergeben (obwohl einige Softwareimplementierungen die RF-Metrik durch 2 teilen ^{[ 2 ]} und andere die RF-Distanz auf einen Maximalwert von 1 skalieren). Die Partitionen werden für jeden Baum berechnet, indem jeder Zweig entfernt wird. Somit entspricht die Anzahl der möglichen Partitionen für jeden Baum der Anzahl der Zweige in diesem Baum.

Die Robinson- Foulds-Distanzen wurden aufgrund ihrer Verzerrung kritisiert ^{[ 3 ]} , stellen aber ein relativ intuitives Maß für die Distanzen zwischen phylogenetischen Bäumen dar und sind daher weiterhin weit verbreitet (die Originalveröffentlichung von 1981, die die Robinson-Foulds-Distanzen beschreibt ^{[ 1 ],} wurde laut Google Scholar bis 2023 über 2700 Mal zitiert ). Die den Robinson-Foulds-Distanzen inhärente Verzerrung legt jedoch nahe, dass Forschende die Verwendung „verallgemeinerter“ Robinson-Foulds-Metriken ^{[ 4 ]} in Betracht ziehen sollten , die möglicherweise eine bessere theoretische und praktische Leistungsfähigkeit aufweisen und die Verzerrungen und irreführenden Eigenschaften der ursprünglichen Metrik vermeiden.

Erläuterung

Gegeben seien zwei wurzellose Bäume mit Knoten und eine Menge von Bezeichnungen (d. h. Taxa ) für jeden Knoten (die leer sein kann, aber nur Knoten mit einem Grad größer oder gleich drei können mit einer leeren Menge bezeichnet werden). Die Robinson-Foulds-Metrik bestimmt die Anzahl der Operationen , die nötig sind, um den einen Baum in den anderen umzuwandeln. Die Anzahl der Operationen definiert ihren Abstand. Wurzelbäume können untersucht werden, indem man dem Wurzelknoten ein Dummy-Blatt hinzufügt. ^[⁵^] $\alpha$ $\alpha ^{-1}$

Die Autoren definieren zwei Bäume als identisch, wenn sie isomorph sind und die Isomorphie die Beschriftung beibehält. Der Beweis basiert auf einer Funktion namens , die eine Kante kontrahiert (die Knoten kombiniert und ihre Mengen zur Vereinigungsmenge zusammenfasst). Umgekehrt expandiert eine Kante (Dekontraktion), wobei die Menge beliebig aufgeteilt werden kann. $\alpha$ $\alpha ^{-1}$

Die Funktion entfernt alle Kanten aus , die nicht in enthalten sind , und erstellt so . Anschließend werden die in gefundenen Kanten dem Baum hinzugefügt, um zu erstellen . Die Anzahl der Operationen in jedem dieser Schritte entspricht der Anzahl der Kanten in , die nicht in enthalten sind, plus der Anzahl der Kanten in , die nicht in enthalten sind . Die Summe der Operationen entspricht einer Transformation von nach oder umgekehrt. $\alpha$ $T_{1}$ $T_{2}$ $T_{1}\wedge T_{2}$ $\alpha ^{-1}$ $T_{2}$ $T_{1}\wedge T_{2}$ $T_{2}$ $T_{1}$ $T_{2}$ $T_{2}$ $T_{1}$ $T_{1}$ $T_{2}$

Eigenschaften

Die RF-Distanz entspricht einer äquivalenten Ähnlichkeitsmetrik, die die Auflösung des strikten Konsensus zweier Bäume widerspiegelt und erstmals 1980 zum Vergleich von Bäumen verwendet wurde. ^{[ 6 ]}

In ihrer Arbeit von 1981 ^{[ 1 ]} bewiesen Robinson und Foulds, dass die Distanz tatsächlich eine Metrik ist .

Algorithmen zur Berechnung der Metrik

1985 präsentierte Day einen auf perfektem Hashing basierenden Algorithmus, der diese Distanz berechnet und dessen Komplexität linear von der Anzahl der Knoten in den Bäumen abhängt. Ein randomisierter Algorithmus , der nicht notwendigerweise perfekte Hashtabellen verwendet, approximiert die Robinson-Foulds-Distanz mit beschränktem Fehler in sublinearer Zeit.

Spezifische Anwendungen

In der Phylogenetik wird die Metrik häufig verwendet, um den Abstand zwischen zwei Bäumen zu berechnen. Das Programm `treedist` aus der PHYLIP- Suite bietet diese Funktion, ebenso wie das Paket `RAxML_standard` , die Python-Bibliothek ` DendroPy` (unter dem Namen „symmetrische Differenzmetrik“) sowie die R-Pakete `TreeDist` ( RobinsonFoulds()Funktion) und `phangorn` ( treedist()Funktion). Für den Vergleich von Baumgruppen sind HashRF und MrsRF die schnellsten Implementierungen.

Die Robinson-Foulds-Metrik wurde auch in der quantitativen vergleichenden Sprachwissenschaft verwendet, um Distanzen zwischen Bäumen zu berechnen, die darstellen, wie Sprachen miteinander verwandt sind.

Stärken und Schwächen

Die RF-Metrik ist nach wie vor weit verbreitet, da die Anzahl der unterschiedlichen Aufspaltungen zwischen zwei Bäumen für viele Systematiker eine relativ intuitive Methode zur Beurteilung der Unterschiede darstellt. Dies ist die Hauptstärke der RF-Distanz und der Grund für ihre anhaltende Verwendung in der Phylogenetik. Natürlich hängt die Anzahl der unterschiedlichen Aufspaltungen zwischen zwei Bäumen von der Anzahl der Taxa in den Bäumen ab, sodass man argumentieren könnte, dass diese Einheit nicht aussagekräftig ist. RF-Distanzen lassen sich jedoch problemlos so normalisieren, dass sie Werte zwischen null und eins annehmen.

Allerdings weist die RF-Metrik auch eine Reihe theoretischer und praktischer Mängel auf: ^{[ 7 ]}^{[ 5 ]}

Im Vergleich zu anderen Metriken mangelt es an Sensitivität und ist daher ungenau; es kann zwei unterschiedliche Werte weniger annehmen, als Taxa in einem Baum vorhanden sind. ^{[ 7 ]}^{[ 5 ]}
Es ist schnell gesättigt; sehr ähnlichen Bäumen kann der maximale Distanzwert zugewiesen werden. ^{[ 7 ]}
Sein Wert kann kontraintuitiv sein. Ein Beispiel: Das Verschieben einer Spitze und ihrer Nachbarspitze an einen bestimmten Punkt eines Baumes erzeugt einen geringeren Differenzwert, als wenn nur eine der beiden Spitzen an dieselbe Stelle verschoben würde. ^{[ 7 ]}
Die Bandbreite der Werte kann von der Baumform abhängen: Bäume mit vielen ungleichmäßigen Partitionen weisen im Durchschnitt relativ geringere Distanzen auf als Bäume mit vielen gleichmäßigen Partitionen. ^{[ 7 ]}
In der Praxis schneidet es auf Basis simulierter Entscheidungsbäume schlechter ab als viele alternative Verfahren. ^{[ 5 ]}

Ein weiterer Aspekt bei der Verwendung von RF-Distanzen ist, dass Unterschiede innerhalb einer Klade trivial sein können (etwa wenn die Klade drei Arten innerhalb einer Gattung unterschiedlich einordnet) oder fundamental (wenn die Klade tief im Stammbaum liegt und zwei fundamentale Untergruppen definiert, wie z. B. Säugetiere und Vögel). Dieses Problem betrifft jedoch nicht die RF-Distanzen an sich, sondern ist eine allgemeinere Kritik an Baumdistanzen. Unabhängig vom Verhalten einer bestimmten Baumdistanz kann ein praktizierender Evolutionsbiologe manche Baumumlagerungen als „wichtig“ und andere als „trivial“ einstufen. Baumdistanzen sind Werkzeuge; sie sind am nützlichsten im Kontext anderer Informationen über die Organismen in den Bäumen.

Diese Probleme lassen sich durch die Verwendung weniger konservativer Metriken beheben. „Generalisierte RF-Distanzen“ berücksichtigen die Ähnlichkeit zwischen ähnlichen, aber nicht identischen Aufteilungen; die ursprüngliche Robinson-Foulds-Distanz hingegen misst der Ähnlichkeit zweier Gruppierungen keine Bedeutung; sind sie nicht identisch, werden sie verworfen. ^{[ 4 ]}

Die leistungsstärksten verallgemeinerten Robinson-Foulds-Distanzen basieren auf der Informationstheorie und messen die Distanz zwischen Bäumen anhand der Informationsmenge, die die Aufteilungen der Bäume gemeinsam enthalten (gemessen in Bit). ^{[ 5 ]} Die Clustering Information Distance (implementiert im R-Paket TreeDist ) wird als geeignetste Alternative zur Robinson-Foulds-Distanz empfohlen. ^{[ 5 ]}

Ein alternativer Ansatz zur Berechnung der Baumdistanz besteht darin , die Quartettdistanz anstelle von Aufteilungen als Grundlage für den Baumvergleich zu verwenden. ^{[ 7 ]}

Software-Implementierungen

Sprache/Programm	Funktion	Anmerkungen
R	`dist.dendlist(dendlist(x,y))`von dendextend	Siehe [1]
R	`RobinsonFoulds(x, y)`von TreeDist	Schneller als die Phangorn-Implementierung; siehe [2]
Python	`tree_1.robinson_foulds(tree_2)`von ete3	Siehe [3]
Julia	`hardwiredClusterDistance(tree1, tree2, true)`von PhyloNetworks	Siehe [4]

Referenzen

^ ^a ^b ^c Robinson, DF; Foulds, LR (Februar 1981). „Vergleich phylogenetischer Bäume“ . Mathematical Biosciences . 53 ( 1–2 ): 131–147 . doi : 10.1016/0025-5564(81)90043-2 .
Kuhner , Mary K.; Yamato, Jon (1. März 2015). „Praktische Leistungsfähigkeit von Metriken zum Baumvergleich“ . Systematic Biology . 64 (2): 205–214 . doi : 10.1093/sysbio/syu085 . ISSN 1076-836X . PMID 25378436 .
^ Y. Lin, V. Rajan, BM Moret Eine Metrik für phylogenetische Bäume basierend auf Matching IEEE/ACM Trans. Comput. Biol. Bioinform., 9 (4) (2012), S. 1014-1022
^ ^a ^b
*Böcker S., Canzar S., Klau GW 2013. Die verallgemeinerte Robinson-Foulds-Metrik. In: Darling A., Stoye J., Hrsg. Algorithmen in der Bioinformatik. WABI 2013. Lecture Notes in Computer Science, Band 8126. Berlin, Heidelberg: Springer. S. 156–169.
- Bogdanowicz D., Giaro K. 2012. Matching split distance for unrooted binary phylogenetic trees. IEEE/ACM Trans. Comput. Biol. Bioinforma. 9:150–160.
- Bogdanowicz D., Giaro K. 2013. Über eine passende Distanz zwischen gewurzelten phylogenetischen Bäumen. Int. J. Appl. Math. Comput. Sci. 23:669–684.
- Nye TMW, Liò P., Gilks WR 2006. Ein neuartiger Algorithmus und ein webbasiertes Werkzeug zum Vergleich zweier alternativer phylogenetischer Bäume. Bioinformatics. 22:117–119.
^ ^a ^b ^c ^d ^e ^fSmith, Martin R. (2020). "Information theoretic Generalized Robinson-Foulds metrics for comparing phylogenetic trees"(PDF). Bioinformatics. 36 (20): 5007–5013. doi:10.1093/bioinformatics/btaa614. PMID 32619004.
^Schuh, R. T. & Polhemus, J. T. (1980). "Analysis of taxonomic congruence among morphological, ecological and biogeographic data sets for the Leptopodomorpha (Hemiptera)". Systematic Biology. 29 (1): 1–26. doi:10.1093/sysbio/29.1.1. ISSN 1063-5157.
^ ^a ^b ^c ^d ^e ^fSmith, Martin R. (2019). "Bayesian and parsimony approaches reconstruct informative trees from simulated morphological datasets"(PDF). Biology Letters. 15 (2). 20180632. doi:10.1098/rsbl.2018.0632. PMC 6405459. PMID 30958126.