| The co phylogeny reconstruction problem is NP-complete. | |
| | |
MedLine Citation:
|
PMID: 20715926 Owner: NLM Status: In-Process |
Abstract/OtherAbstract:
|
The co phylogeny reconstruction problem is that of finding minimum cost explanations of differences between historical associations. The problem arises in parasitology, molecular systematics, and biogeography. Existing software tools for this problem either have worst-case exponential time or use heuristics that do not guarantee optimal solutions. To date, no polynomial time optimal algorithms have been found for this problem. In this article, we prove that the problem is NP-complete, suggesting that future research on algorithms for this problem should seek better polynomial-time approximation algorithms and heuristics rather than optimal solutions. |
| | |
Authors:
|
Y Ovadia; D Fielder; C Conow; R Libeskind-Hadas |
Related Documents
:
|
19566336 - Selection of regularization parameter for optical topography. 18255876 - String taxonomy using learning automata. 21739136 - Domestic dogs (canis familiaris) flexibly adjust their human-directed behavior to the a... 15700406 - A note on efficient computation of haplotypes via perfect phylogeny. 3816706 - Psychosocial sequelae of epilepsy: the role of associated cerebral pathology. 15327346 - The relationship of entrepreneurial traits, skill, and motivation to subsequent venture... |
Publication Detail:
|
Type: Journal Article; Research Support, Non-U.S. Gov't Date: 2010-08-17 |
Journal Detail:
|
Title: Journal of computational biology : a journal of computational molecular cell biology Volume: 18 ISSN: 1557-8666 ISO Abbreviation: J. Comput. Biol. Publication Date: 2011 Jan |
Date Detail:
|
Created Date: 2011-01-07 Completed Date: - Revised Date: - |
Medline Journal Info:
|
Nlm Unique ID: 9433358 Medline TA: J Comput Biol Country: United States |
Other Details:
|
Languages: eng Pagination: 59-65 Citation Subset: IM |
Affiliation:
|
Department of Computer Science, Harvey Mudd College, Claremont, California 91711, USA. |
Export Citation:
|
APA/MLA Format Download EndNote Download BibTex |
| MeSH Terms | |
Descriptor/Qualifier:
|
|
From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine
Previous Document: Quality of care for patients infected with HIV.
Next Document: Kaposi sarcoma (KS)-associated herpesvirus microRNA sequence analysis and KS risk in a European AIDS...