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

生物信息学中的多序列比对与模体识别问题研究

作　者: 刘立芳
导　师: 王宝树；霍红卫
学　校: 西安电子科技大学
专　业: 计算机应用
关键词: 生物信息学多序列比对模体识别隐马尔可夫模型并行遗传算法 Gibbs抽样
分类号: Q811.4
类　型: 博士论文
年　份: 2006年
下　载: 652次
引　用: 1次
阅　读: 论文下载

内容摘要

基因组计划的实施,使序列数据激增,序列分析成为生物信息学的首要任务。序列比对与序列模体(motif)识别是进行生物序列分析的两个主要方法。本论文主要针对多序列比对问题和模体识别问题进行了方法上的研究。本文的主要工作和创新点如下:1、针对生物序列分析中的多序列比对问题,设计了求解多序列比对问题的混合遗传算法。首先采用SP记分函数作为个体的适应度函数,设计了4种遗传算子,对BAliBASE中Ref.1进行了测试,其结果表明该算法对等距蛋白质序列比对是有效的,其中部分比对结果优于ClustalX。2、为了进一步提高算法求解问题的范围及求解的精度,算法改用COFFEE函数作为个体的适应度函数,与之相应的软件称为PHGA-COFFEE,构造了6种遗传算子,特别是设计了2种新颖的变异算子,其中一种变异算子基于COFFEE的一致性信息设计,以改善算法的整体搜索能力;另一种变异算子基于动态规划方法设计,以增强其局部搜索能力。最后,通过对BAliBASE中144个测试例的测试,证明PHGA-COFFEE是有效的,与已有的算法相比,该算法对处于朦胧区和具有N/C末端延伸的序列比对问题有更强的问题求解能力。同时通过对算法并行化,其运行时间显著缩短。3、针对多序列比对中的Profile HMM的参数优化问题,提出了遗传算法与Baum-Welch(BW)算法相结合的混合遗传算法。通过实验分析,证明经过混合遗传算法的训练而得到的Profile HMM能更好地描述多序列比对,从而得到更加准确的比对结果。4、针对生物序列模体的识别问题,提出了一个新的混合Gibbs抽样识别算法。算法基于混合模体模型学习,采用贪心策略,通过似然度最大化,逐次将新的模体加入到混合模型中。算法中设计了位点抽样和模体抽样两种抽样方法,这两种抽样方法交替进行。为了加速搜索过程,对输入数据集采用了基于kd-trees的分层划分策略。实验结果表明,该算法对序列家族大量模体特征的识别具有显著优势,并且可建立更具统计特征的模体模型,从而提高序列分类的准确性。

全文目录

摘要  5-7
ABSTRACT  7-12
第一章绪论  12-26
  1.1 研究背景与现状  12-24
    1.1.1 生物序列分析的意义  12-13
    1.1.2 多序列比对问题及研究现状  13-18
    1.1.3 模体识别问题及研究现状  18-22
    1.1.4 生物序列数据库  22-24
    1.1.5 生物序列图标Logo  24
  1.2 本文的主要工作与内容安排  24-26
第二章多序列比对问题的遗传算法求解  26-54
  2.1 引言  26-41
    2.1.1 相似性记分矩阵  26-28
    2.1.2 空位罚分  28
    2.1.3 双序列比对  28-30
    2.1.4 多序列比对问题优化模型  30-34
    2.1.5 算法基础  34-41
  2.2 SP-GA ：基于SP 记分函数的遗传算法求解  41-45
    2.2.1 染色体编码  41
    2.2.2 交叉算子  41-42
    2.2.3 变异算子  42-43
    2.2.4 选择算子  43
    2.2.5 算法描述  43-44
    2.2.6 测试结果  44-45
  2.3 PHGA-COFFEE：基于COFFEE 记分函数的遗传算法求解  45-52
    2.3.1 种群初始化  45-46
    2.3.2 变异算子  46-48
    2.3.3 迁移算子  48
    2.3.4 双序列比对库的生成  48
    2.3.5 算法描述  48
    2.3.6 测试结果  48-52
  2.4 小结  52-54
第三章 Profile HMM 的混合遗传算法优化  54-78
  3.1 引言  54-60
    3.1.1 隐马尔可夫模型  54-56
    3.1.2 隐马尔可夫模型的计算  56-60
  3.2 序列谱隐马尔可夫模型Profile HMM  60-66
    3.2.1 Profile HMM 的结构  60-61
    3.2.2 基于已有Profile HMM 的多序列比对  61-63
    3.2.3 Profile HMM 的从头训练  63-65
    3.2.4 基于Profile HMM 的从头比对  65-66
  3.3 Profile HMM 的混合遗传算法优化  66-77
    3.3.1 染色体编码  66-67
    3.3.2 种群初始化  67
    3.3.3 适应度函数  67-68
    3.3.4 交叉算子  68
    3.3.5 变异算子  68-69
    3.3.6 计算中的数据稳定性问题  69-70
    3.3.7 概率参数估计的调整  70-71
    3.3.8 混合遗传算法HGA-HMM 描述  71-73
    3.3.9 实验结果  73-77
  3.4 小结  77-78
第四章生物序列模体的混合 Gibbs 抽样识别算法  78-100
  4.1 引言  78-80
    4.1.1 混合模体模型  78-80
    4.1.2 Gibbs 抽样算法  80
  4.2 混合Gibbs 抽样算法  80-98
    4.2.1 确立初始参数候选集  80-81
    4.2.2 位点抽样  81-84
    4.2.3 模体抽样  84-86
    4.2.4 侯选集的修改  86
    4.2.5 混合Gibbs 抽样算法——MSAM  86
    4.2.6 算法复杂性分析  86-88
    4.2.7 实验结果  88-98
  4.3 小结  98-100
结束语  100-102
致谢  102-104
参考文献  104-112
附录1  112-114
附录2  114-116
附录3  116-118
在读期间撰写（发表）的论文目录  118-119
在读期间参加的科研项目  119

生物信息学中的多序列比对与模体识别问题研究

内容摘要

全文目录

相似论文