A Fast and Accurate Reconstruction Algorithm for     Individual Haplotype

doi:10.3969/j.issn.1000-3428.2013.09.050

Abstract

Abstract: A heuristic algorithm for haplotype reconstrucion, named H-MEC, is proposed based on the Minimum Error Correction(MEC) model. H-MEC reconstructs the columns of a pair of haplotypes one by one. It partitions the Single Nucleotide Polymorphisms(SNP) fragments that cover some SNP site into two sets according to the values of the corresponding SNP site, and reconstructs haplotypes by using the fragments of the set which contains more fragments. The experiments are conducted by using the haplotypes on the chromosomes 1 of 60 individuals in the CEPH sample, which are released by the international HapMap project. Experimental results indicate that under various parameter settings, H-MEC can obtain higher reconstruction rate than Fast Hare algorithm and DGS algorithm. Moreover, H-MEC still has high efficiency even for reconstructing long haplotypes.

Key words: Single Nucleotide Polymorphisms(SNP), haplotype, Minimum Error Correction(MEC), heuristic, reconstruction

摘要： 在最少错误更正模型的基础上，提出一种重建单体型的启发式算法H-MEC。按照单体型的单核苷酸多态性(SNP)位点顺序依次构建算法步骤，根据某SNP位点取值将覆盖该SNP位点的片段划分为2个集合，利用包含片段数较多集合中的片段进行重建。使用HapMap计划发布的CEPH样本中的60个个体，在1号染色体的单体型上进行实验。结果表明，H-MEC算法在各种参数设置下，能获得较Fast Hare算法和DGS算法更高的单体型重建率。此外，该算法在重建长单体型时也具有较高的执行效率。

关键词: 单核苷酸多态性, 单体型, 最少错误更正, 启发式, 重建

CLC Number:

TP301.6

WU Jing-li, LIANG Bin-bin, LI Zhi-xin, WANG Hua. A Fast and Accurate Reconstruction Algorithm for Individual Haplotype[J]. Computer Engineering, doi: 10.3969/j.issn.1000-3428.2013.09.050.

吴璟莉，梁彬彬，李志欣，王华. 一种快速精确的个体单体型重建算法[J]. 计算机工程, doi: 10.3969/j.issn.1000-3428.2013.09.050.

/ / Recommend / Download Citations

URL: http://www.ecice06.com/EN/10.3969/j.issn.1000-3428.2013.09.050

http://www.ecice06.com/EN/Y2013/V39/I9/222

References

[1] Botstein D, Risch N. Discovering Genotypes Underlying Human Phenotypes: Past Successes for Mendelian Disease, Future Approaches for Complex Disease[J]. Nature Genetics, 2003, 33(Sl): 228-237. [2] Clark A G. Inference of Haplotypes from PCR-amplified Samples of Diploid Populations[J]. Molecular Biology and Evolution, 1990, 7(2): 111-122. [3] O’Neil S T, Emrich S J. Haplotype and Minimum-chimerism Consensus Determination Using Short Sequence Data[J]. BMC Genomics, 2012, 13(S2). [4] Lancia G, Bafna V, Istrail S, et al. SNPs Problems, Complexity and Algorithms[C]//Proc. of the 9th Annual European Symposium on Algorithms. Aarhus, Denmark: Springer, 2001. [5] Lippert R, Schwartza R, Lancia G, et al. Algorithmic Strategies for the SNPs Haplotype Assembly Problem[J]. Briefings in Bioinformatics, 2002, 3(1): 23-31. [6] Rizzi R, Bafna V, Istrail S, et al. Practical Algorithms and Fixed-parameter Tractability for the Single Individual SNP Haplotyping Problem[C]//Proc. of the 2nd International Workshop on Algorithms in Bioinformatics. Rome, Italy: Springer, 2002. [7] Xie Minzhu, Chen Jian’er, Wang Jianxin. Research on Parameterized Algorithms of the Individual Haplotyping Problem[J]. Journal of Bioinformatics and Computational Biology, 2007, 5(3): 795-816. [8] Cilibrasi R, van Iersel L, Kelk S, et al. The Complexity of the Single Individual SNP Haplotyping Problem[J]. Algorithmica, 2007, 49(1): 13-36. [9] Wang Ruisheng, Wu Lingyun, Li Zhenping, et al. Haplotype Reconstruction from SNP Fragments by Minimum Error Correction[J]. Bioinformatics, 2005, 21(10): 2456-2462. [10] He Dan, Choi A, Pipatsrisawat K, et al. Optimal Algorithms for Haplotype Assembly from Whole-genome Sequence Data[J]. Bioinformatics, 2010, 26(12): 183-190. [11] Panconesi A, Sozio M. Fast Hare: A Fast Heuristic for Single Individual SNP Haplotype Reconstruction[C]//Proc. of Workshop on Algorithms in Bioinformatics. Bergen, Norway: Springer, 2004. [12] Zhao Yuying, Wu Lingyun, Zhang Jihong, et al. Haplotype Assembly from Aligned Weighted SNP Fragments[J]. Journal of Computational Biology and Chemistry, 2005, 29(4): 281-287. [13] Wang Ying, Feng Enmin, Wang Ruisheng. A Clustering Algorithm Based on Two Distance Functions for MEC Model[J]. Journal of Computational Biology and Chemistry, 2007, 31(2): 148-150. [14] Genovese L M, Geraci F, Pellegrini M. SpeedHap: An Accurate Heuristic for the Single Individual SNP Haplotyping Problem with Many Gaps, High Reading Error Rate and Low Coverage[J]. IEEE/ACM Trans. on Computational Biology and Bioinformatics, 2008, 5(4): 492-502. [15] Levy S, Sutton G, Ng P C, et al. The Diploid Genome Sequence of an Individual Human[J]. PLoS Biology, 2007, 5(10): 2113-2144. [16] Bansal V, Bafna V. HapCUT: An Efficient and Accurate Algorithm for the Haplotype Assembly Problem[J]. Bioinformatics, 2008, 24(16): 153-159. [17] Chen Zhixiang, Fu Bin, Schweller R, et al. Linear Time Probabilistic Algorithms for the Singular Haplotype Reconstruction Problem from SNP Fragments[J]. Journal of Computational Biology, 2008, 15(5): 535-546. [18] Geraci F. A Comparison of Several Algorithms for the Single Individual SNP Haplotyping Reconstruction Problem[J]. Bioinformatics, 2010, 26(18): 2217-2225. [19] 吴璟莉, 陈建二, 王建新. 一种基于最少片段删除模型重建单体型的粒子群优化算法[J]. 高技术通讯, 2009, 19(2): 194-199. [20] 吴璟莉. 遗传多态性检测中组合优化问题的研究[D]. 长沙: 中南大学, 2008. [21] Consortium T I H. The International HapMap Project[J]. Nature, 2003, 426(6968): 789-796. [22] Myers G. A Dataset Generator for Whole Genome Shotgun Sequencing[C]//Proc. of the 7th International Conference on Intelligent Systems for Molecular Biology. Heidelberg, Germany: AAAI Press, 1999. 编辑顾逸斐

Please choose a citation manager

Content to export