一种快速精确的个体单体型重建算法

摘要

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