一种基于最少片段删除模型重建单体型的粒子群优化算法

A particle swarm optimization algorithm for haplotype reconstruction based on minimum fragment removal model

利用最少片段删除(MFR)模型研究了个体单体型重建的算法。利用单核苷酸多态性(SNP)位点杂合率低的特性,引入了一种短粒子编码方式,提出了一种重建单体型的粒子群优化算法P-MFR。利用国际人类基因组单体型图计划发布的CEPH样本(祖籍是北欧或西欧的美国犹他州人)中60个个体在1号染色体上的单体型进行实验分析,实验结果显示,与以往求解MFR模型的算法相比较,P-MFR算法能够获得更高重建率的单体型。此外,由于采用了较短的粒子位置编码方式,P-MFR算法在重建长单体型时仍具有较高的执行效率,有很好的实用价值。

The individual haplotype reconstruction problem was studied by using the minimum fragment removal （MFR）model. Owing to the NP-hardness of the MFR model, a practical algorithm based on particle swarm optimization （PSO） for haplotype reconstruction, named P-MFR, was presented. A kind of short particle code was designed for the P-MFR by taking advantage of the low heterozygous frequencies of single nucleotide polymorphisms （SNPs）. The experiments were conducted by using the haplotypes on the chromosomes 1 of 60 individuals in the CEPH sample, which were released by the International HapMap Project. The results indicate that P-MFR can obtain higher reconstruction rate than previous algorithms when solving the MFR model. Moreover, this kind of short particle code makes P-MFR efficient even for reconstructing long haplotypes.