Robinson–Foulds metric
The Robinson–Foulds or symmetric difference metric is a crude and biased measure of the distance between unrooted phylogenetic trees. It is defined as 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. 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. Generalzied Robinson-Foulds metrics have superseded the original metric: these demonstrate 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 for each node the Robinson–Foulds metric finds the number of and operations to convert one into the other. The number of operations defines their distance. Rooted trees can be examined by assigning a label to the leaf node.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, which contracts an edge. Conversely, expands an edge, where the set can be split in any fashion.
The function removes all edges from that are not in, creating, and then is used to add the edges only discovered in to the tree to build . The number of operations in each of these procedures is equivalent to the number of edges in that are not in plus the number of edges in that are not in. The sum of the operations is equivalent to a transformation from to, 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.In their 1981 paper 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 package, the Python library, and R packages and . 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.
Shortcomings
The RF metric suffers a number of theoretical and practical shortcomings:- Relative to other metrics, lacks sensitivity, and is thus imprecise; it can take two fewer distinct values than there are taxa in a tree.
- It is rapidly saturated; very similar trees can be allocated the maximum distance value.
- 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.
- 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.
- It lacks a meaningful unit: a difference of one clade may be trivial, or may be fundamental.
- It performs more poorly than many alternative measures in practical settings, based on simulated trees.
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. The Clustering Information Distance is recommended as the most suitable alternative to the Robinson-Foulds distance.
An alternative approach to tree distance calculation is to use quartets, rather than splits, as the basis for tree comparison.
Software implementations
| Language/Program | Function | Notes |
| R | dist.dendlist from dendextend | See |
| R | RobinsonFoulds from TreeDist | Faster than phangorn implementation; see |
| Python | tree_1.robinson_foulds from ete3 | See |