模拟退火遗传算法在生物多序列比对中的应用研究

论文摘要

序列比对是生物信息学中一项重要的基础性研究课题,最基本任务之一是进行多序列比对,目前还没有一个通用且最佳的多序列比对算法。本文提出使用遗传算法和模拟退火算法相结合来解决多序列比对问题,并对此进行了深入研究和探讨,主要研究结果如下:1、在分析传统遗传算法（Genetic Algorithm）、模拟退火算法（Simulated AnnealingAlgorithm）的优缺点基础上,将模拟退火算法引入遗传算法的选择策略和生存策略,通过模拟退火算法来减轻遗传算法的选择压力,利用模拟退火算法的BoltZman控制来接收交叉和变异后的个体,构建了一种模拟退火遗传算法。2、将模拟退火遗传算法应用到多序列比对问题中,提出了多序列比对的模拟退火遗传算法（MSA-GASA）,建立了数学模型,利用MSA-GASA对BAliBASE数据库中的数据集进行了测试,对测试的试验结果和ClustalX的结果进行比较分析,结果表明,MSA-GASA比ClustalX的比对结果准确度更高,具有更好的敏感性,和传统遗传算法相比,MSA-GASA的收敛性相应加快,时间复杂度相对较小,总之MSA-GASA改善了多序列比对的质量,提高了算法的稳定性。

论文目录

• 摘要
• Abstract
• 第一章 文献综述
• 1 研究背景和意义
• 2 序列比对基础知识
• 2.1 序列比对概述
• 2.2 序列比对分类
• 2.3 空位罚分
• 2.4 相似性得分矩阵
• 2.5 多序列比对算法评价基准数据集
• 2.6 CLUSTALX
• 3 生物信息学中序列比对算法的现状
• 3.1 双序列比对的算法现状
• 3.2 多序列比对算法现状
• 4 研究的主要内容及方法
• 5 本章小结
• 第二章 模拟退火遗传算法的构建
• 1 遗传算法
• 1.1 遗传算法的基本技术
• 1.2 遗传算法的主要运行参数
• 1.3 遗传算法的优越性和不足
• 1.4 标准遗传算法的流程图
• 1.5 标准遗传算法的形式化描述
• 2 模拟退火算法
• 2.1 模拟退火算法的基本思想
• 2.2 模拟退火算法的参数控制问题
• 2.3 模拟退火算法的优点和不足
• 3 模拟退火遗传算法的构建
• 3.1 遗传算法“早熟”产生的原因
• 3.2 模拟退火遗传算法的提出
• 3.3 模拟退火遗传算法的特点
• 3.4 本研究提出的模拟退火遗传算法流程图
• 4 本章小结
• 第三章 模拟退火遗传算法在多序列比对中的应用
• 1 引言
• 2 多序列比对问题的数学模型
• 3 MSA-GASA的简单描述
• 4 MSA-GASA的设计
• 4.1 编码设计
• 4.2 初始化种群
• 4.3 适应度函数
• 4.4 遗传算子
• 4.5 群体更新
• 4.6 算法终止条件
• 4.7 模拟退火参数的设计
• 5 算法的实现
• 5.1 试验环境
• 5.2 试验算法的参数
• 5.3 试验数据
• 5.4 试验设计
• 5.5 试验结果与分析
• 6 本章小结
• 第四章 全文总结
• 1 总结
• 2 展望
• 参考文献
• 致谢
• 作者简介