生物信息学中序列比对方法的研究

论文摘要

序列比对是生物信息学中基本的信息处理方法,对于发现核酸和蛋白质序列上的功能、结构和进化的信息具有非常重要的意义。随着生物序列数据库中数据的快速增长,开发具有高度敏感性和效率的算法就显得非常迫切。免疫遗传算法将遗传算法与免疫原理结合起来考虑,在传统遗传算法的框架之上,引入了免疫系统的免疫调节机制、多样性保持策略诸多特性等,有效地防止了搜索过程中的未成熟收敛等问题,是一种更加有效的优化算法。本文首先介绍了生物信息学发展、研究内容,以及序列比对研究现状和相关算法的问题,然后详细的描述了序列比对中空位罚分策略、相似性记分矩阵和目标函数对比对结果的影响。根据比对序列的数量,文章又分类介绍了双序列比对和多序列比对相关的标准比对算法,系统地论述了双序列比对中的点阵图算法、动态规划算法和多序列比对中的渐进比对算法及基于迭代策略的多序列比对算法,并阐述了相关经典算法,如渐进比对CLUSTALW算法和迭代改进的遗传多序列比对算法SAGA的原理。在对序列比对算法的研究以及遗传算法和免疫遗传算法原理的分析的基础上,文章提出并设计了免疫遗传多序列比对算法,算法根据生物免疫系统的抗原识别、抗体的多样性保持策略和免疫记忆的特性,将生物系统免疫思想引入到遗传算法多序列比对中,通过计算抗体之间的亲和度及基于矢量距的免疫选择方法来促进和抑制抗体,既保留了全体中的较优抗体又保证了抗体的多样性,避免了在用遗传算法进行序列比对过程中遇到的搜索进化过早收敛的问题,算法得到全局最优解,同时与文献中基于信息熵的免疫遗传算法比较,本文算法减少了先验参数的输入、提高了收敛速度。文章最后通过实验对算法进行了可行性和有效性验证,取得了较好的结果。

论文目录

• 摘要
• Abstract
• 1 引言
• 1.1 研究背景与意义
• 1.1.1 生物信息学
• 1.1.2 序列比对的研究意义
• 1.2 研究现状及算法问题
• 1.2.1 研究现状
• 1.2.2 算法问题
• 1.3 文章结构与内容安排
• 2 生物序列比对基础
• 2.1 生物基础知识
• 2.2 序列比对的分类数学描述
• 2.2.1 双序列比对
• 2.2.2 多序列比对
• 2.3 序列比对的相关概念
• 2.3.1 空位罚分概念及策略
• 2.3.2 相似替换矩阵
• 2.3.3 目标函数
• 2.3.4 多序列比对结果的评判标准
• 3 生物序列比对算法
• 3.1 双序列比对算法
• 3.1.1 双序列比对的点阵图法
• 3.1.2 动态规划算法
• 3.2 多序列比对算法
• 3.2.1 渐近比对算法
• 3.2.2 迭代算法
• 4 免疫遗传算法原理
• 4.1 遗传算法及其缺陷
• 4.1.1 遗传算法原理及流程
• 4.1.2 遗传算法基本要素
• 4.1.3 基本遗传算法的缺陷
• 4.2 免疫遗传算法的原理及方法
• 4.2.1 生物免疫学基本原理
• 4.2.2 免疫系统特点及对改进遗传算法的启示
• 4.2.3 免疫遗传算法
• 5 改进免疫遗传算法的序列比对算法的分析设计
• 5.1 改进免疫遗传序列比对算法的设计
• 5.1.1 编码设计
• 5.1.2 初始群体的产生
• 5.1.3 抗体适应度计算与免疫选择
• 5.1.4 遗传算子设计
• 5.1.5 记忆库的设计及算法终止准则
• 5.2 算法的实现
• 5.2.1 测试环境与用例
• 5.2.2 相关参数设置
• 5.2.3 实验结果及分析
• 6 总结与展望
• 参考文献
• 在读期间发表的学术论文
• 作者简历
• 致谢