An optimal algorithm for perfect phylogeny haplotyping

    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