蚁群遗传算法在序列比对中的应用

论文摘要

生物信息学是以计算机为主要工具,对以指数增长的生物数据进行处理的一门交叉学科。序列比对是生物信息学的基本研究方法,通过序列比对可以推断基因的结构、功能和进化关系。蚁群算法是一种仿真算法,模拟了蚂蚁在觅食过程中寻找最短路径的方法来求解最优解。遗传算法是另一种仿真算法,它模拟了生物的遗传过程来寻求最优解。蚁群遗传算法是一种混合算法,它通过遗传算法对蚁群算法的一组参数进行优化,来达到取得全局最优解和加快收敛速度的目的。本文通过对国内外序列比对算法的分析,将蚁群算法应用于序列比对上,设计了新型的蚁群序列比对算法。但因蚁群算法一般仅获得局部最优解,如果将遗传算法应用于蚁群序列比对算法上将克服这一现象,这就产生了蚁群遗传序列比对算法。蚁群遗传序列比对算法能扩大求解空间,克服蚁群算法的局部性,求得全局最优解。实验表明蚁群遗传序列比对算法可以显著提高序列比对的效果。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景
• 1.2 研究现状
• 1.3 研究意义和目标
• 1.3.1 序列比对研究的意义
• 1.3.2 研究的目标
• 1.4 论文结构
• 第二章 生物信息学背景知识
• 2.1 生物信息学基本概念
• 2.1.1 生物信息学的主要研究内容
• 2.1.2 核酸和蛋白质
• 2.1.3 遗传信息的传递与表达
• 2.1.4 生物信息学的中心法则
• 2.2 序列比对的基本原理
• 2.2.1 空位罚分
• 2.2.2 替换矩阵
• 2.2.3 双序列比对基本原理
• 2.3 序列比对问题的描述以及序列比对的分类和目的
• 2.3.1 序列比对问题的描述
• 2.3.2 序列比对的分类
• 2.4 序列比对的常用算法
• 2.4.1 用动态规化算法进行序列比对
• 2.4.2 Needleman-Wunsch 算法和Smith-Waterman 算法
• 2.5 本章小结
• 第三章 蚁群算法、遗传算法和蚁群遗传算法的原理和应用
• 3.1 蚁群算法原理与应用
• 3.1.1 蚁群算法的简单描述
• 3.1.2 蚁群算法的基本原理
• 3.1.3 蚁群算法的模型
• 3.1.4 蚁群算法的设计步骤
• 3.1.5 蚁群算法的应用
• 3.2 遗传算法原理与应用
• 3.2.1 遗传算法的产生的历史背景
• 3.2.2 遗传算法的基本原理和特点
• 3.2.3 基本遗传算法的设计步骤
• 3.2.4 遗传算法在旅行商问题（TSP）中的应用
• 3.3 蚁群遗传算法原理与应用
• 3.3.1 蚁群遗传算法的基本原理
• 3.3.2 蚁群遗传算法的设计步骤
• 3.3.3 蚁群遗传算法的应用
• 3.4 本章小结
• 第四章 蚁群序列比对算法设计
• 4.1 蚁群序列比对算法在DNA 序列比对上应用的设计
• 4.1.1 蚁群序列比对算法在DNA 序列比对上应用的设计思路
• 4.1.2 蚁群序列比对算法的描述
• 4.1.3 蚁群序列比对算法的流程图
• 4.2 蚁群序列比对算法在DNA 比对和氨基酸序列比对上的应用
• 4.2.1 DNA 和氨基酸序列比对中常用的得分矩阵
• 4.2.2 蚁群序列比对算法在DNA 和氨基酸序列比对中的应用
• 4.3 实验结果及分析
• 4.3.1 蚁群序列比对算法的收敛性实验及结果分析
• 4.3.2 蚁群序列比对算法在DNA 序列比对上应用的实验及结果分析
• 4.3.3 蚁群序列比对算法在氨基酸序列比对上应用的实验及结果分析
• 4.4 本章小结
• 第五章 蚁群遗传序列比对算法设计
• 5.1 蚁群序列比对算法的不足及解决办法的提出
• 5.1.1 蚁群序列比对算法的不足
• 5.1.2 蚁群遗传序列比对算法的提出
• 5.2 蚁群遗传序列比对算法的设计
• 5.2.1 蚁群遗传序列比对算法的描述
• 5.2.2 蚁群遗传序列比对算法的算法流程图
• 5.3 实验结果及分析
• 5.3.1 蚁群遗传序列比对算法的收敛性实验结果及分析
• 5.3.2 蚁群遗传序列比对算法在DNA序列比对上应用的实验结果及分析
• 5.3.3 蚁群遗传序列比对算法在氨基酸序列比对上应用的实验结果及分析
• 5.4 本章小结
• 第六章 总结与展望
• 致谢
• 参考文献
• 附录：作者在攻读硕士学位期间发表的论文