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 T0 and T1 leaf-labeled by the elements of A, find a maximum cardinality subset B ofA such that the restrictions of T0 and T1 to B are topologically isomorphic. Polynomial time solutions exist, but they rely on a dynamic program with Θ(n2) nodes-and Θ(n2) 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(n1. 5logn) 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 Θ(n2).
|Number of pages
|Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
|Published - 1994
|Proceedings of the 35th IEEE Annual Symposium on Foundations of Computer Science - Santa Fe, NM, USA
Duration: Nov 20 1994 → Nov 22 1994
All Science Journal Classification (ASJC) codes
- General Computer Science