Who is Who in Phylogenetic Networks

Publication no #682   Type :   Html | Bib | Both

Created: 2009-01-06 00:41:25     Modified: 2009-01-06 00:48:39

682 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." @Article{LiebeskindCharleston2009,       AUTHOR = {Libeskind-Hadas, Ran and Charleston, Michael A.},       TITLE = {On the Computational Complexity of the Reticulate Cophylogeny Reconstruction Problem},       YEAR = {2009},       JOURNAL = {JCB},       VOLUME = {16},       NUMBER = {1},       PAGES = {105-117},       URL = {http://dx.doi.org/10.1089/cmb.2008.0084},       NOTE = {http://dx.doi.org/10.1089/cmb.2008.0084},       ANNOTE = {BIBUPDATE : 20090105},       KEYWORDS = {cophylogeny, heuristic, NP complete, parsimony, phylogenetic network, reconstruction} }