Optimal Evolutionary Tree Comparison by Sparse Dynamic Programming (Extended 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 /spl Tscr//sub 0/ and /spl Tscr//sub 1/ leaf-labeled by the elements of A, find a maximum cardinality subset B of A such that the restrictions of /spl Tscr//sub 0/ and /spl Tscr//sub 1/ to B are topologically isomorphic. Polynomial time solutions exist, but they rely on a dynamic program with /spl Theta/(n/sup 2/) nodes-and /spl Theta/(n/sup 2/) running time. We sparsify this dynamic program and show that MAST is equivalent to Unary Weighted Bipartite Matching (UWBM) modulo an O(nc/sup /spl radic/(log n/) additive overhead. Applying the best bound for UWBM, we get an O(n/sup 1. 5/ log n) algorithm for MAST. From our sparsification follows an O(nc/sup /spl radic/(log n/)) time algorithm for the special case of bounded degrees. Also here the best previous bound was /spl Theta/(n/sup 2/). >

Authors

• Martín Farach-Colton
• Mikkel Thorup

Keywords

• Dynamic programming
• Computer science
• History
• Contracts
• Evolution (biology)
• Genetic programming
• Computational biology
• Polynomials
• Additives
• Phylogeny
• Sparse Dynamic Programming
• Bipartite Matching
• Total Weight
• Edge Weights
• Pair Of Nodes
• Linear Time
• Sum Of Weights
• Root Of The Tree
• RNA Secondary Structure
• Algorithm For Problem
• Set Of Species
• Binary Tree
• TreeBASE
• Critical Nodes
• Lowest Common Ancestor
• Maximum Matching
• Core Nodes
• Graph Matching
• Weight Matching
• Balanced Tree