Sparse dynamic programming for evolutionary-tree comparison

作     者：Farach, M Thorup, M 

作者机构：UNIV COPENHAGENDEPT COMP SCIDK-2100 COPENHAGENDENMARK 

出 版 物：《SIAM JOURNAL ON COMPUTING》 (工业与应用数学会计算杂志)

年 卷 期：1997年第26卷第1期

页      面：210-230页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：sparse dynamic programming computational biology evolutionary trees 

摘      要：Constructing evolutionary trees for species sets is a fundamental problem in biology. Unfortunately, there is no single agreed upon method for this task, and many methods are in use. Current practice dictates that trees be constructed using different methods and that the resulting trees should be compared for consensus. It has become necessary to automate this process as the number of species under consideration has grown. We study one formalization of the problem: the maximum agreement-subtree (MAST) problem. The MAST problem is 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 topological restrictions of T-0 and T-1 to B are isomorphic. In this paper, we will show that this problem reduces to unary weighted bipartite matching (UWBM) with an O(n(1+o(1))) additive overhead. We also show that UWBM reduces linearly to MAST. Thus our algorithm is optimal unless UWBM can be solved in near linear time. The overall running time of our algorithm is O(n(1.5)log n), improving on the previous best algorithm, which runs in O(n(2)). We also derive an O(nc(root log n))-time algorithm for the case of bounded degrees, whereas the previously best algorithm runs in O(n(2)), as in the unbounded case.