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

基于三阶马尔科夫模型和最大流的模体识别算法

作　者: 谢玲艳
导　师: 霍红卫
学　校: 西安电子科技大学
专　业: 计算机软件与理论
关键词: PSSM 模体识别三阶马尔科夫模型最大流最大密度子图
分类号: TP301.6
类　型: 硕士论文
年　份: 2010年
下　载: 54次
引　用: 0次
阅　读: 论文下载

内容摘要

DNA模体识别问题是生物信息学研究的最核心的问题之一。模体蕴含着丰富的生命特征信息。模体识别技术的出发点是找出序列间的相似片段,通过这些相似片段发现基因的表达调控规律,进而揭示生命的奥秘。本文首先介绍了模体识别问题的研究现状,包括两类模体识别问题的解决方法——基于枚举的方法和基于局部搜索的方法、PSSM模型及模体评分标准。这两类方法有个共同的特点：假定模体中的碱基之间是相互独立、互不依赖的。但已有证据证明了模体中碱基之间是相互依赖的。针对这个问题,本文使用了三阶马尔科夫模型表示模体中碱基之间的依赖关系。首先本文算法将输入序列转换成图,然后使用最大流算法搜索图的最大密度子图,简称MDS,并用最大密度子图表示识别出的模体,其时间复杂度是多项式的。

全文目录

摘要  3-4
Abstract  4-7
第一章绪论  7-13
  1.1 引言  7-8
  1.2 模体识别简介及相关概念  8-10
    1.2.1 模体  8-9
    1.2.2 模体的表示方法  9-10
    1.2.3 模体识别问题  10
  1.3 本文所做的工作  10-13
第二章模体识别问题的研究现状  13-21
  2.1 描述模体识别问题的方法  13-14
    2.1.1 基于枚举的方法  13-14
    2.1.2 基于局部搜索的方法  14
  2.2 常见模体模型  14-15
  2.3 模体评分标准  15-17
    2.3.1 信息容量  15-16
    2.3.2 信息容量的P值方法  16-17
    2.3.3 一致性得分  17
    2.3.4 对数似然值  17
  2.4 研究现状存在的问题  17-19
  2.5 本章小结  19-21
第三章基于三阶马尔科夫模型和最大流的模体识别算法  21-43
  3.1 算法的提出  21-22
  3.2 TMMF模体识别算法描述  22-26
    3.2.1 TMMF模体识别算法  22-23
    3.2.2 算法中模体的表示形式  23-24
    3.2.3 密度函数的选择  24-26
  3.3 构造碱基序列加权图  26-35
    3.3.1 碱基的编码方式  27-28
    3.3.2 k-mer转换成图中顶点的方法  28-29
    3.3.3 碱基之间依赖关系的解决方法  29-32
    3.3.4 背景模型的计算  32-33
    3.3.5 k-mer之间相似性的定义方法  33-35
  3.4 求解最大密度子图  35-41
    3.4.1 FIFO最大流算法  36-40
    3.4.2 最小割原理及实现方法  40-41
    3.4.3 重新创建图方法  41
  3.5 算法时间复杂度分析  41-42
  3.6 本章小结  42-43
第四章实验结果与分析  43-47
  4.1 实验结果  43-45
  4.2 实验结果的分析  45
  4.3 本章小结  45-47
第五章结束语  47-49
致谢  49-51
参考文献  51-54

基于三阶马尔科夫模型和最大流的模体识别算法

内容摘要

全文目录

相似论文