| The undirected incomplete perfect phylogeny problem. | |
| | |
MedLine Citation:
|
PMID: 18989047 Owner: NLM Status: MEDLINE |
Abstract/OtherAbstract:
|
The incomplete perfect phylogeny (IPP) problem and the incomplete perfect phylogeny haplotyping (IPPH) problem deal with constructing a phylogeny for a given set of haplotypes or genotypes with missing entries. The earlier approaches for both of these problems dealt with restricted versions of the problems, where the root is either available or can be trivially re-constructed from the data, or certain assumptions were made about the data. In this paper, we deal with the unrestricted versions of the problems, where the root of the phylogeny is neither available nor trivially recoverable from the data. Both IPP and IPPH problems have previously been proven to be NP-complete. Here, we present efficient enumerative algorithms that can handle practical instances of the problem. Empirical analysis on simulated data shows that the algorithms perform very well both in terms of speed and in terms accuracy of the recovered data. |
| | |
Authors:
|
Ravi Vijaya Satya; Amar Mukherjee |
Related Documents
:
|
14607467 - Extensions to minimum relative entropy inversion for noisy data. 8790627 - Implementation of the three-dimensional-pattern search problem on hopfield-like neural ... 3602167 - External approach for secondary rhinoplasty. 19568217 - Use of an adapted problem-based learning approach to aid the development of clinical au... 2234707 - Observer variability in the scoring of colpophotographs. 13383367 - Endemic goitre and its prevention in hungary. |
Publication Detail:
|
Type: Journal Article; Research Support, U.S. Gov't, Non-P.H.S. |
Journal Detail:
|
Title: IEEE/ACM transactions on computational biology and bioinformatics / IEEE, ACM Volume: 5 ISSN: 1557-9964 ISO Abbreviation: IEEE/ACM Trans Comput Biol Bioinform Publication Date: 2008 Oct-Dec |
Date Detail:
|
Created Date: 2008-11-07 Completed Date: 2009-01-30 Revised Date: - |
Medline Journal Info:
|
Nlm Unique ID: 101196755 Medline TA: IEEE/ACM Trans Comput Biol Bioinform Country: United States |
Other Details:
|
Languages: eng Pagination: 618-29 Citation Subset: IM |
Affiliation:
|
School of Electrical Engineering and Computer Science, University of Central Florida, 4000 Central Florida Blvd., Orlando, FL 32816., USA. ravi.vijayasatya@gmail.com |
Export Citation:
|
APA/MLA Format Download EndNote Download BibTex |
| MeSH Terms | |
Descriptor/Qualifier:
|
Algorithms* Chromosome Mapping / methods* Evolution* Evolution, Molecular* Haplotypes / genetics* Phylogeny* Polymorphism, Single Nucleotide / genetics* Sequence Analysis, DNA / methods* |
From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine
Previous Document: An introduction to metabolic networks and their structural analysis.
Next Document: Optimization of cDNA microarray experimental designs using an evolutionary algorithm.