论文摘要
序列比对是生物信息学中最基本的信息处理方法之一,对于研究核酸与蛋白质序列有着非同一般的意义。通过序列比对,可以发现核酸或者蛋白质序列中的相似性片段,然后根据生物科学中的生物进化理论,依据相似性片段数量的多少以及相似程度的高低推断出该序列属于哪个基因家族,或者说,这些序列之间有着怎样的进化关系。同时,还可以根据相似性片段推测出未知序列的功能和结构。此外,序列比对还可应用在医学领域,通过比对健康序列和病变序列,可以推测出哪些基因发生了病变,发生病变的位置,为疾病的治疗提供有效帮助。多序列比对是本文研究的主要内容,研究的主要目的是提高多序列比对的精度。首先介绍了多序列比对研究现状和相关算法的问题,尤其是对群智能算法的研究,比如遗传算法、粒子群算法、模拟退火算法解决序列比对问题的现状；其次首次将人工蜂群算法应用到多序列比对问题中;最后,又对粒子群算法和人工蜂群算法进行了改进,应用到多序列比对中,并通过仿真实验的方式,证明了这两种方法的有效性。具体如下：介绍了基本粒子群优化算法（Particle Swarm Optimization, PSO）模型以及几种最具代表性的惯性权重取值方法：随迭代次数线性降低的线性惯性权重、动态自适应的惯性权重取值方法等。惯性权重大,粒子群算法的全局搜索能力强,粒子主要的功能是探索新的解领域；惯性权重小,粒子群算法的局部搜索能力强,粒子的主要功能是开发当前最优解,提高解的精度。对这些理论有了深入了解和分析之后,提出新的惯性权重取值方法----分段取值惯性权重（subsection weight, SW）,将算法运行过程分成两个部分,符部分采用不同的惯性策略。随后,根据生物学中鸟群觅食的特点,粒子除了一个自我学习能力和社会生存能力之外,还具有小范围内粒子之间的交流能力,三者分别对应着个体最优位置、全局最优位置、群组最优位置。将引入的群组最优位置与Sw惯性取值方法融合在一起,提出SWGPSO算法。介绍了人工蜂群算法的相关知识,基本人工蜂群算法模型来源于蜂群的觅食行为,在这个模型中,雇佣蜂、跟随蜂和侦察蜂符自行使自己的职权,并和谐交流,从而达到搜索到最佳食物源的目的。首先尝试将人工蜂群算法应用到多序列比对问题中,并对其解决该问题的效果进行了比较分析,不仅证实了该算法可以用于求解多序列比对问题,而且其性能在某种意义上要优于其他的群智能算法。一般来说,单一的算法并不完美,总会有一些缺点,因此,我们又对基本人工蜂群算法进行改进,将模拟退火算法中的Metropolis接受准则引入到侦察蜂的随机搜索过程中,使得侦察蜂能够以一个较小概率接受较差的解,从而保持种群多样性,避免算法陷入局部最优,提出了ABCSA算法。仿真实验结果表明ABCSA算法所得到的序列比对结果比基本人工蜂群算法得到的更精确,也证明了ABCSA算法解决多序列比对问题的有效性。