Submit Manuscript  

Article Details

Computational Models and Algorithms for the Single Individual Haplotyping Problem

[ Vol. 5 , Issue. 1 ]


Minzhu Xie, Jianxin Wang, Jianer Chen, Jingli Wu and Xucong Liu   Pages 18 - 28 ( 11 )


Single nucleotide polymorphism (SNP) is the predominant form of human genetic variation, and is widely used in disease association studies. Haplotype, i.e. a sequence of SNPs on a chromosome, can provide more information than single SNPs. Haplotype-based analysis is more powerful in complex disease association studies than SNP-based methods. However, it is much difficult to determine haplotypes using only biological experiments. Single individual haplotyping uses computational techniques to infer the haplotypes of an individual from his or her DNA sequence fragments. As more and more individual genomes have been sequenced, the single individual haplotyping problem has been a hotspot of bioinformatics. This paper reviews the computational models and algorithms for the problem, and discusses directions for future research.


SNP, single individual haplotyping, computational model, exact algorithm, parameterized algorithm, heuristic algorithm


School of Information Science and Engineering, Central South University, ChangSha, 410083, Hu- Nan, China.

Read Full-Text article