Title
An optimal algorithm for perfect phylogeny haplotyping
Abbreviated Journal Title
J. Comput. Biol.
Keywords
perfect phylogeny; haplotype inference; coalescence; parsimony; HapMap; DIPLOID POPULATIONS; HUMAN GENOME; INFERENCE; RECOMBINATION; SAMPLES; Biochemical Research Methods; Biotechnology & Applied Microbiology; Computer Science, Interdisciplinary Applications; Mathematical &; Computational Biology; Statistics & Probability
Abstract
Inferring haplotype data from genotype data is a crucial step in linking SNPs to human diseases. Given n genotypes over m SNP sites, the haplotype inference (HI) problem deals with finding a set of haplotypes so that each given genotype can be formed by a combining a pair of haplotypes from the set. The perfect phylogeny haplotyping (PPH) problem is one of the many computational approaches to the HI problem. Though it was conjectured that the complexity of the PPH problem was O(nm), the complexity of all the solutions presented until recently was O(nm(2)). In this paper, we make complete use of the column-ordering that was presented earlier and show that there must be some interdependencies among the pairwise relationships between SNP sites in order for the given genotypes to allow a perfect phylogeny. Based on these interdependencies, we introduce the FlexTree (flexible tree) data structure that represents all the pairwise relationships in O(m) space. The FlexTree data structure provides a compact representation of all the perfect phylogenies for the given set of genotypes. We also introduce an ordering of the genotypes that allows the genotypes to be added to the FlexTree sequentially. The column ordering, the FlexTree data structure, and the row ordering we introduce make the O(nm) OPPH algorithm possible. We present some results on simulated data which demonstrate that the OPPH algorithm performs quiet impressively when compared to the previous algorithms. The OPPH algorithm is one of the first O(nm) algorithms presented for the PPH problem.
Journal Title
Journal of Computational Biology
Volume
13
Issue/Number
4
Publication Date
1-1-2006
Document Type
Article
Language
English
First Page
897
Last Page
928
WOS Identifier
ISSN
1066-5277
Recommended Citation
"An optimal algorithm for perfect phylogeny haplotyping" (2006). Faculty Bibliography 2000s. 6677.
https://stars.library.ucf.edu/facultybib2000/6677
Comments
Authors: contact us about adding a copy of your work at STARS@ucf.edu