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

生物序列索引结构构造算法研究

作　者: 黄影
导　师: 霍红卫
学　校: 西安电子科技大学
专　业: 计算机软件与理论
关键词: 后缀树后缀排序后缀数组最长公共前缀自顶向下
分类号: TP391.3
类　型: 硕士论文
年　份: 2009年
下　载: 3次
引　用: 0次
阅　读: 论文下载

内容摘要

生物信息学是在生命科学的研究中,以计算机为工具对生物信息进行储存、检索和分析的科学。如何快速而有效地对生物数据进行处理,从而发现蕴涵于其中的丰富生物知识,是生物信息学研究的重要内容。其中,生物序列的索引技术是目前的一个研究热点。本文主要是对生物序列的索引结构进行研究,重点研究了索引结构的构造算法。首先介绍了索引技术的发展现状,阐述了后缀树和后缀数组索引结构的定义以及相关概念,总结了国内外现有的索引结构构造算法。然后着重介绍并分析了基于后缀数组和后缀树等数据结构的索引结构构造算法。对于较小的序列来说,后缀树索引是一种很好的解决办法,但由于存在“内存瓶颈”问题,不适合大的序列；而后缀数组则需较少的存储空间,但在数据搜索方面的效率却较低。由此,本文基于自顶向下的后缀树构造思想,提出了一种基于后缀树的索引结构分步构造算法。首先对所有后缀按照字母表顺序进行排序,再求出有序相邻后缀之间的最长公共前缀,最后根据后缀顺序和最长公共前缀构造后缀树。该算法不但可以在线性时间内构造后缀树,而且不需要使用后缀链,在一定程度上缓解了“内存瓶颈”问题。

全文目录

摘要  3-4
Abstract  4-7
第一章绪论  7-11
  1.1 研究背景  7-8
    1.1.1 研究动机与意义  7-8
    1.1.2 生物序列上的索引技术  8
  1.2 本文研究工作  8-9
  1.3 本文组织结构  9-11
第二章生物序列索引结构概述  11-23
  2.1 后缀树索引结构  11-13
  2.2 后缀数组索引结构  13-14
  2.3 其他索引结构  14-15
  2.4 后缀树与后缀数组比较  15
  2.5 索引结构的存储  15-17
    2.5.1 直接存储方式  15-16
    2.5.2 优化储存方式  16-17
  2.6 生物序列的搜索技术  17-18
    2.6.1 精确字符串匹配  17
    2.6.2 近似字符串匹配  17-18
  2.7 索引结构的应用  18-21
    2.7.1 基于后缀树的多序列比对算法  18-19
    2.7.2 QUASAR算法  19-21
  2.8 本章小结  21-23
第三章常见的索引结构构造算法  23-35
  3.1 基于后缀数组的索引结构构造算法  23-28
  3.2 基于后缀树的索引结构构造算法  28-32
    3.2.1 后缀树相关术语  28
    3.2.2 Ukkonen后缀树构造  28-31
    3.2.3 自顶向下的后缀树构造算法  31-32
  3.3 本章小结  32-35
第四章分步的后缀树索引结构构造算法  35-43
  4.1 对文本中的所有后缀进行排序  35-38
  4.2 求相邻后缀之间的最长公共前缀  38-39
  4.3 构造后缀树  39-40
  4.4 算法分析及实验结果  40-41
  4.5 本章小结  41-43
第五章总结与展望  43-45
致谢  45-47
参考文献  47-51
研究成果  51

相似论文

基于串核的蛋白质分类算法的研究与实现,TP301.6
面向短消息文本的聚类技术研究与应用,TP391.1
XML重复对象检测系统的设计与实现,TP311.11
基因组比对中若干改进算法研究,TP301.6
基因组中最大唯一匹配的查找算法研究,TP301.6
Web中文文本聚类研究,TP391.1
复杂产品分区协同设计平台的研究与实现,TP391.72
DNA序列中串联重复体查找算法研究,R346
基于Web页面嵌套模式的包装器生成系统的设计与实现,TP393.092
基于网络的P2P蠕虫检测系统的研究与实现,TP393.08
基于锚点的多基因组序列比对算法,TP301.6
基于元素增长搜索策略的频繁闭模式挖掘算法的研究与实现,TP311.13
基于FPGA的数字下变频器的设计与实现,TN773
P2P网络深度包业务识别（DPI）方法的改进,TP393.02
基于自顶向下技术的工程机械Digital Prototyping设计方法及应用,TP391.72
基于Pro/ENGINEER的常用机构库研究与开发,TP391.72
2.45GHz RFID加密卡的研究与开发,TP391.44
基于后缀数组的字符串模式查找的算法,TP301.6
基于COM组件技术的内燃机连杆组CAD系统开发,TP391.72
基于后缀数组聚类的元搜索引擎的设计与实现,TP391.3