title: On the computational complexity of the reticulate cophylogeny reconstruction problem.
abstract: 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.
authors.affiliation: Department of Computer Science, Harvey Mudd College, Claremont, California 91711, USA. hadas@cs.hmc.edu
authors.forename: Ran
authors.initials: R
authors.lastname: Libeskind-Hadas
authors.forename: Michael A
authors.initials: MA
authors.lastname: Charleston
mesh_terms: D000465:Algorithms; D005075:Biological Evolution; D019295:Computational Biology / Q000379:methods*; D008962:Models, Theoretical; D010802:Phylogeny; D013997:Time Factors