Identifying Rogue Taxa through Reduced Consensus: NP-Hardness and Exact Algorithms
Identifying Rogue Taxa through Reduced Consensus: NP-Hardness and Exact Algorithms
复制标题
通过简化共识识别流氓分类群：NP 难度和精确算法
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
David Fernández
中科院分区：
文献类型：
--
作者：
A. Deepak;Jianrong Dong;David Fernández
在系统发育树的集合中，流氓分类群是指其位置在不同的树之间变化很大的分类群。这样的分类群的存在可以极大地降低集合的共识树的分辨率（例如多数规则或严格共识）。减少共识方法旨在识别和消除流氓分类群，以产生更多信息的共识树。给定相同叶集上的系统发育树集合，目标是找到一组分类群，其移除使集合的一致树中的内边数量最大化。我们证明了这个问题对于严格的多数决共识是np困难的。给出了原树严格一致性最大度有界时严格一致性简化的多项式时间算法。我们描述了精确整数线性规划公式，用于计算简化的严格共识树、多数共识树和松散共识树。在实验测试中，我们的精确解在几个问题实例上优于启发式方法。
A rogue taxon in a collection of phylogenetic trees is one whose position varies drastically from tree to tree. The presence of such taxa can greatly reduce the resolution of the consensus tree (e.g., the majority-rule or strict consensus) for a collection. The reduced consensus approach aims to identify and eliminate rogue taxa to produce more informative consensus trees. Given a collection of phylogenetic trees over the same leaf set, the goal is to find a set of taxa whose removal maximizes the number of internal edges in the consensus tree of the collection. We show that this problem is NP-hard for strict and majority-rule consensus. We give a polynomial-time algorithm for reduced strict consensus when the maximum degree of the strict consensus of the original trees is bounded. We describe exact integer linear programming formulations for computing reduced strict, majority and loose consensus trees. In experimental tests, our exact solutions improved over heuristic methods on several problem instances.
影响因子：
6.5
作者：
Cranston, Karen A.;Rannala, Bruce
通讯作者：
Rannala, Bruce