Phylogeny Comparison with Split Distance

Problem

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 s(T1,T2) denotes the number of nontrivial splits shared by unrooted binary trees T1 and T2, Then their split distance is dsplit(T1,T2)=2(n−3)−2s(T1,T2).

Given: A collection of at most 3,000 species taxa and two unrooted binary trees T1 and T2 on these taxa in Newick format.

Return: The split distance dsplit(T1,T2).