生物信息学是在生命科学的研究中,以计算机为工具对生物信息进行储存、检索和分析的科学。序列比对是生物信息学中一种基本的信息处理方法,对于发现核酸和蛋白质序列功能、结构和进化的信息具有非常重要的意义。随着生物序列数据库中序列数据的激增,开发兼有高度生物敏感性和高效率的算法就显得非常迫切。本文研究了生物信息学中的双序列比对算法。论文叙述了序列比对算法领域从70年代到现在的发展过程,讨论了Needleman和Wunsch最早提出的生物序列比对算法----全局比对动态规划算法,同时分析了目前双序列比对动态规划算法及启发式算法存在的问题。遗传算法是模拟自然界生物进化过程来求解最优极值问题的一类自组织、自适应人工智能技术,它通过对当前群体施加选择、交叉、变异等一系列遗传操作,从而产生新一代的群体,并逐渐使群体进化到包含或接近最优解的状态。由于其具有易于实现、应用效果明显等优点而被众多应用领域所接受,在自适应控制、组合优化、模式识别、机器学习、人工智能等领域得到了广泛的应用。但许多仿真和应用结果都表明遗传算法还存在群体易陷入“早熟”现象,局部搜索能力弱等问题。模拟退火算法刚好可以补充遗传算法这一不足,模拟退火算法是模拟物理退火过程的一种随机优化搜索算法。算法以优化过程的求解与物理退火过程的相似性为基础,通过接受准则和对下降温度的控制,能够有效的克服优化过程陷入局部极小从而获得全局最优解。论文将遗传算法结合模拟退火思想用于双序列比对问题,建立了相应的数学模型。实验结果表明,对于双序列比对问题,算法是有效的合理的。