HMC: Haplotype inference tool based on Markov Chain model

• Latest version: 0.09.001
• Last updated: September 1, 2009

References#

• Ji-Hong Zhang, Ling-Yun Wu and Xiang-Sun Zhang. A new statistical method for haplotype inference from genotype data. In Proceedings of IASTED International Conference on Computational and Systems Biology (CASB 2006), pp. 7-12, ACTA Press, 2006.
• Ji-Hong Zhang, Ling-Yun Wu, Jian Chen, and Xiang-Sun Zhang. A fast haplotype inference method for large population genotype data. Computational Statistics and Data Analysis, Vol. 52, No. 11, pp. 4891-4902, 2008.
• Ling-Yun Wu, Ji-Hong Zhang, and Raymond Chan. Improved approach for haplotype inference based on Markov chain. In Proceedings of 2nd International Symposium on Optimization and Systems Biology, Lecture Notes in Operations Research, Vol. 9, pp. 204–215, World Publishing Corporation, Beijing, 2008.

Method#

Reconstruction of haplotypes from genotype data is a crucial step in related haplotype studies. In this paper, a new haplotype inference method based on Markov chain model for population-based haplotype reconstruction is proposed. The haplotype inference methods based on Markov chain model do not assume haplotype blocks in the population and allows each individual haplotype to have its own structure, thus are able to accommodate recombination and obtain higher adaptivity to the genotype data, specifically in the case of long marker maps. The proposed method presents a general Markov chain model for haplotype inference problem. A dynamic programming algorithm is developed for the model. The algorithm is theoretically guaranteed to find exact global optimal solutions within polynomial running time. Through extensive computational experiments on simulated and real genotype data, the designed algorithm is shown to be efficient, and outperforms previous methods.

Software#

This version of the program is in very preliminary stage and provided just for testing purpose. The program is still under development.

HMC 0.4#

• HMC-0.4.1.zip
• Data.zip
• References
  • Ji-Hong Zhang, Ling-Yun Wu and Xiang-Sun Zhang. A new statistical method for haplotype inference from genotype data. In Proceedings of IASTED International Conference on Computational and Systems Biology (CASB 2006), pp. 7-12, ACTA Press, 2006.

HMC 0.8#

• HMC-0.8.3.zip
• References
  • Ji-Hong Zhang, Ling-Yun Wu, Jian Chen, and Xiang-Sun Zhang. A fast haplotype inference method for large population genotype data. Computational Statistics and Data Analysis, Vol. 52, No. 11, pp. 4891-4902, 2008.

HMC 0.9#

• HMC-0.9.1.zip
• References
  • Ling-Yun Wu, Ji-Hong Zhang, and Raymond Chan. Improved approach for haplotype inference based on Markov chain. In Proceedings of 2nd International Symposium on Optimization and Systems Biology, Lecture Notes in Operations Research, Vol. 9, pp. 204–215, World Publishing Corporation, Beijing, 2008.