Optimal Evolutionary Tree Comparison by Sparse Dynamic Programming (Extended Abstract)
Martı́n Farach-Colton, Mikkel Thorup · 1994
) Martin Farach 3 Mikkel Thorup y Department of Computer Science Department of Computer Science Rutgers University University of Copenhagen Piscataway, NJ 08855 2100 København Ø USA Denmark Abstract 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 0 and T 1 leaf-labeled by the elements of A, find a maximum cardinality subset B of A such that the restrictions of T 0 and T 1 to B are topologically isomorphic. Polynomial time solutions exist, but they rely on a dynamic program with 2(n 2 ) nodes---and 2(n 2 ) running time. We sparsify this dynamic program and show that MAST is equivalent to Unary Weighted Bipartite Matching (UWBM) modulo an O(nc p log n ) additive overhead. Applying the best bound for UWBM, we get an O(n 1:5 log n) algorithm for MAST. From ...