基于带变异算子粒子群的多序列比对算法研究与应用

《基于带变异算子粒子群的多序列比对算法研究与应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、摘要序列比对是生物信息学中一项重要的基础性研究课题，多序列比对则是其最基本任务之一。由于各种原因，目前还没有一个最佳的多序列比对算法。在研究比较了现有的多序列比对算法的基础上，本文首次提出了使用带变异算子粒子群优化算法来解决多序列比对问题。本文首先分析了空位罚分、替换矩阵和目标函数对序列比对的影响，具体实现SP和COFFEE目标函数。然后通过对多序列比对算法的现状的研究以及对粒子群优化算法特点等的分析，实现了基于粒子群优化算法的多序列比对算法MSAPSO(aParticleSwarmOptimizationdedicatedforMultipleSequenceAlign

2、ments)，提出了基于带变异算子粒子群优化算法的多序列比对算法MSAVPSO(aVariation-OperatorParticleSwarmOptimizationdedieatedforMultipleSequenceAlignments)，并分别实现了基于SP和COFFEE目标函数的MSAPSO和MSAVPSO。最后用基准多序列比对库BALIBASEl．0中的用例对算法进行测试，结果表明MSAVPSO算法在解决基因序列比对问题上是有效的。关键词：：生物信息学多序列比对目标函数粒子群优化算法变异算子AbstraetAbstractSequencealignmento

3、fbioinformaticsisanimportantfundamentalsubjectinbioinformaticsresearch，oneofitsmostbasictaskistomultiplesequencealignments．Alsothereisnotanoptimalalgorithmofmultiplesequencealignments．Thispaperproposesamethod,whichUseParticleSwarmOptimizationandVariation-OperatorParticleSwarmOptimizationa

4、lgorithmofevolutionaryalgorithm，tosolvetheproblemsofmultiplesequencealignments．First,theeffectonsequencealignmentcausedbythegappenalty,substitutionmatrixandobjectivefunctionareanalyzed，andtheSPobjectivefunctionandCOFFEEobjectivefunctionareimplemented．Thenthedynamicprogrammingalgorithmthat

5、isoneofaccuratealgorithmsofpairwisealignmentisstudiedandimplemented．Laterthroughthestudyoncurrentsituationofthemultiplesequencealignmentsalgorithmandtheanalysistotheprincir'leandcharacteristicofthegeneticalgorithmandparticleswarmoptimizationalgorithmandSOon,presentthemultiplesequencealign

6、mentsalgorithmbasedonparticleswarmoptimizationalgorithmMSAPSO(aParticleSwarmOptimizationdedicatedforMultipleSequenceAlignment)andthemultiplesequencealignmentsalgorithmbasedonVariation-OperatorparticleswarmoptimizationalgorithmMSAVPSO(aVariation-OperatorParticleSwarmOptimizationdedicatedfo

7、rMultipleSequenceAlignment)．AlsothetwoalgorithmsbasedonSPobjectivefunctionandCOFFEEobjectivefunctionisimplemented．Finally,twoalgorithmsareusedtotestbenchmarkmultiplesequencealignmentsdatabaseBALIBASEl．0．TheresultsshowthattheproposedMSVAPSOalgorithmisfeasibletosolvet