基于遗传算法的多序列比对算法研究

论文摘要

序列比对是生物信息学中一项重要的基础性研究课题,而多序列比对又是序列比对中最重要、也是最有挑战性的任务之一。研究多序列比对对于蛋白质的功能域识别、二级结构预测、基因识别以及分子系统发育分析等具有重要的意义。由于多序列比对问题是一个NP完全问题,如何求解至今仍是生物信息学中的一个难题。本文主要研究了遗传算法在多序列比对中的应用,分别提出多种群遗传算法和小生境遗传算法解决多序列比对问题,为解决生物多序列比对问题提供了新的途径。本文主要完成了以下两个方面的工作：第一针对传统遗传算法在多序列比对后期种群多样性差、容易陷入局部最优解等问题,本文提出了一种多种群遗传算法。利用多种群方法以及迁移策略对标准遗传算法进行改进,采用单向环拓扑结构连接各子群,随机迁移策略增加种群的多样性,并利用多序列比对结果中空位很少单独出现的特点设计了-种新的突变算子,以增强算法的局部搜索能力。随后利用该算法对基准多序列比对库BAliBASE1.0多条序列进行了比对测试,并且分析了各算法对不同测试集的优劣,实验结果表明了算法的有效性。第二为了进一步提高算法的寻优能力及种群的多样性,本文在上一算法的基础上引入了一种基于罚函数的小生境技术。基于罚函数的小生境遗传算法在多序列比对中的应用主要解决了三个方面的问题：多序列个体两两之间的相似度计算、罚函数的选取和指定距离L的选取对算法的影响,并且在各种群中以各自不同的突变概率进化,可以很好地保持种群的多样性。随后利用该算法对基准多序列比对库BAliBASE1.0多条序列进行了比对测试,并综合了上一算法的实验结果进行比较分析,结果表明相比于第三章的算法,基于罚函数的小生境遗传算法具有更好的寻优能力。

论文目录

• 摘要
• Abstract
• 目录
• 插图索引
• 附表索引
• 第1章 绪论
• 1.1 项目来源
• 1.2 研究背景和意义
• 1.3 国内外研究现状与发展趋势
• 1.3.1 生物信息处理
• 1.3.2 生物序列比对的研究概况
• 1.4 本文的工作
• 1.5 本文结构
• 第2章 生物序列比对基础
• 2.1 序列比对的相关概念
• 2.1.1 序列比对描述
• 2.1.2 空位罚分和替换矩阵
• 2.1.3 目标函数
• 2.1.4 多序列比对的评判标准
• 2.2 序列比对的算法介绍
• 2.2.1 双序列比对算法
• 2.2.2 多序列比对算法
• 2.3 小结
• 第3章 多种群遗传算法在多序列比对中的应用
• 3.1 遗传算法
• 3.1.1 遗传算法概述
• 3.1.2 遗传算法原理及流程
• 3.2 多种群遗传算法在多序列比对中的应用
• 3.2.1 编码方法
• 3.2.2 遗传算子
• 3.2.3 选择算子
• 3.2.4 迁移算子
• 3.2.5 算法描述
• 3.2.6 测试结果及分析
• 3.3 小结
• 第4章 基于罚函数的小生境遗传算法的多序列比对
• 4.1 引言
• 4.2 小生境技术
• 4.3 基于罚函数的排挤小生境遗传算法在多序列比对中的应用
• 4.4 实验结果分析
• 4.5 小结
• 结论
• 参考文献
• 致谢
• 附录A 攻读学位期间所发表的学术论文目录