July 2, 2012, midnight by Rosalind Team
Topics: Phylogeny
Quantifying Binary Tree Comparison
We may often obtain two different phylogenies on the same collection of taxa from different sets of data. As a result, we would like to have a way of quantifying how much the two phylogenies differ. In the simplest case, we would like to compare the characters of two phylogenies.
Recall from “Counting Unrooted Binary Trees” that two unrooted binary trees are equivalent when they have the same set of splits; recall also (by extension of “Counting Phylogenetic Ancestors”) that any unrooted binary tree on
$n$ taxa must have$n - 3$ nontrivial splits.
Define the split distance between two unrooted binary trees as the number of nontrivial splits contained in one tree but not the other.
Formally, if
Given: A collection of at most 3,000 species taxa and two unrooted binary trees
Return: The split distance
dog rat elephant mouse cat rabbit (rat,(dog,cat),(rabbit,(elephant,mouse))); (rat,(cat,dog),(elephant,(mouse,rabbit)));
2