Document Type
Article
Department
Computer Science (HMC)
Publication Date
2009
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.
Rights Information
© 2009 Mary Ann Liebert, Inc.
DOI
10.1089/cmb.2008.0084
Recommended Citation
R. Libeskind-Hadas and M. Charleston, “On the Computational Complexity of the Reticulate Cophylogeny Reconstruction Problem,” Journal of Computational Biology, Vol. 16, No. 1, January 2009, pp. 105-117. DOI: 10.1089/cmb.2008.0084
