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

基于分步查找的高效复合模式查找算法

作　者: 胡慧泽
导　师: 霍红卫
学　校: 西安电子科技大学
专　业: 计算机软件与理论
关键词: 复合模式错配树二分体分步查找栈式节点存储
分类号: Q811.4
类　型: 硕士论文
年　份: 2010年
下　载: 6次
引　用: 0次
阅　读: 论文下载

内容摘要

复合模式查找是生物信息学中模式发现问题的一个新的研究领域,而寻求效率更高,精度更高的复合模式查找算法将是复合模式研究领域的长期热点与目标。本文对此进行了深入的研究和探讨。本文深入研究了当今国际上的各种复合模式查找算法,系统地阐述了最具代表性的MITRA-Dyad算法和RISO算法。同时,由于本文实现的算法需要用到单分体模式查找算法,故对当今流行的单分体模式查找算法进行了简要的介绍,分析了各算法的优缺点,并对本文使用到的MITRA-Count单分体模式查找算法进行了系统阐述。ECOMP算法是一种使用错配树数据结构的复合模式分步查找算法。本文针对复合模式的一种简单形式—二分体模式的特点进行研究,通过对ECOMP算法的理论分析和实验测试,证明ECOMP算法可以应用于实际的复合模式查找问题。同时,由于ECOMP算法的第一部分MITRA-Count算法的设计机制,导致其运行速度和空间占用方面都存在低效性的特点,本文将对错配树的递归遍历方式改进为基于栈式节点存储的非递归遍历方式,从而提高了MITRA-Count的运行速度,减少了空间占用。另一方面,本文还对ECOMP算法的第二部分,即将单分体模式组合为复合模式的部分进行了空间优化,减少了算法实现时的内存开销,并通过模拟数据和真实数据的测试证明了本文对ECOMP算法改进的有效性。

全文目录

摘要  3-4
Abstract  4-7
第一章绪论  7-13
  1.1 引言  7-8
  1.2 模式查找问题概述  8-9
  1.3 复合模式查找问题概述  9-10
  1.4 本文所做的工作  10-13
第二章复合模式查找基础  13-27
  2.1 单分体模式问题描述  13-16
    2.1.1 单分体模式问题定义  13-15
    2.1.2 单分体模式查找问题研究现状  15-16
  2.2 复合模式问题定义  16-19
  2.3 复合模式查找问题研究现状  19-25
    2.3.1 MITRA-Dyad算法  20-22
    2.3.2 RISO算法  22-25
  2.4 本章小结  25-27
第三章 ECOMP算法研究  27-43
  3.1 MITRA-Count算法  28-36
    3.1.1 错配树  28-30
    3.1.2 MITRA-Count算法概述  30-35
    3.1.3 MITRA-Count实现  35-36
  3.2 ECOMP算法  36-40
    3.2.1 ECOMP算法概述  36-40
    3.2.2 ECOMP实现  40
  3.3 复杂度分析  40-42
  3.4 本章小结  42-43
第四章改进的ECOMP算法  43-51
  4.1 MITRA-Count实现改进  43-49
  4.2 ECOMP实现改进  49-50
  4.3 本章小结  50-51
第五章实验结果与分析  51-57
  5.1 模拟数据实验结果  51-53
  5.2 真实数据实验结果  53-54
  5.3 实验结果分析  54-55
  5.4 本章小结  55-57
第六章结束语  57-59
致谢  59-61
参考文献  61-63

基于分步查找的高效复合模式查找算法

内容摘要

全文目录

相似论文