Title

An optimal algorithm for perfect phylogeny haplotyping

Authors

Authors

R. Vijayasatya;A. Mukherjee

Comments

Authors: contact us about adding a copy of your work at STARS@ucf.edu

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

WOS:000238488000004

ISSN

1066-5277

Share

COinS