CAJ | 학술논문

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