Ran Libeskind-Hadas and
Michael A. Charleston. On the Computational Complexity of the Reticulate Cophylogeny Reconstruction Problem. In JCB, Vol. 16(1):105-117, 2009. Keywords: cophylogeny, heuristic, NP complete, parsimony, phylogenetic network, reconstruction. Note: http://dx.doi.org/10.1089/cmb.2008.0084.
Toggle 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. © Mary Ann Liebert, Inc. 2009."
|