| On the computational complexity of the reticulate cophylogeny reconstruction problem. | |
| | |
MedLine Citation:
|
PMID: 19119995 Owner: NLM Status: MEDLINE |
Abstract/OtherAbstract:
|
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:
|
Ran Libeskind-Hadas; Michael A Charleston |
Related Documents
:
|
3621235 - Synthesis and n.m.r.-spectral analysis of unenriched and [1-13c]-enriched 5-deoxypentos... 22213885 - Rendering justice in witch trials: the case of the val de lièpvre. 12935215 - Reduction of the sign problem using the meron-cluster approach. 2303775 - Mental arithmetic: effects of calculation procedure and problem difficulty on solution ... 10976595 - The development of concern for others in children with behavior problems. 1144555 - Needle aspiration of the flexor digital sheath as an aid in diagnosing tenosynovitis. |
Publication Detail:
|
Type: Journal Article; Research Support, Non-U.S. Gov't |
Journal Detail:
|
Title: Journal of computational biology : a journal of computational molecular cell biology Volume: 16 ISSN: 1557-8666 ISO Abbreviation: J. Comput. Biol. Publication Date: 2009 Jan |
Date Detail:
|
Created Date: 2009-01-05 Completed Date: 2009-02-09 Revised Date: - |
Medline Journal Info:
|
Nlm Unique ID: 9433358 Medline TA: J Comput Biol Country: United States |
Other Details:
|
Languages: eng Pagination: 105-17 Citation Subset: IM |
Affiliation:
|
Department of Computer Science, Harvey Mudd College, Claremont, California 91711, USA. hadas@cs.hmc.edu |
Export Citation:
|
APA/MLA Format Download EndNote Download BibTex |
| MeSH Terms | |
Descriptor/Qualifier:
|
Algorithms Computational Biology / methods* Evolution* Models, Theoretical Phylogeny* Time Factors |
From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine
Previous Document: Extended HP model for protein structure prediction.
Next Document: Boolean network approach to negative feedback loops of the p53 pathways: synchronized dynamics and s...