| Extensions and Improvements to the Chordal Graph Approach to the Multi-State Perfect Phylogeny Problem. | |
| | |
MedLine Citation:
|
PMID: 21301033 Owner: NLM Status: Publisher |
Abstract/OtherAbstract:
|
The multi-state perfect phylogeny problem is a classic problem in computational biology. When no perfect phylogeny exists, it is of interest to find a set of characters to remove in order to obtain a perfect phylogeny in the remaining data. This is known as the character removal problem. We show how to use chordal graphs and triangulations to solve the character removal problem for an arbitrary number of states, which was previously unsolved. We outline a preprocessing technique that speeds up the computation of the minimal separators of a graph. Minimal separators are used in our solution to the missing data character removal problem and to Gusfield's solution of the perfect phylogeny problem with missing data. |
| | |
Authors:
|
Rob Gysel; Daniel Gusfield |
Related Documents
:
|
21405383 - Does adiabatic quantum optimization fail for np-complete problems? 6810993 - Mortality from asthma: a new epidemic in new zealand. 19822633 - An anatomic study of flexor tendon sheaths: a cadaveric study. |
Publication Detail:
|
Type: JOURNAL ARTICLE Date: 2011-2-3 |
Journal Detail:
|
Title: IEEE/ACM transactions on computational biology and bioinformatics / IEEE, ACM Volume: - ISSN: 1557-9964 ISO Abbreviation: - Publication Date: 2011 Feb |
Date Detail:
|
Created Date: 2011-2-8 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:
|
UC Davis, Davis. |
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: Uncovering Hidden Phylogenetic Consensus in Large Datasets.
Next Document: CARASIL.