On the computational complexity of the maximum parsimony reconciliation problem in the duplication-loss-coalescence model.
BACKGROUND
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.


RESULTS
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.


CONCLUSIONS
These intractability results are likely to guide future research on algorithmic aspects of the DLC-reconciliation problem.
Department of Computer Science, Harvey Mudd College, Claremont, USA.|School of Medicine, University of Pittsburgh, Pittsburgh, USA.
Daniel
D
Bork
School of Computer Science, Carnegie Mellon University, Pittsburgh, USA.
Ricson
R
Cheng
Department of Computer Science, Harvey Mudd College, Claremont, USA.
Jincheng
J
Wang
Department of Computer Science, Harvey Mudd College, Claremont, USA.
Jean
J
Sung
Department of Computer Science, Harvey Mudd College, Claremont, USA.
Ran
0000-0001-9120-1948
R
Libeskind-Hadas
APX-hardness; Duplication-loss-coalescence model; NP-hardness; Phylogenetic reconciliation