On the computational complexity of the reticulate cophylogeny reconstruction problem.
The cophylogeny reconstruction problem is that of finding minimal cost explanations of differences between evolutionary histories of ecologically linked groups of biological organisms. We present a proof that shows that the general problem of reconciling evolutionary histories is NP-complete and provide a sharp boundary where this intractability begins. We also show that a related problem, that of finding Pareto optimal solutions, is NP-hard. As a byproduct of our results, we give a framework by which meta-heuristics can be applied to find good solutions to this problem.
Libeskind-Hadas
Ran
R
Department of Computer Science, Harvey Mudd College, Claremont, California 91711, USA. hadas@cs.hmc.edu
Charleston
Michael A
MA
D000465:Algorithms; D005075:Biological Evolution; D019295:Computational Biology / Q000379:methods*; D008962:Models, Theoretical; D010802:Phylogeny; D013997:Time Factors