Sparse Dynamic Programming for Evolutionary-Tree Comparison

摘要: Constructing evolutionary trees for species sets is a fundamental problem in biology. Unfortunately, there no single agreed upon method this task, and many methods are use. Current practice dictates that be constructed using different the resulting should compared consensus. It has become necessary to automate process as number of under consideration grown. We study one formalization problem: maximum agreement-subtree $($\MAST$)$ problem. The $\MAST$ follows: given set $A$ two rooted $\cT_0$ $\cT_1$ leaf-labeled by elements $A$, find maximum-cardinality subset $B$ such topological restrictions isomorphic. In paper, we will show reduces unary weighted bipartite matching ($\UWBM$) with an $O(n^{1+o(1)})$ additive overhead. also $\UWBM$ linearly $\MAST$. Thus our algorithm optimal unless can solved near linear time. The overall running time $O(n^{1.5} \log n)$, improving on previous best algorithm, which runs $O(n^2)$. derive $O(n c^{\sqrt{\log n}})$-time case bounded degrees, whereas previously $O(n^2),$ unbounded case.