Review: Comparison of Phylogenetic Trees¶
Citation
- Robinson, D. F., & Foulds, L. R. (1981). Comparison of phylogenetic trees. Mathematical Biosciences, 53(1–2), 131–147.
- DOI
Abstract¶
Several measures for comparing unrooted phylogenetic trees on the same set of labeled leaves are introduced and analyzed. The symmetric difference of the bipartition sets (the Robinson-Foulds distance) is shown to be a metric and is compared with edit-distance and other criteria. Properties of the metric and algorithms for computing it are discussed.
Phylogenetic trees can differ in both topology and branch lengths. Robinson and Foulds (1981) address the question of how to measure topological difference alone: given two unrooted trees on the same set of taxa, how many "steps" does it take to go from one to the other?
The key insight is that every internal branch of an unrooted binary tree defines a bipartition (or split) of the leaf set into two groups, one on each side of the branch. Two trees that share a bipartition can be considered topologically similar in that respect; two trees that do not share any bipartitions are maximally different. The Robinson-Foulds (RF) distance is defined as the size of the symmetric difference of the bipartition sets:
where \( B(T) \) is the set of bipartitions induced by tree \( T \) and \( \triangle \) is symmetric difference (elements in one set but not both). For two fully resolved binary trees on \( n \) leaves, the maximum RF distance is \( 2(n - 3) \).
The paper proves that \( d_\mathrm{RF} \) is a metric: it satisfies non-negativity, symmetry, the identity of indiscernibles, and the triangle inequality. It also gives an efficient algorithm for computing it.
In Hifuku, the RF distance is the topological term of the tree metric (Section 5). The normalized branch score \( d^2 = (1 - w)\,\mathrm{CBS}^2/C_\mathrm{ref} + w\,\mathrm{RF}/R_\mathrm{ref} \) mixes the Robinson-Foulds count against the clade branch score under a weight \( w \in [0, 1] \), moving the metric from pure branch length (\( w = 0 \)) to pure topology (\( w = 1 \)). RF is purely topological and ignores branch lengths, while the clade branch score integrates both. On the GPU the RF term is computed from a shared-split count with a root-pair deduplication. The two ends of the weight agree on the qualitative ordering of trees in many cases but can disagree significantly when branch lengths are highly variable.
The RF distance is also used by IQ-TREE 2 (see Minh et al. 2020) to assess convergence of tree search algorithms, and it is the standard tool for comparing reference trees to inferred trees in benchmarking experiments.