Current Bioinformatics

Yi-Ping Phoebe Chen
Department of Computer Science and Information Technology
La Trobe University


Computational Models and Algorithms for the Single Individual Haplotyping Problem

Author(s): Minzhu Xie, Jianxin Wang, Jianer Chen, Jingli Wu, Xucong Liu.


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.

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

Order Reprints Order Eprints Rights & PermissionsPrintExport

Article Details

Year: 2010
Page: [18 - 28]
Pages: 11
DOI: 10.2174/157489310790596411