退火进化算法在生物序列比对中的应用研究

摘要

比较是科学研究中最常见的方法，通过将研究对象相互比较来寻找对象可能具备的特性。序列比对是在生物信息学研究中最常用和最经典的研究手段。其意义在于从核酸、氨基酸的层次分析序列的相似性，推测其结构功能及进化上的联系，是基因识别、分子进化、生命起源研究的基础。 本文中介绍了生物信息学中的双序列和多序列比对算法的研究现状，并对多序列比对问题提出了一种基于模拟退火算法和遗传算法相结合的退火进化算法。多序列比对问题的算法复杂性按指数规律增长，属于NP问题，根据这一特点，我们采用属于迭代方法的遗传算法与模拟退火算法相结合的这一算法，这种方法能够很好的处理NP问题。由于遗传算法容易导致早熟收敛问题，使得进化无法收敛到最优解。很多基于遗传算法的多序列比对的算法就存在这一缺点。根据这一特点，我们通过引进模拟退火算法，利用模拟退火接受准则(即Metropolis准则)保持群体中个体的多样性来解决早熟收敛。模拟退火具有概率突跳的双向搜索能力，既容易跳出局部极值的陷阱，又能确保搜索的全局优化性。将模拟退火引入到遗传算法策略中，不但丰富了遗传算法的搜索行为，避免出现早熟收敛，同时又可以利用遗传算法本身强大的并行全局搜索能力。 最后本文进行了一系列数据测试，通过测试结果，我们可以看到本算法在生物敏感性和运算效率较之传统算法均有所提高。

目录

文摘

英文文摘

独创性说明及大连理工大学学位论文版权使用授权书

引 言

1生物信息学基础

2序列比对基础

3多序列比对算法研究

4退火进化算法

5基于退火进化的多序列比对算法设计

结 论

参考文献

攻读硕士学位期间发表学术论文情况

致谢