Computer Science (HMC)
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.
© 2009 Mary Ann Liebert, Inc.
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