The Robinson–Foulds distance
An intuitive way to calculate the similarity between two trees is tocalculate the resolution of their strict consensus, which corresponds tothe number of splits that occur in both trees(Schuh & Polhemus, 1980). The correspondingdistance measure, the Robinson–Foulds distance(Robinson & Foulds, 1981), counts the numberof splits that are unique to one of the two trees.
It is important to remember that counting splits is not the same ascounting clades, edges or nodes. If a tree is drawn as rooted (evenwithout a root edge), then the number of splits is one less than thenumber of edges or clades, and two less than the number of nodes. Forexample, the trees below have one split, two edges and three nodes incommon.
The simplicity of counting splits is appealing, but limited by theunderlying assumption that all splits are equivalent.
As an example, a split that separates eight leaves into two sets offour (as in the right-hand tree above) has a\(\frac{1}{35}\) chance of being compatiblewith the reference tree. In contrast, a split that separates two leavesfrom the other six has a\(\frac{1}{7}\) chance of matching thereference tree: the similarity observed is five times more likely tohave arisen by chance. In other words, failure to match an even split isless 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. Comparea balanced and an unbalanced eight-taxon tree:
Each tree divides the eight taxa into five splits. Thephylogenetic information content of a splitis a function of the probability that the split will match a uniformlychosen random tree, i.e. the proportion of eight-leaf binary trees thatcontain the split in question. (Information content, in bits, is definedas\(-\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 fourothers (4|4); splits 2–5 are maximally uneven(2|6). If each split is treated as independent, then thetotal information content of the five splits is 19.37 bits, whereas thatof the five splits in the second tree, of sizes2|6,3|5,4|4,3|5 and2|6, is 22.54 bits. Put another way, a random tree will onaverage share more splits with the balanced tree (whose splits arepredominantly uneven and thus likely to be matched) than the asymmetrictree (which contains more even splits that are less likely to occur in arandom tree).
Indeed, of the 10 395 eight-leaf trees, many more bear at least onesplit in common with a balanced tree than with an asymmetric tree: