基于加权粒子群算法的单体型装配问题

杨英杰

（铜仁学院数学与计算机科学系，554300）

基于加权粒子群算法的单体型装配问题

杨英杰

（铜仁学院数学与计算机科学系，554300）

针对单体型装配问题的特点，提出一种求解该问题的加权粒子群算法。通过对DALY数据库ID13进行测试，表明算法有效性。同时，与基础粒子群算法和遗传算法进行比较，表明我们所设计的算法在单体型重构率上优于两者。

粒子群算法；单体型装配；遗传算法

0 引言

单体型是指位于一条染色体上或某一区域的一组相关联的SNP等位基因。由于实验条件下获得单体型数据非常困难，也非常昂贵，由此衍生了单体型装配问题。目前单体型装配问题的主要方法有clark算法，分支定界算法，动态聚类算法，遗传算法等。

粒子群算法最早是由心理学研究学者Kennedy博士和Eberhart博士提出来的一种智能算法。本文是粒子群算法在单体型装配问题上的一个很好的应用。

1 求单体型装配问题的加权粒子群算法

1.1 相关定义

定义1 假设由测序试验得到了一对同源染色体DNA上含有n个SNP位点的区域上的m个排列好的SNP片段。为了计算方便，我们用1来表示正常型等位基因；用-1来表示变异型等位基因；0表示信息丢失或没测出的基因，称为间隙。那么，排列好的片段就可以构成上的一个阶SNP矩阵。

定义4 粒子编码：m个SNP片段的一个分类就是一个粒子，每个粒子实际上就是一个m维二进制串。

1.2 适应度函数

我们采用最少错误纠正模型，需定义误差函数：对m个片段的一个划分，确定两条单体，从而有。最优划分的错误纠正次数最少，最多的错误纠正次数为mn，故适应度函数为

1.3 算法流程

3）更新粒子的速度和位置

4）若迭代次数大于G，终止，否则，转向2。

2 实验结果与分析

2.1 ID13的重构率

给ID13单体型产生12个例子，每个例子的SNP片段分别根据以下参数随机产生：片段个数m=40，即将每对单体型拷贝20份;片段间隙率g：0.25,0.5,0.75; 错误率e:0.1,0.2,0.3,0.4。对每个例子执行10次，10次执行结果的平均值列在图1中。

图1 加权粒子群算法在ID13上的重构率

图2 加权粒子群算法，基础粒子群算法，遗传算法在ID13上的重构率

由图1可以看出，当片段的错误率和片段间隙率较低时，ID13重构出的单体型重构率在百分之九十以上，与真实的单体型几乎一致。当片段错误率和片段间隙率较高时，错误率较高。但是，实验表明，一般情况下，我们获取的基因组数据信息的错误率和间隙率都不太大（一般情况下g<0.5,e<0.2）。因此，我们设计的加权粒子群算法具有实际意义。

2.2 加权粒子群算法(MPSO)，基础粒子群算法(PSO)，遗传算法(GA)的比较

为了检验本文算法的优越性，与基础粒子群算法，遗传算法进行了比较，检验实例选择ID13，实验实验数据按照3.1方式获取，实验结果如下。

由图2可以看出，加权粒子群算法的重构率优于遗传算法和基础粒子群算法，特别是对于遗传算法（种群数400，迭代次数150次），算法优越性体现的更好，值得推广。

3 结束语

本文根据单体型装配问题的特点，提出来一种适合求解单体型装配问题的加权粒子群算法。通过对真实数据ID13进行测验，说明了该算法的有效性，同时与遗传算法，基础粒子群算法进行比较，发现本文设计的加权粒子群算法重构率更高，算法性能更优。

[1] Daly M,Rioux J,Hudson T et al.High-resolution haplotype structure in human genome[J].Nature Genetics,2001,29(2): 229-232.

[2] Weiyi Qian et al ,Particle swarm optimization for SNP haplotype reconstruction problem,[J],Applied Mathematics and Computation,2008,196:266-272.

[3] Rui-Sheng Wang et al.Haplotype construction from SNP fragments by minimum error correction[J]. Oxford University Press,2005,21(10):2456-2462.

Weighed Particle Swarm Optimization for Haplotype Reconstruction Problem

Yang Yingjie
(Department of mathematics and computer,tongren university,tongren,554300,China)

A weighed swarm optimization is proposed based on haplotype reconstruction problem’s characteristics.The algorithm presented is implemented on both ID13 and is compared with basic swarm optimization and the genetic algorithm.The comparative results indicate that the proposed optimization has much higher accuracy.

particle swarm optimization;haplotype reconstruction;genetic algorithm

TP311

杨英杰（1982-），女，硕士，讲师，主要研究方向：最优化方法，生物信息学,控制论。

贵州省科技厅项目（黔科合J字LKT[2012]24号），铜仁学院自然科学基金(TS10018)