On the complexity of comparing evolutionary trees
On the complexity of comparing evolutionary trees
复制标题
DOI：
10.1016/s0166-218x(96)00062-5
复制
发表时间：
1996-12-05
影响因子：
1.1
通讯作者：
Zhang, KZ
中科院分区：
文献类型：
--
作者：
Hein, J;Jiang, T;Zhang, KZ
我们研究了进化树比较中出现的几个问题的计算复杂性和近似。结果表明，对于任何 delta < 1，三棵无界度树的最大一致性子树 (MAST) 问题不能在多项式时间内在比率 2(log delta n) 内近似，除非 NP 子集等于或等于 DTIME[2(polylog n)]，并且两棵二叉树的边缘收缩的 MAST 是 NP 困难的。这回答了[1]中提出的两个悬而未决的问题。对于涉及两棵树的最大细化子树（MRST）问题，我们证明当两棵树都具有有界度时，该问题是多项式时间可解的；当其中一棵树可以具有任意度时，该问题是 NP 困难的。最后，我们考虑通过转移子树将一棵树最优地转换为另一棵树的问题。结果表明，子树转移距离的计算是NP困难的，并给出了性能比为3的近似算法。
We study the computational complexity and approximation of several problems arising in the comparison of evolutionary trees. It is shown that the maximum agreement subtree (MAST) problem for three trees with unbounded degree cannot be approximated within ratio 2(log delta n) in polynomial time for any delta < 1, unless NP subset of or equal to DTIME[2(polylog n)], and MAST with edge contractions for two binary trees is NP-hard. This answers two open questions posed in [1]. For the maximum refinement subtree (MRST) problem involving two trees, we show that it is polynomial-time solvable when both trees have bounded degree and is NP-hard when one of the trees can have an arbitrary degree. Finally, we consider the problem of optimally transforming a tree into another by transferring subtrees around. It is shown that computing the subtree-transfer distance is NP-hard and an approximation algorithm with performance ratio 3 is given.