Title

An Optimal Algorithm For Perfect Phylogeny Haplotyping

Keywords

Coalescence; Haplotype inference; HapMap; Parsimony; Perfect phylogeny

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(nm2). 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. © Mary Ann Liebert, Inc.

Publication Date

5-1-2006

Publication Title

Journal of Computational Biology

Volume

13

Issue

4

Number of Pages

897-928

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1089/cmb.2006.13.897

Socpus ID

33745289568 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/33745289568

This document is currently not available here.

Share

COinS