论文摘要
生物信息学是由生物学、应用数学和计算机科学相互交叉所形成的新型学科,是当今生命科学和自然科学的重大前沿领域之一。其中,生物序列比对是生物信息学中一个最基本的研究方法,而多序列比对又是生物序列比对的最基本的任务,如何获得比对质量更好、时间空间效率更高的多序列比对算法是生物信息学研究的一个重要的课题。多序列比对是NP完全问题,动态规划算法是其基本算法,它可以找到一个得分最高(或代价最小)的序列对比排列,但当序列数量增加时,计算量将呈指数增长。在实际操作中,算法都会在计算速度和获得最佳比对值之间寻求平衡。一个有效的方法是用遗传算法这种近似算法求解,但遗传算法有着易早熟、稳定性差等缺点,所以本文提出一种改进的自适应遗传算法,采用了适应度值的标定,并在进化过程中实现了群体多样性,同时利用构造神经元激活函数最常用的sigmoid函数,对交叉率和突变率进行了优化,实现了交叉率和突变率的非线性自适应调整,提高了算法的寻优能力和稳定性。位爬山算法是一种局部搜索算法,有着较强的局部求精能力,适用于基于二进制编码的函数优化和组合问题,由于遗传算法的宏观搜索能力大于局部求精能力,所以本文在改进的自适应遗传算法后期采用位爬山策略来提高解的精度。本文根据改进的自适应遗传算法设计并开发了序列比对分析程序,并将其应用于具体的核酸多序列及蛋白质多序列,通过得到的实验数据,将新算法和标准遗传算法及传统自适应遗传算法实现的多序列比对算法进行了比较和分析,发现新算法改善了多序列比对的质量,提高了算法的稳定性。
论文目录
摘要Abstract引言第一章 生物信息学基础1.1 生物信息学概述1.2 基因组序列分析1.3 核酸序列数据库1.3.1 GenBanK1.3.2 EMBL1.3.3 DDBJ第二章 生物序列比对基础2.1 序列比对概述2.2 空位罚分与相似性得分矩阵2.2.1空位罚分2.2.2 相似性得分矩2.2.2.1 核酸得分矩阵2.2.2.2 蛋白质得分矩阵2.3 SP 模型2.4 双序列比对2.5 多序列比对2.6 几种常见的多序列比对算法2.6.1 动态规划多序列比对算法2.6.2 树形比对算法和星形比对算法2.6.2.1 树形比对算法2.6.2.2 星形比对算法2.6.3 ClustalW 算法第三章 遗传算法基础3.1 遗传算法发展史3.2 遗传算法的一个简单例子3.3 遗传算法的模式理论和积木块假设3.3.1 遗传算法的模式理论3.3.2 遗传算法的积木块假3.4 群体规模对遗传算法的影响3.5 遗传算法的编码与适应度函数3.5.1 编码3.5.2 适应度的计算3.6 遗传算法的主要算子及终止条件3.6.1 复制3.6.2 交叉3.6.3 突变3.6.4 算法的终止条件3.7 遗传算法的工作步骤及流程3.7.1 遗传算法的工作步骤3.7.2 遗传算法的流程第四章 改进的自适应遗传算法4.1 自适应遗传算法(Adaptive GA)4.2 改进的自适应遗传算法4.2.1 抑制算法陷入局部收敛采用的改进方4.2.1.1 早熟标志的建立4.2.1.2 群体多样化4.2.1.3 适应值标定4.2.2 交叉率和突变率的非线性自适应调整4.2.3 改进的自适应遗传算法的工作步骤和算法流程4.2.3.1 改进的自适应遗传算法的工作步骤4.2.3.2 改进的自适应遗传算法的算法流程4.3 实验及分析4.3.1 测试函数4.3.2 算法性能4.3.3 算法性能评价第五章 位爬山策略与改进自适应遗传算法的结合5.1 位爬山算法5.1.1 位爬山算法简介5.1.2 位变异顺序按随机位序列集合进行的位爬山5.1.3 位变异顺序按随机位序列集合进行的位爬山改进5.2 位爬山法与改进自适应遗传算法的结合与实现5.2.1 位爬山法与改进自适应遗传算法的结合5.2.2 算法实现第六章 改进的自适应遗传算法在多序列比对中的分析应用6.1 改进的自适应遗传算法在多序列比对中的分析应用6.1.1 改进的自适应遗传算法的编码方式6.1.2 适应度函数和遗传操作6.1.2.1 适应度函数6.1.2.2 遗传操作6.1.3 实验步骤6.2 实验分析及其与其它遗传算法的比较6.2.1 实验数据6.2.2 开发环境6.2.3 程序实现6.2.4 实验数据6.2.5 实验结果分析结论附录:空位插入程序及SP 打分程序(核酸序列)参考文献后记
相关论文文献
标签:自适应遗传算法论文; 生物序列比对论文; 多序列比对论文;