基于deBruijn图的短序列拼接算法的优化及并行化

《基于deBruijn图的短序列拼接算法的优化及并行化》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中图分类号UDCTP391600硕士学位论文学校代码密级10533基于deBruijn图的短序列拼接算法的优化及并行化AparallelandoptimizedalgorithmsfordenOVOSlaOrtreadassemblyUSlngde15rullnzraons，'-，⋯作者姓名学科专业研究方向学院(系、所)指导教师：邱凤：计算机科学与技术：生物信息学：信息科学与工程学院：胡志刚教授答辩委员会主席中南大学二零一三年四月一令一二，半幽月原创性声明本人声明，所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除

2、了论文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得中南大学或其它单位的学位或证书而使用过的材料。与我共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。作者签名：篁翌虱日期：丝!≥年工月望日学位论文版权使用授权书本人了解中南大学有关保留、使用学位论文的规定，即：学校有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文，允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科学技术信息研究所将本学位论文收录到《中国学位论文

3、全文数据库》，并通过网络向社会公众提供信息服务。储繇丑堂新签磁蚂吼丛年』月兰日基于deBruijn图的短序列拼接算法的优化及并行化摘要：基因组测序一直是基因组学的核心内容，随着测序技术的产生和发展，人们能在较短时间内获得大量测序数据。测序技术朝着高通量、低成本、高精度的方向发展，积累的测序数据也随之越来越多。如何快速、准确地处理海量测序数据己成为DNA测序发展的瓶颈。本文通过对现有基于deBruijn图算法的新一代测序技术优缺点的深入分析和研究，针对得到的read片段长度短、数量多以及通量高的特点，研究设计了基于deBruijn图的优化算法。

4、在序列拼接的过程中引入决策表的概念，通过决策表中的信息更新来优化deBruijn图中最优路径的选择，缩小后继k．mer的选择范围，从而达到缩短序列拼接时间，提高contig准确率的目的。在优化算法的基础上，提出了算法的并行化处理方案，通过分别对I／O读取和存储的并行化以及拼接过程中的并行化设计，达到进一步缩短拼接时间，减少单机上存储压力，提高计算性能的目的。仿真实验结果表明，本文提出的基于deBruijn图算法的短序列拼接算法的优化及并行化设计与新一代测序技术中的基于deBruijn图算法相比，有效提高了序列拼接的运算速度，降低了单机运行的内

5、存压力。在拼接数据量为20G的C．elegans基因组，处理器为8个时，其加速比达到6倍，且具有良好的可扩展性。图21幅，表9个，参考文献70篇。关键词：deBruijn图；序列拼接；决策表；并行分类号：TP391IIAParallelandoptimizedalgorithmsfordenovoshortreadassemblyusingdeBruijngraphsAbstract：Genomesequencinghasbeenthecorecontentofgenomics．Withtheemergenceanddevelopmentof

6、thesequencingtechnology,hugesequencingdataCanbeobtainedinarelativelyshortperiodoftime．Sequencingtechnologyhasmovedtowardthathighflux，lowcostandhighprecision．Withthedevelopmentofsequencingtechnologyandemergencyofmassivedata，handlingthemassivesequencingdataaccuratelyhasbecome

7、thebottleneckofthedevelopmentofDNAsequencing．Bytheanalysisofexistingassemblymethodsandrelevanttechn0109YbasedondeBruijngraph，theadvantagesanddisadvantagesofthenew。generationsequencingtechnologyarepresented．Accordingtotheshortlength，thehugeamountandthehighfluxofreadfragments

8、．t11edeBruijnalgorithmisoptimizedbycombiningwithadecisiontable．Thesequenceassembly