多序列比对问题的粒子群优化算法求解

《多序列比对问题的粒子群优化算法求解》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、维普资讯http://www.cqvip.com多序列比对问题的粒子群优化算法求解张鹏帅霍红卫(西安电子科技大学计算机学院，西安710071)E—mail：pshzhangCt~mail．xidian．edu．cn摘要文章提出了一新的算法，4'1用粒子群优化算法求解多序列比对的问题，这是粒子群优化算法在生物信息学方面的一个新的应用。文章从粒子群算法的原理和多序列比对问题模型入手，来提出怎样改造粒子群优化算法使其可以解决多序列比对问题，最后给出利用粒子群优化算法求解多序列比对的算法，及其测试结果。关键词生物信息学双序列比对多序列比对粒子群优化算法文章编号1002-

2、8331-(2005)18-0084—04文献标识码A中图分类号TP301PSOforMultipleSequencesAlignmentZhangPengshuaiHuoHongwei(Schoo1ofComputerScience，XidianUniversity。Xian710071)Abatract：Thispaperintroducesanewalgorithm：theparticleswarmoptimization(PSO)forsolvingtheproblemofse—queneealignment．ItisanewattemptthatPSO

3、inthebioinformaticsappliedfield．Takethemuhiplesequencealignmentmodel，Analgorithmofakindofspecialparticleswarmoptimizationisconstructedanddon'tchanget}lecharaetersandadvantagesofPSO．Finally，ThepaperintroducestheMSAPSO(MultipleSequenceAlignmentPSO)andt}letestresuh．Keywords：bioinformati

4、cs，pairwisealignment，multiplesequencealigrmaent，particleswarmoptimisationl引言着眼于序列中的某些特殊片断，比较这些片断之间的相似性，在生物信息学中，对序列数据进行相似性比较即序列比即局部比对(1ocalalignment)。对，是一种基本的信息处理方法，它对于发现生物序列中的功典型的双序列比对算法是needleman—Wunsch算法[7／。双能、结构和进化的信息具有非常重要的意义【11，而序列比对就是序列比对是序列分析的基础。然而，对于构成基因家族的成组运用某种特定的数学模型或算法，找出

5、两个或多个序列之间最的序列来说，要建立多个序列之间的关系，这样才能揭示整个大匹配碱基或残基数，比对的结果反映了算法在多大程度上反基因家族的特征。这就要进行多序列比对(Multiplesequence映了序列之间的相似性关系以及他们的生物学特征。alignment)由于可以提高序列比对的信噪比，多序列比对在阐序列比对的发展已经有40对年的时间了，Gibbs于1970明一组相关序列的重要生物学模式方面起着相当重要的作用。年提出了点阵法13]，1981年Smitll和waterman提出了动态规划多序列比对是进行生物序列分析的最基本的任务之一，它算法，应用最广的有Fa

6、sta[~和Blast算法婀。在发现序列模体(motif)和保守区域、系统发育分析、结构预测当今生物信息学领域的主要研究方向之一，是从研究蛋白等方面具有重要的作用，是生物信息学当前的研究热点问题之’一质功能人手，进而阐明进化关系。以序列为基础，用序列分析的O手段以及所得的结果推断生物大分子的功能是其常用的方法已有的多序列比对算法有：Needlman—Wunsch算法、Car-之一。基本出发点，是通过和数据库中已知功能的序列进行相rilo—LipmantSt"J~法、广泛使用的多序列比对软件包ClustalW~基似性比对，确定那些新测定的序列与已知序列之间的关系。

7、于渐进比对思想构建、SAGAt01基于遗传算法构建。确定DNA序列之间或蛋白质序列之间相似性程度的过程该文研究一种新的序列比对的方法，利用粒子群优化算法称为序列比对(sequencealignment)。可以通过插入空位得到更(PSO)来实现基因序列的比对。这是一个崭新的尝试。好的匹配。序列比对是序列分析和数据库搜索的基础，也可用来找出保守的序列模体。序列比对分为双序列比对和多序列比2粒子群优化算法(PSO)对。人类受到社会系统、物理系统、生物系统等运行机制启发，双序列比对(pairwisealignment)是指通过一定算法对两建立和发展许多方法来解决实际的问

8、题。典型的有遗传算法、个