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

维普资讯 多序列比对问题的粒子群优化算法求解 张鹏帅 霍红卫 (西安电子科技大学计算机学院，西安 710071) E—mail：pshzhangCttttttttt~mail．xidian．edu．cn 摘 要 文章提 出了一新的算法，41用粒子群优化算法求解多序列比对的问题，这是粒子群优化算法在生物信息学方面 的一个新的应用。文章从粒子群算法的原理和多序列 比对问题模型入手，来提 出怎样改造粒子群优化算法使其可以解决 多序列比对问题 ，最后给 出利用粒子群优化算法求解多序列比对的算法，及其测试结果。 关键词 生物信息学 双序列比对 多序列比对 粒子群优化算法 文章编号 1002-8331-(2005)18-0084—04 文献标识码 A 中图分类号 TP301 PSO forMultipleSequencesAlignment ZhangPengshuai HuoHongwei (Schoo1ofComputerScience，XidianUniversity。Xian710071) Abatract： Thispaperintroducesanewalgorithm：theparticleswarm optimization (PSO)forsolvingtheproblem ofse— quenee alignment．Itisa new attemptthatPSO in thebioinformaticsapplied field． Take themuhiple sequencealingment model，Analgorihtm ofakindofspecial particleswarm optimization isconstructed anddontchanget}lecharaetersand advantagesofPSO．Finally，ThepaperintroduceshteMSAPSO(MultipleSequenceAlingmentPSO)andt}letestresuh． Keywords：bioinformatics，pairwisealignment，multipleseuqence aligrmaent，particleswarm optimisation l 引言 着眼于序列中的某些特殊片断，比较这些片断之间的相似性 ， 在生物信息学中，对序列数据进行相似性比较即序列比 即局部比对 (1ocal alignment)。 对，是一种基本的信息处理方法，它对于发现生物序列中的功 典型的双序列 比对算法是 needleman—Wunsch算法7[／。双 能、结构和进化的信息具有非常重要的意义11【，而序列比对就是 序列比对是序列分析的基础。然而 ，对于构成基 因家族的成组 运用某种特定的数学模型或算法 ，找出两个或多个序列之间最 的序列来说 ，要建立多个序列之间的关系 ，这样才能揭示整个 大匹配碱基或残基数 ，比对的结果反映了算法在多大程度上反 基因家族的特征。这就要进行多序列比对 (Multipleseuqence 映了序列之 间的相似性关系以及他们的生物学特征 。 alingment)由于可以提高序列比对的信噪比，多序列比对在阐 序列 比对的发展已经有 40对年的时间了，Gibbs于 1970 明一组相关序列的重