后缀树论文：生物序列索引结构构造算法研究

《后缀树论文：生物序列索引结构构造算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、后缀树论文：生物序列索引结构构造算法研究【中文摘要】生物信息学是在生命科学的研究中,以计算机为工具对生物信息进行储存、检索和分析的科学。如何快速而有效地对生物数据进行处理,从而发现蕴涵于其中的丰富生物知识,是生物信息学研究的重要内容。其中,生物序列的索引技术是目前的一个研究热点。本文主要是对生物序列的索引结构进行研究,重点研究了索引结构的构造算法。首先介绍了索引技术的发展现状,阐述了后缀树和后缀数组索引结构的定义以及相关概念,总结了国内外现有的索引结构构造算法。然后着重介绍并分析了基于后缀数组和后缀树等数据结构的索引结构构造算法。对于较小的序

2、列来说,后缀树索引是一种很好的解决办法,但由于存在“内存瓶颈”问题,不适合大的序列；而后缀数组则需较少的存储空间,但在数据搜索方面的效率却较低。由此,本文基于自顶向下的后缀树构造思想,提出了一种基于后缀树的索引结构分步构造算法。首先对所有后缀按照字母表顺序进行排序,再求出有序相邻后缀之间的最长公共前缀,最后根据后缀顺序和最长公共前缀构造后缀树。该算法不但可以在线性时间内构造后缀树,而且不需要使用后缀链,在一定程度上缓解了“内存瓶颈”问题。【英文摘要】Bioinformaticsisthescienceofusingcomputertechno

3、logytostore,retrieveandanalyzebiologicalinformationinthefieldoflifesciences.Todeveloprapidandeffectivecomputeralgorithmtofindknowledgefromverylargebiologicaldataisthemainresearchwork.Thisthesismainlyfocusesonthestudyofsuffixtreeandsuffixarrayindextechnicaldealingwithbio-seq

4、uences.First,indexstructureofbio-sequencesisdescribed,thenseveralalgorithmsofindesstructureconstructionbasedonthe...【关键词】后缀树后缀排序后缀数组最长公共前缀自顶向下【英文关键词】suffixtreesuffixsortingsuffixarraylongestcommonprefixtop-down【目录】生物序列索引结构构造算法研究摘要3-4Abstract4第一章绪论7-111.1研究背景7-81.1.1研究动机与意义7

5、-81.1.2生物序列上的索引技术81.2本文研究工作8-91.3本文组织结构9-11第二章生物序列索引结构概述11-232.1后缀树索引结构11-132.2后缀数组索引结构13-142.3其他索引结构14-152.4后缀树与后缀数组比较152.5索引结构的存储15-172.5.1直接存储方式15-162.5.2优化储存方式16-172.6生物序列的搜索技术17-182.6.1精确字符串匹配172.6.2近似字符串匹配17-182.7索引结构的应用18-212.7.1基于后缀树的多序列比对算法18-192.7.2QUASAR算法19-212.

6、8本章小结21-23第三章常见的索引结构构造算法23-353.1基于后缀数组的索引结构构造算法23-283.2基于后缀树的索引结构构造算法28-323.2.1后缀树相关术语283.2.2Ukkonen后缀树构造28-313.2.3自顶向下的后缀树构造算法31-323.3本章小结32-35第四章分步的后缀树索引结构构造算法35-434.1对文本中的所有后缀进行排序35-384.2求相邻后缀之间的最长公共前缀38-394.3构造后缀树39-404.4算法分析及实验结果40-414.5本章小结41-43第五章总结与展望43-45致谢45-47参考文

7、献47-51研究成果51