学位论文 > 优秀研究生学位论文题录展示

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

作　者: 范慧
导　师: 吴蓉晖
学　校: 湖南大学
专　业: 计算机科学与技术
关键词: 生物信息学双序列比对多序列比对遗传算法智能算子方差进化周期
分类号: TP18
类　型: 硕士论文
年　份: 2012年
下　载: 41次
引　用: 0次
阅　读: 论文下载

内容摘要

随着生物分子序列数据的快速增长及人类基因组计划的实施，生物信息学逐渐发展起来。在生物信息学中，序列比对问题是生物信息学中最基本的也是最重要的问题之一，通过序列比对可以对序列进行分析，从而预测生物序列的结构和功能。由于序列比对问题可以看成是一个组合优化问题，而遗传算法是一种求解大规模问题的全局性优化算法，因此可以用来解决序列比对问题。本文在基于遗传算法解决双序列比对和多序列比对的问题上进行了研究。对序列比对问题研究之后提出了一种改进的遗传算法来解决序列比对问题。针对遗传算法在解决序列比对问题时容易出现的陷入局部最优、不稳定性等问题，本文进行了三个方面的改进：第一，在遗传算子方面使用了智能遗传算子和普通遗传算子相结合的方法，智能遗传算子的设计是为了能使算法迅速收敛到最优解的区域，并能收敛到最优解，而普通遗传算子的作用是为了能够产生新的基因，从而保持种群的多样性；第二，引入了对种群多样性进行评估的性能指标，即利用方差对种群的多样性进行评估，从而根据种群的多样性选择不同的智能变异率和普通变异率，这样就能够时刻保证种群的多样性，从而避免算法陷入局部最优；第三，停止准则引入了进化周期的概念，通过对当前周期内的最优解与上一周期的最优解之差和阈值的比较来确定周期数是否要加一，当进化周期数达到指定值时输出最优结果，这样做避免了种群过早的陷入局部最优及改善了算法的稳定性。通过上面三种策略的加入，使得改进后的遗传算法在解决序列比对问题上得到了很好的效果。为了验证此方法的有效性，通过实验将这种改进的遗传算法分别应用在双序列比对和多序列比对上，并将得到的结果在字符的匹配列数和适应度值上与经典算法T-COFFEE进行比较，从实验结果和实验分析中可以看出此方法的有效性。

全文目录

摘要  4-5
Abstract  5-7
目录  7-9
插图索引  9-10
附表索引  10-11
第1章绪论  11-15
  1.1 研究意义及背景  11-12
  1.2 国内外的研究现状  12-13
  1.3 本文的工作  13-14
  1.4 本文的结构安排  14-15
第2章序列比对概述  15-32
  2.1 序列比对的基础知识  15-26
    2.1.1 序列的同源性和相似性  15-16
    2.1.2 插入、删除、替代、重排事件  16
    2.1.3 空位罚分  16-18
    2.1.4 相似性打分矩阵  18-22
    2.1.5 目标函数  22-23
    2.1.6 序列比对问题描述  23-26
  2.2 双序列比对算法  26-27
    2.2.1 动态规划算法  26-27
    2.2.2 基于点阵图的双序列比对算法  27
  2.3 多序列比对算法  27-31
    2.3.1 精确比对算法  28-29
    2.3.2 渐进比对算法  29-30
    2.3.3 迭代算法  30-31
  2.4 小结  31-32
第3章基于遗传算法的序列比对算法的改进研究  32-48
  3.1 遗传算法概述  32-34
  3.2 基于遗传算法的序列比对算法的改进算法  34-47
    3.2.1 改进算法的思想和流程  35-37
    3.2.2 改进算法的操作设计  37-47
  3.3 小结  47-48
第4章实验与结论分析  48-58
  4.1 实验参数设置  48
  4.2 双序列比对实验  48-52
    4.2.1 实验数据  48
    4.2.2 实验结果和分析  48-52
  4.3 多序列比对实验  52-56
    4.3.1 实验数据  52
    4.3.2 实验结果和分析  52-56
  4.4 实验结论  56-57
  4.5 小结  57-58
结论  58-60
参考文献  60-65
致谢  65-66
附录 A 攻读硕士学位期间发表的论文  66-67
附录 B 攻读硕士学位期间所参与的项目  67-68

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

内容摘要

全文目录

相似论文