Mathematical properties and bounds on haplotyping populations by pure parsimony

I. Lin Wang, Chia Yuan Chang

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


Although the haplotype data can be used to analyze the function of DNA, due to the significant efforts required in collecting the haplotype data, usually the genotype data is collected and then the population haplotype inference (PHI) problem is solved to infer haplotype data from genotype data for a population. This paper investigates the PHI problem based on the pure parsimony criterion (HIPP), which seeks the minimum number of distinct haplotypes to infer a given genotype data. We analyze the mathematical structure and properties for the HIPP problem, propose techniques to reduce the given genotype data into an equivalent one of much smaller size, and analyze the relations of genotype data using a compatible graph. Based on the mathematical properties in the compatible graph, we propose a maximal clique heuristic to obtain an upper bound, and a new polynomial-sized integer linear programming formulation to obtain a lower bound for the HIPP problem.

Original languageEnglish
Pages (from-to)120-125
Number of pages6
JournalMathematical Biosciences
Issue number2
Publication statusPublished - 2011 Jun

All Science Journal Classification (ASJC) codes

  • Statistics and Probability
  • Modelling and Simulation
  • Biochemistry, Genetics and Molecular Biology(all)
  • Immunology and Microbiology(all)
  • Agricultural and Biological Sciences(all)
  • Applied Mathematics


Dive into the research topics of 'Mathematical properties and bounds on haplotyping populations by pure parsimony'. Together they form a unique fingerprint.

Cite this