免疫遗传算法在生物序列比对中的应用

论文摘要

序列比对是生物信息学中最常见的问题之一,也是一种重要的生物信息处理技术。它通过对生物序列数据进相似性比较,来发现生物序列中的功能、结构和进化等信息,是基因识别、分子进化、生命起源等生物信息学研究的基础。免疫遗传算法是一种混合型改进遗传算法。它将遗传算法与免疫原理结合起来考虑,在传统遗传算法的框架之上,引入了免疫系统的诸多特性如免疫调节机制、多样性保持策略等,有效地防止了搜索过程中的未成熟收敛等问题,是一种更加有效的优化算法。本文在分析了国内外序列比对算法及序列比对的优化问题本质的基础上,设计了一种适用于双序列比对可行解的编码方案,提出了一种应用于双序列比对的新算法——基于免疫遗传算法的双序列比对方法（PSAIGA,Pair-wise Sequence Alignment based onImmune Genetic Algorithm）。并应用上述算法分别进行了DNA和蛋白质序列的比对,通过实验证明了其可行性和有效性。本文PSAIGA算法的实现采用的是C++语言。同时,对Needleman-Wunsch算法、基于遗传算法的双序列比对方法PSAGA也进行了实现。前者为评价PSAGA及PSAIGA算法结果的优劣提供了判定依据;而后者的比对实验结果说明了与其相比PSAIGA能够明显改善比对结果,提高比对效率。此外,还采用Windows API函数对进行序列比对的用户交互界面进行了实现。

论文目录

• 摘要
• Abstract
• 第一章 引言
• 1.1 生物信息学
• 1.2 序列比对算法的发展
• 1.3 免疫遗传算法概述
• 1.4 本文主要内容
• 第二章 生物序列比对
• 2.1 生物学背景知识
• 2.1.1 遗传信息的传递与表达
• 2.1.2 物种进化与基因突变
• 2.2 生物序列比对
• 2.2.1 序列比对问题
• 2.2.2 序列比对问题的数学模型
• 2.2.3 序列比对的分类
• 2.2.4 空位罚分
• 2.2.5 打分矩阵
• 2.3 基于动态规划的序列比对算法
• 2.3.1 动态规划算法
• 2.3.2 用动态规划算法进行序列比对
• 2.3.3 基于动态规划的一些比对算法
• 2.5 小结
• 第三章 免疫遗传算法的原理和应用
• 3.1 遗传算法的原理及缺陷
• 3.1.1 遗传算法中的基本概念
• 3.1.2 基本遗传算法的流程
• 3.1.3 模式定理
• 3.1.4 遗传算子及其对遗传算法性能的影响
• 3.2 生物免疫学基本原理
• 3.2.1 生物免疫系统的作用原理
• 3.2.2 免疫系统的特点及其对改进算法的启示
• 3.3 免疫遗传算法的基本原理
• 3.3.1 基于疫苗机制的IGA
• 3.3.2 利用抗体多样性保持策略的IGA
• 3.4 小结
• 第四章 基于IGA 的序列比对算法的分析与设计
• 4.1 免疫遗传算法求解序列比对的模型
• 4.2 应用于序列比对的免疫遗传算法的操作模型
• 4.2.1 抗体适应度计算
• 4.2.2 免疫选择模块
• 4.2.3 遗传算子设计
• 4.3 基于IGA 的序列比对算法的基本步骤
• 4.4 小结
• 第五章 算法实现与实验结果分析
• 5.1 PSAIGA 算法的实现
• 5.1.1 参数的设置
• 5.1.2 仿真程序的流程
• 5.1.3 PSAGA 算法的实现
• 5.2 实验结果及其分析
• 5.2.1 PSAIGA 搜索序列最优比对的过程
• 5.2.2 DNA 序列的比对结果及其分析
• 5.2.3 蛋白质序列的比对结果及其分析
• 5.3 算法比较
• 5.3.1 PSAIGA 与基于遗传算法的序列比对方法PSAGA 的比较
• 5.3.2 PSAIGA 与NW 算法的比较
• 5.4 小结
• 结论
• 参考文献
• 致谢
• 在校期间公开发表论文及著作情况