Haplotyping populations by pure parsimony based on compatible genotypes and greedy heuristics

I. Lin Wang, Hui E. Yang

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


The population haplotype inference problem based on the pure parsimony criterion (HIPP) infers an m × n genotype matrix for a population by a 2m × n haplotype matrix with the minimum number of distinct haplotypes. Previous integer programming based HIPP solution methods are time-consuming, and their practical effectiveness remains unevaluated. On the other hand, previous heuristic HIPP algorithms are efficient, but their theoretical effectiveness in terms of optimality gaps has not been evaluated, either. We propose two new heuristic HIPP algorithms (MGP and GHI) and conduct more complete computational experiments. In particular, MGP exploits the compatible relations among genotypes to solve a reduced integer linear programming problem so that a solution of good quality can be obtained very quickly; GHI exploits a weight mechanism to selects better candidate haplotypes in a greedy fashion. The computational results show that our proposed algorithms are efficient and effective, especially for solving cases with larger recombination rates.

Original languageEnglish
Pages (from-to)9798-9809
Number of pages12
JournalApplied Mathematics and Computation
Issue number23
Publication statusPublished - 2011 Aug 1

All Science Journal Classification (ASJC) codes

  • Computational Mathematics
  • Applied Mathematics


Dive into the research topics of 'Haplotyping populations by pure parsimony based on compatible genotypes and greedy heuristics'. Together they form a unique fingerprint.

Cite this