The Robinson–Foulds distance
An intuitive way to calculate the similarity between two trees is to calculate the resolution of their strict consensus, which corresponds to the number of splits that occur in both trees (Schuh & Polhemus, 1980). The corresponding distance measure, the Robinson–Foulds distance (Robinson & Foulds, 1981), counts the number of splits that are unique to one of the two trees.
It is important to remember that counting splits is not the same as counting clades, edges or nodes. If a tree is drawn as rooted (even without a root edge), then the number of splits is one less than the number of edges or clades, and two less than the number of nodes. For example, the trees below have one split, two edges and three nodes in common.
The simplicity of counting splits is appealing, but limited by the underlying assumption that all splits are equivalent.
As an example, a split that separates eight leaves into two sets of four (as in the right-hand tree above) has a \(\frac{1}{35}\) chance of being compatible with the reference tree. In contrast, a split that separates two leaves from the other six has a \(\frac{1}{7}\) chance of matching the reference tree: the similarity observed is five times more likely to have arisen by chance. In other words, failure to match an even split is less noteworthy than failure to match an uneven one.
As a consequence, trees whose splits are less even will, on average, exhibit higher Robinson–Foulds distances with comparison trees. Compare a balanced and an unbalanced eight-taxon tree:
Each tree divides the eight taxa into five splits. The phylogenetic information content of a split is a function of the probability that the split will match a uniformly chosen random tree, i.e. the proportion of eight-leaf binary trees that contain the split in question. (Information content, in bits, is defined as \(-\log_2(\textrm{probability})\).) This, in turn, is a function of the evenness of the split:
| Matching trees | P(Match in random tree) | Phylogenetic information content | |
|---|---|---|---|
| Split size: 2:6 | 945 / 10 395 | 0.0909 | 3.46 bits |
| Split size: 3:5 | 315 / 10 395 | 0.0303 | 5.04 bits |
| Split size: 4:4 | 225 / 10 395 | 0.0216 | 5.53 bits |
In the first tree, split 1 is even, dividing four taxa from four
others (4|4); splits 2–5 are maximally uneven
(2|6). If each split is treated as independent, then the
total information content of the five splits is 19.37 bits, whereas that
of the five splits in the second tree, of sizes 2|6,
3|5, 4|4, 3|5 and
2|6, is 22.54 bits. Put another way, a random tree will on
average share more splits with the balanced tree (whose splits are
predominantly uneven and thus likely to be matched) than the asymmetric
tree (which contains more even splits that are less likely to occur in a
random tree).
Indeed, of the 10 395 eight-leaf trees, many more bear at least one split in common with a balanced tree than with an asymmetric tree:
