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

DNA序列中串联重复体查找算法研究

作　者: 王敬艳
导　师: 霍红卫
学　校: 西安电子科技大学
专　业: 计算机软件与理论
关键词: 串联重复体 LZ分解后缀树进化串联重复体
分类号: R346
类　型: 硕士论文
年　份: 2009年
下　载: 21次
引　用: 0次
阅　读: 论文下载

内容摘要

在DNA序列分析中,串联重复体查找是一个重要的基础性问题。人类DNA序列50%以上是由串联重复体组成的。串联重复体在基因表达、调控和遗传等方面起着十分重要的作用,同时它是产生多种疾病的病因。另外以串联重复体为基础的“DNA指纹技术”在法医学等领域广泛应用。因此关于串联重复的研究具有十分重要的意义。本文主要研究串联重复体查找算法。1)针对精确串联重复体提出了一种基于LZ分解查找串联重复体的算法。对于存储在后缀树上的字符串S,该算法能在线性的时间找到所有出现在S中的串联重复体。为了进一步提高算法的效率,我们对后缀树进行了改进,给中间节点加入了叶子信息数组,这样就避免了算法对子树的遍历。2)引入了一种新类型的近似串联重复体—进化串联重复体,由于以前提出的算法都不能解决进化串联重复体的查找问题,因此提出了基于海明距离的查找算法。对于给定的重复单元的长度l,该算法的时间复杂度为O(ln2),解决了进化串联重复体的查找问题。为了说明算法的正确性和有效性,本文将这两种分别应用于实际的基因组DNA序列,结果表明基于LZ分解的查找串联重复体方法能找到更多的串联重复体,基于海明距离的查找方法则解决了进化串联重复体的查找问题。

全文目录

摘要  3-4
Abstract  4-7
第一章绪论  7-13
  1.1 引言  7-8
  1.2 重复体查找的生物意义及研究现状  8-11
    1.2.1 重复体查找的生物意义  8-9
    1.2.2 重复体查找的研究现状  9-11
  1.3 本文的研究工作  11
  1.4 本文的章节安排  11-13
第二章重复体查找方法  13-19
  2.1 重复体查找的数据结构  13-16
    2.1.1 后缀树  13-14
    2.1.2 改进的后缀树  14-16
  2.2 重复体查找算法介绍  16-18
    2.2.1 Tandem repeat finder  16-17
    2.2.2 REPuter  17
    2.2.3 ML算法  17-18
  2.3 本章小结  18-19
第三章基于LZ分解的串联重复体查找方法  19-31
  3.1 基本概念  19-20
  3.2 基于LZ分解的串联重复体查找方法  20-26
    3.2.1 LZ分解及串联重复体在LZ分解块上的性质  20-22
    3.2.2 查找最左覆盖集  22-24
    3.2.3 标注串联重复体  24
    3.2.4 得到Occurrence集  24-26
  3.3 算法描述  26-28
  3.4 算法分析  28-29
  3.5 实验结果分析  29-30
  3.6 本章小结  30-31
第四章基于海明距离查找进化串联重复体的算法  31-45
  4.1 基本概念  31-33
  4.2 基于海明距离查找进化串联重复体的算法  33-38
    4.2.1 计算等价类  33
    4.2.2 构造等价类图  33-35
    4.2.3 构造位置图  35-37
    4.2.4 求最大进化串联重复体  37-38
  4.3 HDETR算法描述  38-41
  4.4 算法分析  41
  4.5 实验结果分析  41-43
  4.6 本章小结  43-45
第五章结束语  45-47
致谢  47-49
参考文献  49-53
研究成果  53

DNA序列中串联重复体查找算法研究

内容摘要

全文目录

相似论文