Bork Daniel, Cheng Ricson, Wang Jincheng, Sung Jean, Libeskind-Hadas Ran
Department of Computer Science, Harvey Mudd College, Claremont, USA.
School of Medicine, University of Pittsburgh, Pittsburgh, USA.
Algorithms Mol Biol. 2017 Mar 14;12:6. doi: 10.1186/s13015-017-0098-8. eCollection 2017.
Phylogenetic tree reconciliation is a widely-used method for inferring the evolutionary histories of genes and species. In the duplication-loss-coalescence (DLC) model, we seek a reconciliation that explains the incongruence between a gene and species tree using gene duplication, loss, and deep coalescence events. In the maximum parsimony framework, costs are associated with these event types and a reconciliation is sought that minimizes the total cost of the events required to map the gene tree onto the species tree.
We show that this problem is NP-hard even for the special case of minimizing the number of duplications. We then show that the problem is APX-hard when both duplications and losses are considered, implying that no polynomial-time approximation scheme can exist for the problem unless P = NP.
These intractability results are likely to guide future research on algorithmic aspects of the DLC-reconciliation problem.
系统发育树调和是一种广泛用于推断基因和物种进化历史的方法。在复制-丢失-合并（DLC）模型中，我们寻求一种调和，通过基因复制、丢失和深度合并事件来解释基因树和物种树之间的不一致。在最大简约框架下，成本与这些事件类型相关联，并寻求一种调和，以使将基因树映射到物种树上所需的事件总成本最小化。
我们表明，即使对于最小化复制数量的特殊情况，该问题也是NP难的。然后我们表明，当同时考虑复制和丢失时，该问题是APX难的，这意味着除非P = NP，否则该问题不存在多项式时间近似方案。
这些难解性结果可能会指导未来关于DLC调和问题算法方面的研究。
