序列比对是生物信息学研究中一种基本的信息处理方法,对序列分析、序列结构功能的预测以及进化树的构建具有极为重要的意义。无论是双序列比对还是多序列比对,都可以看成是数学上的优化问题。随着生物分子序列数据的急速增长,找到整体上最优比对的难度也随之增加,对于这类优化问题研究者们致力于用启发式算法来找到问题的近似最好解,如遗传算法,蚁群算法等。而化学反应优化(Chemical Reaction Optimization)是一种新的启发式算法,通过模拟化学反应中分子运动过程来搜索最优解,并且CRO已经成功解决一些经典的优化问题,因此本文首次运用CRO来完成序列比对。本文的研究是运用化学反应优化方法来解决双序列比对问题的一次有益尝试,以期为序列分析领域提供全新的序列比对工具,为以后解决多序列比对问题提供平台,也可加以并行处理技术对其进行加速,以加强其处理大规模序列比对问题的能力。首先对序列比对的概念及相关知识点进行了介绍,并对现有经典的双序列比对算法进行详细地阐述与比较。针对双序列比对问题的数学模型,在CRO的算法框架上,提出了一种新的双序列比对算法HCRO-PSA(Hybrid Chemical Reaction Optimization for Pairwise Sequence Alignment)。CRO 模拟化学反应中分子运动中能量的变化而得到的一种元启发式方法,通过四个基本操作:撞墙、分解、分子间无损碰撞以及合成来完成对解空间的搜索,其中撞墙和分子间无损碰撞可以进行局部最优值搜索,而分解和合成是用来拓展搜索领域,从而尽可能获得全局最优值,最后找到系统中势能值最低的分子结构。由于CRO在迭代过程中只记录下当前质量好的分子,这样使得搜索会陷于局部最优解,为了更好的获得全局最优解本文在CRO框架上引入退火操作将Metropolis接受准则,提出解决双序列比对的混合式CRO算法。HCRO-PSA算法针对双序列比对的实际问题结合启发思想完整地设计了 CRO的具体操作,为加快算法处理序列比对的速度,设计了一种并行CRO模型。为了验证新算法的可行性,通将混合式CRO算法应用到双序列比对上,并将得到的结果在得分值上与经典算法进行了实验验证,实验结果表明了此算法的有效性,在一定序列长度范围内,可以达到很好的比对精度。