TY - JOUR

T1 - Optimal evolutionary tree comparison by sparse dynamic programming

AU - Farach, Martin

AU - Thorup, Mikkel

N1 - Funding Information:
*farachOcs .r utgers. edu; Supported by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center under NSF contract STC-8809648. tmthorup0diku.dk; Most of the research in this paper was done while the second author was visiting DIMACS. Supported by the Danish Technical Research Council, by the Danish Re- search Academy and by DIMACS under NSF contract STC-8809648.
Publisher Copyright:
© 1994 IEEE

PY - 1994

Y1 - 1994

N2 - 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).

AB - 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).

UR - http://www.scopus.com/inward/record.url?scp=0041563636&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0041563636&partnerID=8YFLogxK

U2 - 10.1109/SFCS.1994.365716

DO - 10.1109/SFCS.1994.365716

M3 - Conference article

AN - SCOPUS:0041563636

SN - 0272-5428

SP - 770

EP - 779

JO - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

JF - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

T2 - Proceedings of the 35th IEEE Annual Symposium on Foundations of Computer Science

Y2 - 20 November 1994 through 22 November 1994

ER -