支持大规模压缩序列的在线子串查询处理与优化技术

《支持大规模压缩序列的在线子串查询处理与优化技术》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号UDC密级学位论文支持大规模压缩序列的在线子串查询处理与优化技术作者姓名：指导教师：申请学位级别：学科专业名称：论文提交日期：学位授予日期：评阅人：李中博杨晓春教授东北大学计算机软件与理论研究所硕士学科类别：工学计算机应用技术2010年6月论文答辩日期：2010年7月2010年月答辩委员会主席：申德荣申德荣石祥滨东北大学2010年6月AThesisfortheDegreeofMasterinComputerSoftwareandTheoryProcessingandOptimizationTechniquesforOnline

2、SearchingSubsequencesonLargeCompressedSequencesByLiZhongboSupervisor：ProfessorYANGXiaochunNortheasternUniversityJune2010独创性声明本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢意。学位论文作者签名：如舟日期：矽f

3、9刍’，7目‘司学位论文版权使用授权书本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关数据库进行检索、交流。作者和导师同意网上交流的时间为作者获得学位后：半年口一年口一年半口两年√学位论文作者签名：套婶傅签字日期：沙／ro．7、f导师签名：档迈勿彖签字日期：阳知．7。莎东北大学硕士学位论文摘要支持大规模压缩序列的在线子串查询处理与优化技术摘要随着社会的进步和科学的发展，信息数据

4、量呈爆炸性增长，特别是基因序列这样的数据，其增长速度已经超出了人们的想象，给数据存储和传输造成了很大的压力，各种压缩技术被提出来解决这样的问题。在压缩序列上进行子串查询处理对于基因序列分析和关键字搜索等实际应用非常有意义。这些序列数据往往以压缩形式存储，给子串查询造成一定的难度，使得该研究领域面临着巨大的挑战。本文所研究的内容是基于最近提出的一种无损压缩技术，对于多个非常相似的字符序列，只需保留一个参照序列，然后利用参照序列上的编辑操作来编码这些相似序列与参照序列的差异。该技术对于基因这种大规模的字符序列能够起到非常好的压缩效果。这

5、种压缩技术是新颖而且重要的，那么如何在这种大规模压缩序列上进行在线子串查询处理是本文要解决的问题。针对上述大规模无损压缩序列，本文针对参照序列是否在线被处理这两种情况，分别提出相应的在线子串查询处理与优化技术。在未索引参照序列的情况下，通过改进经典的BM算法，提出了支持单压缩序列的子串查询算法。利用多个压缩序列在参照序列上拥有许多公共片段的特点，进而提出了支持多压缩序列的子串查询算法。在索引参照序列的情况下，通过建立一个基于q．gram的倒排表索引，提出一个基本的子串查询算法。针对其不足，采用对编辑操作的过滤技术，进而又提出了一个优

6、化查询算法。通过在一个基因数据集上的实验，显示出所提出的技术能够高效地支持大规模无损压缩序列的子串查询处理。关键词：压缩序列；在线查询；子串查询；索引；过滤东北大学硕士学位论文AbstmctPrecessingandOptimizationTechniquesforOnlineSearchingSubsequencesonLargeCompressedSequencesAbstractWiththedevelopmentofsocietyandscience，theamountofinformationdataincreasesex

7、ponentially,especiallygenomicsequencesdata，itsincreasingrateisincredible，whichposesabigpressureonthestorageandtransmissionofdata,SOtherearemanycompressiontechniquesproposedtosolvethisproblem．Searchingsubsequencesoncompressedsequencesisveryimportantinpracticalapplicatio

8、nssuchasgenomicsequenceanalysisandkeywordsearching，wheretheirsequencedataisalwayskeptcompressedinordertoreducethegrea