多序列比对问题的概率统计粒子群算法求解

Particle Swarm Optimization with Probability Statistic for Biological Multiple Sequence Alignment

多序列比对问题是生物信息学的热点研究问题.针对大规模多序列比对精度低问题,提出基于概率统计自适应粒子群的生物多序列比对算法.根据优质解的分布概率建立模型用于引导粒子产生新解,使种群中的粒子具有更全面的学习能力,从而提高比对结果的精度;引入适应度方差、期望最优解和变异操作跳出早熟状态,避免算法陷入局部最优值.对BALIBASE中142个例子进行仿真,实验结果验证了算法的可行性和有效性,与已有的算法相比,该算法对大规模亲缘较近长序列比对问题具有更强的求解能力.

Multiple sequence alignment is a researched hotspot in Bioinformatics.With the problem of low precision of large-scale multiple sequence alignment,a new multiple sequence alignment algorithm based on particle swarm optimization with probability statistic and automatic adaptive mutation（MSA_PMPSO） was proposed.MSA_PMPSO generates new solutions with the help of a model which is established according to the distributional probability of high quality solutions.This design may enhance the study capability of particles and improve the accuracy of alignment.Also the algorithm introduces the fitness variance,the expected optimal solution and the mutation operation,which makes for jumping out of the local optimum.The experimental results of 142 benchmarks from the BALIBASE prove that the proposed algorithm is feasible and valid.Especially,it is more advantageous than existing algorithms when the large-scale closed genetic long sequences are aligned.