蚁群与遗传算法的融合及其在生物序列比对问题中的应用

论文摘要

序列比对是生物信息学中最常见的问题之一，也是一种重要的生物信息处理技术。它通过对生物序列数据进行相似性比较，来发现生物序列中的功能、结构和进化等信息，是基因识别、分子进化、生命起源等生物信息学研究的基础。遗传算法(Genetic Algorithm，GA)是一种基于自然选择原理和自然遗传机制的随机化全局寻优搜索算法，体现了“生存竞争、优胜劣汰、适者生存”的竞争机制。它模拟自然界中的生命进化机制的系统模型，在人工系统中实现特定参数目标的优化。遗传算法的主要特征是全局收敛性。蚁群算法(Ant Colony Algorithm，简称AA)是基于对自然界中真实蚁群的集体觅食行为的研究，模拟真实蚁群的协作过程而得到的一种随机搜索算法。算法由若干个人工蚂蚁共同构造解路径，通过在解路径上遗留并交换信息素提高解的质量，进而达到求解的目的。蚁群算法的主要特征是正反馈和隐并行性。本文对传统的蚁群算法和遗传算法进行了研究，并将两者有机结合，提出了一种新型的蚁群遗传算法。该算法有效地利用了蚁群算法的正反馈特性和遗传算法的全局收敛特性，能快速有效地搜索最优解。将蚁群遗传算法应用到生物学的序列比对问题中，并通过程序与经典的比对算法进行比较分析结果表明了算法的可行性和有效性。论文的主要工作如下：一、研究了生物信息学中的序列比对基础，并对常用的序列比对算法进行了分析。二、对蚁群算法和遗传算法进行了研究：分别建立了基于蚁群算法和遗传算法的序列比对模型，提出了相应的基于蚁群算法的序列比对算法(AA_SA)和基于遗传算法的序列比对算法(GA_SA)．三、结合蚁群算法的正反馈特性和遗传算法的全局收敛特性，提出了一种新的算法——蚁群遗传算法(GAAA)。将GAAA应用到生物信息中的序列比对问题中，建立了基于GAAA的序列比对模型，给出了序列比对问题的GAAA算法描述(GAAA_SA)．四、实现DNA序列比对原型系统，对蚁群遗传算法、遗传算法、蚁群算法这三种进化算法进行了仿真实验。结果表明蚁群遗传算法的收敛率更高，具有更好的全局收敛性能，蚁群遗传算法能在更少的迭代次数中达到全局最优解。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景与意义
• 1.2 生物信息学中序列比对算法的发展
• 1.3 遗传算法和蚁群算法概述
• 1.4 本文的主要内容
• 第二章 序列比对基础
• 2.1 生物信息学背景知识
• 2.1.1 遗传信息载体-DNA
• 2.1.2 分子生物学中心法则
• 2.2 序列比对
• 2.2.1 序列比对问题描述及比对目的
• 2.2.2 序列比对的分类
• 2.2.2.1 双序列比对和多序列比对
• 2.2.2.2 全局比对和局部比对
• 2.2.3 替换矩阵和空位处罚
• 2.3 经典序列比对算法
• 2.3.1 动态规划算法
• 2.3.1.1 动态规划算法的思想和特征
• 2.3.1.2 动态规划算法的基本步骤
• 2.3.1.3 基于动态规划的算法-NeedleMan-Wunsch算法和Smith-Waterman算法
• 2.4 其他比对方法-FASTA和 BLAST算法
• 2.5 小结
• 第三章 蚁群算法和遗传算法的原理以及在序列比对问题中的应用
• 3.1 蚁群算法的基本原理
• 3.2 蚁群算法在序列比对问题中的应用
• 3.2.1 蚁群算法求解序列比对问题的模型
• 3.2.2 蚁群比对算法的设计与分析
• 3.2.3 蚁群比对算法的描述
• 3.2.4 蚁群比对算法的分析
• 3.2.5 蚁群比对算法的实验结果和分析
• 3.3 遗传算法的基本原理
• 3.3.1 遗传算法的基本原理
• 3.3.2 遗传算法的算法描述
• 3.4 遗传算法在序列比对问题中的应用
• 3.4.1 遗传比对算法的模型
• 3.4.2 遗传比对算法的设计与分析
• 3.4.3 遗传比对算法的描述
• 3.4.4 遗传比对算法的实验结果和分析
• 3.5 小结
• 第四章 基于蚁群遗传算法的序列比对算法的分析与设计
• 4.1 蚁群算法和遗传算法的对比研究
• 4.2 蚁群算法和遗传算法的融合
• 4.2.1 蚁群算法和遗传算法的融合的可行性和优越性
• SA）在序列比对中的应用'>4.3 蚁群遗传比对算法（GAAA_SA）在序列比对中的应用
• SA）求解序列比对的模型'>4.3.1 蚁群遗传比对算法（GAAA_SA）求解序列比对的模型
• 4.4 蚁群遗传比对算法的描述与分析
• 4.4.1 蚁群遗传比对算法的算法描述
• 4.4.2 蚁群遗传比对算法的分析
• 4.5 小结
• 第五章 算法实现与实验结果分析
• 5.1 蚁群遗传比对算法的实现
• 5.1.1 参数设置
• 5.1.2 算法流程
• 5.1.3 算法实现
• 5.2 实验结果与分析
• SA搜索最优序列比对的过程'>5.2.1 GAAA_SA搜索最优序列比对的过程
• 5.3 算法比较
• SA）与蚁群比对算法（AA_SA）的比较'>5.3.1 蚁群遗传比对算法（GAAA_SA）与蚁群比对算法（AA_SA）的比较
• SA）与遗传比对算法（GA_SA）的比较'>5.3.2 蚁群遗传比对算法（GAAA_SA）与遗传比对算法（GA_SA）的比较
• SA）与动态规划算法（NW）的比较'>5.3.3 蚁群遗传比对算法（GAAA_SA）与动态规划算法（NW）的比较
• 5.4 小结
• 第六章 总结与展望
• 参考文献
• 附录一 SW算法实现核心代码
• SA算法实现核心代码'>附录二 GAAA_SA算法实现核心代码
• 致谢
• 攻读学位期间发表的学术论文