生物序列及其索引的压缩存储技术的研究与实现

《生物序列及其索引的压缩存储技术的研究与实现》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图书分类号：TP399U.D.C.:681.3.066工学硕士学位论文生物序列及其索引的压缩存储技术的研究与实现硕士研究生：郑元荣导师：张岩副教授申请学位：工学硕士学科、专业：计算机科学与技术所在单位：计算机科学与技术学院答辩日期：2007年7月授予学位单位：哈尔滨工业大学ClassifiedIndex:TP399U.D.C.:681.3.066ADissertationfortheDegreeofM.Eng.RESEARCHANDIMPLEMENTATIONOFCOMPRESSSTORAGEOFBIOLOGICALSEQUENCESANDINDICESCandidate:Supe

2、rvisor:AcademicDegreeAppliedfor:Specialty:Affiliation:DateofOralExamination:University:ZhengYuan-rongAssociateProf.ZhangYanMasterofEngineeringComputerScienceandTechnologyComputerScienceandTechnologyJuly,2007HarbinInstituteofTechnology哈尔滨工业大学工学硕士学位论文摘要自从1953年DNA结构被揭示以来，分子生物学取得了巨大的进展。随着对生物大分子序列操

3、纵能力的增强，生物信息学等学科研究的深入及人类基因组计划的完成，科研工作已经产生并仍在产生大量的数据，存储DNA序列信息及其索引所占用的空间也在呈指数增长。因此，设计高效的生物序列索引结构，研究生物序列数据的压缩存储技术成为生物数据库领域的重要研究课题。生物序列数据库中存储着规模巨大的生物序列信息，由于生物的关键基因往往有多个副本，这些信息中有很多重复子串，而且生物有时为了进化或“自私”的目的也要对某些基因进行复制。因此，生物序列数据库中存在大量数据冗余，是可以被压缩的。本文提出了一种结构并行的局部优化压缩算法，通过把生物序列数据分片到多台处理机，在单个处理机上采用广义后缀树来查找序

4、列中冗余子串的方法，明显提高了序列压缩的处理速度。在生物序列分片压缩的基础上，本文还给出了一种结构并行的搜索操作算法。索引技术加快了序列处理的速度，现有的索引技术包括后缀树，后缀数组，q-gram和q-sample等。其中后缀树处理速度最快，但由于“内存瓶颈”问题不能应用在大序列上。本文提出了压缩的分层存储索引结构。这种结构采用一种自顶向下建立后缀树索引结构的方法，它由若干层组成，每层都可以依次独立建立，这样就有效避免了“内存瓶颈”问题。该结构在保证建立效率和搜索操作效率的同时，有效利用了存储空间。在此基础上，给出了其上的搜索操作算法。实验表明：本文的序列压缩算法与其他压缩算法相比，

5、压缩效果有明显改进；分层存储索引的空间需求情况得到了较大缓解，同时其搜索操作的效率并未受到明显影响。关键词压缩；并行处理；生物序列；后缀树；分层索引-I-哈尔滨工业大学工学硕士学位论文AbstractEversincethestructureofDNAwasunraveledin1953,molecularbiologyhaswitnessedtremendousadvances.RecentadvancesinsequencingtechnologyhaveallowedtherapidaccumulationofDNAandproteindata.Ahugeamountofbi

6、osequenceshavebeenandarebeinggeneratedinlaboratoriesallovertheworld.Itiswellknownthattheirsizeincreasesnowadaysexponentially.Therefore,thedesignofeffectiveindicesandcompressionofgeneticinformationconstituteaveryimportanttask.Therearelarge-scalebiologicalsequenceinformationsstoredinbiologicaldat

7、abase.Itiswellknownthatmanyessentialgenes(likerRNAs)havemanycopiesandrepeatsubstring.Italsohasbeenconjecturedthatgenesduplicatethemselvesforevolutionaryorsimplyfor“selfish”purposes.AllthisevidencegivesmoreconcretesupportthattheDNA