Computational Problems in Haplotype Inference
Creators: name: Namjoshi, Parag
Publisher: name: Maryland Shared Open Access Repository
Year: 2009
Subjects: Haplotype Inference
Pure Parsimony

description: The genome of all organisms is partitioned into a fixed number of chromosomes. Mammals, including humans, are diploid, i.e., they have two copies of each autosome (non-sex chromosomes), one inherited from each parent.  Most sites along the autosome of any two individuals from the same species are identical, except for a small number of sites where they are statistically different.  Such variations are due to mutations or crossovers that were introduced at conception (meiosis).  These sites are called Single Nucleotide Polymorphism (SNP) sites.  The sequence of nucleotides that appear at the SNP sites of an autosome of a haplotype.  Similarly, for a given set of homologous autosomes of an individual, the sequence of multisets of nucleotides that appear at each SNP site is the individual's genotype. An individual's genotype can be viewed as the site-wise combination of that individual's haplotypes. The haplotypes are conjectured to be the genetic basis for hereditary diseases such as Alzheimer's, diabetes, and heart diseases. Determining an individual's genotype using molecular methods in the wet--lab is relatively inexpensive. However, determining an individual's haplotypes using molecular methods in the wet--lab is expensive and time consuming. Consequently, developing computational methods for inferring haplotypes from the genotypes of a given set of individuals becomes important.  Since the haplotype inference problem can have multiple solutions, we often seek solutions with as few haplotypes as possible, leading to the Haplotype Inference with Pure Parsimony (HIPP) problem, which is NP-hard. We provide novel algorithms for the HIPP problem and compare their performance with various existing algorithms for this problem. For example, we provide an algorithm, which is based on semidefinite programming, that can incorporate additional constraints to handle many variations of the HIPP problem.  We also provide a novel efficient algorithm for solving certain sparse linear programs, which yields substantial improvements to a well known algorithm for HIPP that is based on integer/linear programming.  Our algorithm routinely solves linear programs, derived from HIPP instances, with about 15,000 constraints and 35,000 variables on a low-cost commodity laptop in under an hours on average using a few MBs of RAM.  Previously, linear programs of such dimensions could not be solved, even on more expensive hardware. Moreover, in disease association or adverse drug reaction studies, in addition to the genotypes, information regarding the presence or absence of a disease or severity of an adverse drug response is available.  The classical HIPP problem does not consider this crucial additional information, consequently yielding solutions which can have a significant number of conflicts with the underlying disease or drug response model, reducing the utility of the inferred haplotypes in such studies.  Considering this additional information gives rise to the trait haplotyping with pure parsimony problem. We provide the first algorithm for this trait haplotype inference problem that finds parsimonious solutions with no conflicts with the underlying trait (disease, drug response, or phenotype) model. Haplotype inference studies for plants have important agricultural and economic implications. Plants are often polyploid organisms, that is they have more than two copies of each autosome. Consequently, haplotype inference for polyploids is an important problem.  We show that haplotype inference for a single polyploid genotype reduces to a minimum cardinality integer partition problem, and it is challenging in itself.  Furthermore, we provide an easily computable lower bound for the HIPP problem for polyploids. We then show that our lower bound is tighter than all of the other lower bounds proposed in the literature, and discuss its applications in the design of algorithms for the HIPP problem for polyploids.