SPARSE DYNAMIC-PROGRAMMING FOR EVOLUTIONARY-TREE COMPARISON

Constructing evolutionary trees for species sets is a fundamental prob lem in biology. Unfortunately, there is no single agreed upon method f or this task, and many methods are in use. Current practice dictates t hat trees be constructed using different methods and that the resultin g trees should be compared for consensus. It has become necessary to a utomate this process as the number of species under consideration has grown. We study one formalization of the problem: the maximum agreemen t-subtree (MAST) problem. The MAST problem is as follows: given a set A and two rooted trees T-0 and T-1 leaf-labeled by the elements of A, find a maximum-cardinality subset B of A such that the topological res trictions of T-0 and T-1 to B are isomorphic. In this paper, we will s how that this problem reduces to unary weighted bipartite matching (UW BM) with an O(n(1+o(1))) additive overhead. We also show that UWBM red uces linearly to MAST. Thus our algorithm is optimal unless UWBM can b e solved in near linear time. The overall running time of our algorith m is O(n(1.5)log n), improving on the previous best algorithm, which r uns in O(n(2)). We also derive an O(nc(root log n))-time algorithm for the case of bounded degrees, whereas the previously best algorithm ru ns in O(n(2)), as in the unbounded case.