Optimizing tree and character compatibility across several phylogenetic trees
Optimizing tree and character compatibility across several phylogenetic trees
复制标题
优化多个系统发育树的树和特征兼容性
DOI：
10.1016/j.tcs.2013.10.015
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
C. Semple
中科院分区：
文献类型：
--
作者：
S. Linz;K. S. John;C. Semple
给定重叠分类群上的有根系统发生树的集合R，判定是否存在与R相容的有根系统发生树需要多项式时间。由于不是一组物种的所有进化历史都可以用一棵树来解释，所以很自然地要求所需的有根系统发育树的最小数量，使得R中的每棵树至少与一棵树兼容。本文表明，这是计算上很难计算这个最小数目。特别地，如果R包含有根三元组（三个叶子上的有根二元系统发生树），则判定是否存在两个有根系统发生树使得R中的每个有根三元组与两个树中的至少一个相容是NP完全的。此外，对于一组二进制字符和一个正整数k，我们表明，以确定是否存在一组P的k根系统发育树，使每个字符在k是兼容的至少一个树在P是NP-完全的所有k <$3，但可在多项式时间k= 2。这推广了k= 1的结果，其中众所周知是多项式时间。
Given a set R of rooted phylogenetic trees on overlapping taxa, it takes polynomial time to decide whether or not there exists a rooted phylogenetic tree that is compatible with R. Since not all evolutionary histories for a set of species can be explained by a single tree, it is natural to ask for the minimum number of rooted phylogenetic trees needed such that each tree in R is compatible with at least one tree. This paper shows that it is computationally hard to compute this minimum number. In particular, if R contains rooted triples (rooted binary phylogenetic trees on three leaves), it is NP-complete to decide whether there exist two rooted phylogenetic trees such that each rooted triple in R is compatible with at least one of the two trees. Furthermore, for a set Σ of binary characters and a positive integer k, we show that to decide if there exists a set P of k rooted phylogenetic trees such that each character in Σ is compatible with at least one tree in P is NP-complete for all k⩾ 3, but solvable in polynomial time for k= 2. This generalizes the result for k= 1, where it is well-known to be polynomial time.