Robinson–Foulds metric
 | This article has been nominated to be checked for its neutrality. (September 2020) (Learn how and when to remove this template message) |
The Robinson–Foulds or symmetric difference metric, often abbreviated as the RF distance, is a simple way to calculate the distance between phylogenetic trees.[1]
It is defined as (A + B) where A is the number of partitions of data implied by the first tree but not the second tree and B is the number of partitions of data implied by the second tree but not the first tree (although some software implementations divide the RF metric by 2[2] and others scale the RF distance to have a maximum value of 1). The partitions are calculated for each tree by removing each branch. Thus, the number of eligible partitions for each tree is equal to the number of branches in that tree.
RF distances have been criticized as biased,[3] but they represent a relatively intuitive measure of the distances between phylogenetic trees and therefore remain widely used (the original 1981 paper describing Robinson-Foulds distances[1] was cited more than 2700 times by 2023 based on Google Scholar). Nevertheless, the biases inherent to the RF distances suggest that researches should consider using "Generalized" Robinson–Foulds metrics[4] that may have better theoretical and practical performance and avoid the biases and misleading attributes of the original metric.
Explanation
Given two unrooted trees of nodes and a set of labels (i.e., taxa) for each node (which could be empty, but only nodes with degree greater than or equal to three can be labeled by an empty set) the Robinson–Foulds metric finds the number of [math]\displaystyle{ \alpha }[/math] and [math]\displaystyle{ \alpha^{-1} }[/math] operations to convert one into the other. The number of operations defines their distance. Rooted trees can be examined by attaching a dummy leaf to the root node.[5]
The authors define two trees to be the same if they are isomorphic and the isomorphism preserves the labeling. The construction of the proof is based on a function called [math]\displaystyle{ \alpha }[/math], which contracts an edge (combining the nodes, creating a union of their sets). Conversely, [math]\displaystyle{ \alpha^{-1} }[/math] expands an edge (decontraction), where the set can be split in any fashion.
The [math]\displaystyle{ \alpha }[/math] function removes all edges from [math]\displaystyle{ T_1 }[/math] that are not in [math]\displaystyle{ T_2 }[/math], creating [math]\displaystyle{ T_1 \wedge T_2 }[/math], and then [math]\displaystyle{ \alpha^{-1} }[/math] is used to add the edges only discovered in [math]\displaystyle{ T_2 }[/math] to the tree [math]\displaystyle{ T_1 \wedge T_2 }[/math] to build [math]\displaystyle{ T_2 }[/math]. The number of operations in each of these procedures is equivalent to the number of edges in [math]\displaystyle{ T_1 }[/math] that are not in [math]\displaystyle{ T_2 }[/math] plus the number of edges in [math]\displaystyle{ T_2 }[/math] that are not in [math]\displaystyle{ T_1 }[/math]. The sum of the operations is equivalent to a transformation from [math]\displaystyle{ T_1 }[/math] to [math]\displaystyle{ T_2 }[/math], or vice versa.
Properties
The RF distance corresponds to an equivalent similarity metric that reflects the resolution of the strict consensus of two trees, first used to compare trees in 1980.[6]
In their 1981 paper[1] Robinson and Foulds proved that the distance is in fact a metric.
Algorithms for computing the metric
In 1985 Day gave an algorithm based on perfect hashing that computes this distance that has only a linear complexity in the number of nodes in the trees. A randomized algorithm that uses hash tables that are not necessarily perfect has been shown to approximate the Robinson-Foulds distance with a bounded error in sublinear time.
Specific applications
In phylogenetics, the metric is often used to compute a distance between two trees. The treedist program in the PHYLIP suite offers this function, as does the RAxML_standard package, the DendroPy Python library (under the name "symmetric difference metric"), and R packages TreeDist (`RobinsonFoulds()` function) and phangorn (`treedist()` function). For comparing groups of trees, the fastest implementations include HashRF and MrsRF.
The Robinson–Foulds metric has also been used in quantitative comparative linguistics to compute distances between trees that represent how languages are related to each other.
Strengths and weaknesses
The RF metric remains widely used because the idea of using the number of splits that differ between a pair of trees is a relatively intuitive way to assess the differences among trees for many systematists. This is the primary strength of the RF distance and the reason for its continued use in phylogenetics. Of course, the number of splits that differ between a pair of trees depends on the number of taxa in the trees so one might argue that this unit is not meaningful. However, it is straightforward to normalize RF distances so they range between zero and one.
However, the RF metric also suffers a number of theoretical and practical shortcomings:[7][5]
- Relative to other metrics, lacks sensitivity, and is thus imprecise; it can take two fewer distinct values than there are taxa in a tree.[7][5]
- It is rapidly saturated; very similar trees can be allocated the maximum distance value.[7]
- Its value can be counterintuitive. One example is that moving a tip and its neighbour to a particular point on a tree generates a lower difference value than if just one of the two tips were moved to the same place.[7]
- Its range of values can depend on tree shape: trees that contain many uneven partitions will command relatively lower distances, on average, than trees with many even partitions.[7]
- It performs more poorly than many alternative measures in practical settings, based on simulated trees.[5]
Another issue to consider when using RF distances is that differences in one clade may be trivial (perhaps if the clade resolves three species within a genus differently) or may be fundamental (if the clade is deep in the tree and defines two fundamental subgroups, such as mammals and birds). However, this issue is not a problem with RF distances per se, it is a more general criticism of tree distances. Regardless of the behaviour of any specific tree distance a practicing evolutionary biologist might view some tree rearrangements as "important" and other rearrangements as "trivial". Tree distances are tools; they are most useful in the context of other information about the organisms in the trees.
These issues can be addressed by using less conservative metrics. "Generalized RF distances" recognize similarity between similar, but non-identical, splits; the original Robinson Foulds distance doesn't care how similar two groupings are, if they aren't identical they are discarded.[4]
The best-performing generalized Robinson-Foulds distances have a basis in information theory, and measure the distance between trees in terms of the quantity of information that the trees' splits hold in common (measured in bits).[5] The Clustering Information Distance (implemented in R package TreeDist) is recommended as the most suitable alternative to the Robinson-Foulds distance.[5]
An alternative approach to tree distance calculation is to use Quartet distance, rather than splits, as the basis for tree comparison.[7]
Software implementations
| Language/Program | Function | Notes |
|---|---|---|
| R | dist.dendlist(dendlist(x,y)) from dendextend |
See [1] |
| R | RobinsonFoulds(x, y) from TreeDist |
Faster than phangorn implementation; see [2] |
| Python | tree_1.robinson_foulds(tree_2) from ete3 |
See [3] |
| Julia | hardwiredClusterDistance(tree1, tree2, true) from PhyloNetworks |
See [4] |
References
- ↑ 1.0 1.1 1.2 Robinson, D.F.; Foulds, L.R. (February 1981). "Comparison of phylogenetic trees" (in en). Mathematical Biosciences 53 (1–2): 131–147. doi:10.1016/0025-5564(81)90043-2. https://linkinghub.elsevier.com/retrieve/pii/0025556481900432.
- ↑ Kuhner, Mary K.; Yamato, Jon (2015-03-01). "Practical Performance of Tree Comparison Metrics" (in en). Systematic Biology 64 (2): 205–214. doi:10.1093/sysbio/syu085. ISSN 1076-836X. PMID 25378436. https://academic.oup.com/sysbio/article/64/2/205/1630737.
- ↑ Y. Lin, V. Rajan, B.M. Moret A metric for phylogenetic trees based on matching IEEE/ACM Trans. Comput. Biol. Bioinform., 9 (4) (2012), pp. 1014-1022
- ↑ 4.0 4.1 *Böcker S., Canzar S., Klau G.W. 2013. The generalized Robinson-Foulds metric. In: Darling A., Stoye J., editors. Algorithms in Bioinformatics. WABI 2013. Lecture Notes in Computer Science, vol 8126. Berlin, Heidelberg: Springer. p. 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. On a matching distance between rooted phylogenetic trees. Int. J. Appl. Math. Comput. Sci. 23:669–684.
- Nye T.M.W., Liò P., Gilks W.R. 2006. A novel algorithm and web-based tool for comparing two alternative phylogenetic trees. Bioinformatics. 22:117–119.
- ↑ 5.0 5.1 5.2 5.3 5.4 5.5 Smith, Martin R. (2020). "Information theoretic Generalized Robinson-Foulds metrics for comparing phylogenetic trees". Bioinformatics 36 (20): 5007–5013. doi:10.1093/bioinformatics/btaa614. PMID 32619004. http://dro.dur.ac.uk/31189/1/31189.pdf.
- ↑ 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.
- ↑ 7.0 7.1 7.2 7.3 7.4 7.5 Smith, Martin R. (2019). "Bayesian and parsimony approaches reconstruct informative trees from simulated morphological datasets". Biology Letters 15 (2): 20180632. doi:10.1098/rsbl.2018.0632. PMID 30958126. PMC 6405459. http://dro.dur.ac.uk/27164/1/27164.pdf.
Further reading
- M. Bourque, Arbres de Steiner et reseaux dont certains sommets sont a localisation variable. PhD thesis, University 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, D. R.; Foulds, L. R. (1981). "Comparison of phylogenetic trees". Mathematical Biosciences 53 (1–2): 131–147. doi:10.1016/0025-5564(81)90043-2.
- William H. E. Day, "Optimal algorithms for comparing trees with labeled leaves", Journal of Classification, Number 1, December 1985. doi:10.1007/BF01908061
- Makarenkov, V and Leclerc, B. Comparison of additive trees using circular orders, Journal of Computational Biology,7,5,731-744,2000,"Mary Ann Liebert, Inc."
- Pattengale, Nicholas D.; Gottlieb, Eric J.; Moret, Bernard M.E. (2007). "Efficiently Computing the Robinson–Foulds Metric". Journal of Computational Biology 14 (6): 724–735. doi:10.1089/cmb.2007.R012. PMID 17691890.
- Sukumaran, J.; Holder, Mark T. (2010). "DendroPy: A Python library for phylogenetic computing". Bioinformatics 26 (12): 1569–1571. doi:10.1093/bioinformatics/btq228. PMID 20421198.
 |  |
