Optimal evolutionary tree comparison by sparse dynamic programming

In computational biology one is often interested in finding the concensus between different evolutionary trees for the same set of species. A popular formalizations is the Maximum Agreement Subtree Problem (MAST) defined 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 ofA such that the restrictions of T₀ and T₁ to B are topologically isomorphic. Polynomial time solutions exist, but they rely on a dynamic program with Θ(n²) nodes-and Θ(n²) running time. We sparsify this dynamic program and show that MAST is equivalent to Unary Weighted Bipartite Matching (UWBM) modulo an O(nc ^logn) additive overhead. Applying the best bound for UWBM, we get an O(n^{1. 5}logn) algorithm for MAST. From our sparsification follows an O(nc ^logn) time algorithm for the special case of bounded degrees. Also here the best previous bound was Θ(n²).