随着人类基因组计划(HGP)等项目的实施,生物学及相关数据的积累速度呈爆炸性增长,生物信息学这个融合了生命科学、信息科学等众多相关学科的边缘学科,为“海量”生物信息的处理提供了新的方法。序列比对是生物信息学中序列分析的基本操作,它对于发现生物序列中的功能、结构和进化信息具有非常重要的意义。目前双序列比对算法已趋于完善,相比之下,现有实用的多序列比对方法还不能保证一定给出最优的比对结果,而是只能给出一个近似值。如何开发出准确和高效的多序列比对程序是目前序列比对的一个难点。本文主要研究当前多序列比对发展现状,设计并实现了一种将组合优化中遗传算法和模拟退火算法运用到多序列比对中的方法。本文首先分析了序列比对中相似性记分矩阵、空位罚分和目标函数对比对结果的影响,并具体实现了两种广泛应用的目标函数:SP函数和COFFEE函数。然后深入研究了当前流行的比对算法,并系统地论述了双序列比对中经典的全局比对Needleman-Wunsch算法和局部比对Smith-Waterman算法;讨论了多序列比对的精确算法——动态规划法,分析了该算法呈指数增长的算法复杂性,进而引入了当前流行的渐进比对算法和迭代比对算法,并阐述了经典渐进比对软件CLUSTAL的算法机制。在此基础上本文引入遗传算法。遗传算法是一种模拟自然界生物进化过程的人工智能技术,通过选择、交叉、变异等遗传操作迭代更新种群,从而产生适应度更高的个体。本文对多序列比对问题建立遗传算法模型,实现了MSA-GA算法,设计出了适合多序列比对的二维染色体编码策略和三种遗传算子,以SP目标函数实现了MSA-GA算法,并在BAliBASE3.0比对库中与经典的CLUSTAL算法比较测试。从研究表明MSA-GA算法的比对结果比较满意,但与CLUSTAL相比还存在差距。此后研究了MSA-GA算法不足之处,深入阐述了遗传算法中普遍存在的“早熟”现象。传统的遗传操作在不断迭代中强化了某些个体的优势,使得搜索范围迅速变窄,令算法最终收敛于一个局部最优解。为了寻求更高效的多序列比对算法,本文将模拟退火算法引入到传统的遗传算法中,设计并实现了MSA-GSA算法。模拟退火算法模拟了固体退火过程,运用接受准则和对下降温度的控制跳出局部极值的陷阱,并确保搜索的全局优化性。主要的工作是设计并实现了将退火操作加入到遗传算法的三种主要操作选择、交叉和变异中,在种群更新阶段,通过Metropolis接受准则调整遗传算法的进化过程,保证了种群多样性,并在迭代后期加快了收敛速度,克服“早熟”现象,得到全局最优解。在适应度函数方面,以COFFEE函数替代了SP函数,通过Needleman-Wunsch比对算法建立双序列比对库。经测试MSA-GSA算法精度有大幅提高,证明该算法在解决多序列比对问题上是行之有效的。