| The Complexity of Finding Multiple Solutions to Betweenness and Quartet Compatibility. | |
| | |
MedLine Citation:
|
PMID: 21788676 Owner: NLM Status: Publisher |
Abstract/OtherAbstract:
|
We show that two important problems that have applications in computational biology are ASP-complete, which implies that, given a solution to a problem, it is NP-complete to decide if another solution exists. We show first that a variation of Betweenness, which is the underlying problem of questions related to radiation hybrid mapping, is ASP-complete. Subsequently, we use that result to show that Quartet Compatibility, a fundamental problem in phylogenetics that asks whether a set of quartets can be represented by a parent tree, is also ASP-complete. The latter result shows that Steel's Quartet Challenge, which asks whether a solution to Quartet Compatibility is unique, is coNP-complete. |
| | |
Authors:
|
Maria Luisa Bonet; Simone Linz; Katherine St John |
Related Documents
:
|
22527246 - Activation-induced cytidine deaminase (aid) linking immunity, chronic inflammation, and... 19040876 - Using a virtual learning environment to address one problem with problem based learning. 14418976 - Analysis of absenteeism in industry. 8208146 - Foundations of problem-based learning: some explanatory notes. 7283066 - Professional singers: the science and art of clinical care. 1447426 - Completed suicide and recent lithium treatment. |
Publication Detail:
|
Type: JOURNAL ARTICLE Date: 2011-7-20 |
Journal Detail:
|
Title: IEEE/ACM transactions on computational biology and bioinformatics / IEEE, ACM Volume: - ISSN: 1557-9964 ISO Abbreviation: - Publication Date: 2011 Jul |
Date Detail:
|
Created Date: 2011-7-26 Completed Date: - Revised Date: - |
Medline Journal Info:
|
Nlm Unique ID: 101196755 Medline TA: IEEE/ACM Trans Comput Biol Bioinform Country: - |
Other Details:
|
Languages: ENG Pagination: - Citation Subset: - |
Affiliation:
|
Universitat Politecnica de Catalunya (UPC), Barcelona. |
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: Smoldyn on Graphics Processing Units: Massively Parallel Brownian Dynamics Simulation.
Next Document: Optimizing Phylogenetic Networks for Circular Split Systems.