Sparse dynamic programming for evolutionary-tree comparison

Constructing evolutionary trees for species sets is a fundamental problem in biology. Unfortunately, there is no single agreed upon method for this task, and many methods are in use. Current practice dictates that trees be constructed using different methods and that the resulting trees should be compared for consensus. It has become necessary to automate this process as the number of species under consideration has grown. We study one formalisation of the problem: the maximum agreement-subtree (MAST) problem. The MAST problem is as follows: given a set A and two rooted trees T₀ and T₁ leaf-labeled by the elements of A, find a maximum-cardinality subset B of A such that the topological restrictions of T₀ and T₁ to B are isomorphic. In this paper, we will show that this problem reduces to unary weighted bipartite matching (UWBM) with an O(n^1+o(1)) additive overhead. We also show that UWBM reduces linearly to MAST. Thus our algorithm is optimal unless UWBM can be solved in near linear time. The overall running time of our algorithm is O(n^1.5 log n), improving on the previous best algorithm, which runs in O(n²). We also derive an O(nc^{√log n})-time algorithm for the case of bounded degrees, whereas the previously best algorithm runs in O(n²), as in the unbounded case.