基于bwt地dna从头测序重叠群生成算法

《基于bwt地dna从头测序重叠群生成算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、硕士学位论文基于BWT的DNA从头测序重叠群生成算法ANALGORITHMOFDENOVOCONTIGCONSTRUCTIONBASEDONBWT毕鹏程哈尔滨工业大学2012年7月中图分类号：TP311学校代码：10213 UDC：004密级：公开工学硕士学位论文基于BWT的DNA从头测序重叠群生成算法硕士研究生：毕鹏程导师：王亚东教授申请学位：工学硕士学科：计算机科学与技术所在单位：计算机科学与技术学院答辩日期：2011年7月授予学位单位：哈尔滨工业大学ClassifiedIndex:TP311 U.D.C:004DissertationfortheMasterDegreei

2、nEngineeringANALGORITHMOFDENOVOCONTIGCONSTRUCTIONBASEDONBWTCandidate：BiPengchengSupervisor：Prof.WangYadongAcademicDegreeAppliedfor：MasterofEngineeringSpecialty：ComputerScienceandTechnologyAffiliation：SchoolofComputerScienceandTechnologyDateofDefence：July,2012Degree-Conferring-Institution：Har

3、binInstituteofTechnology哈尔滨工业大学工学硕士学位论文摘要随着遗传学研究的深入，特别是人类基因组计划完成之后，人们认识到取得各个物种的完整基因组序列对于生命本质的探索有着非常重要的作用。如今新一代DNA测序技术已经发展成熟并被广泛的使用，其前所未有的测序速度逐渐的促进了基于序列研究的基因组学的研究，同时也增加了对生物信息学算法的需求。新一代测序技术与传统测序技术相比有速度快、成本低和准确度高的优点，但是其产生的序列片段相对较短。由于传统测序技术开发的序列拼接算法已不适用于新一代测序技术，开发针对新一代测序技术的拼接软件已成为生物信息学领域里一个热门的课题

4、。为此提出一种基于BWT的从头测序的重叠群生成算法，该算法利用BWT的搜索功能找到read之间的最优重叠从而实现序列拼接的目的。首先通过分析实验数据，总结出read数据的特点。然后对序列拼接问题进行分析和建模并给出解决方案。接着详细介绍了整个BWT索引的建立过程，讲述了BWT的原理和作用，以及BTW索引的数据结构和使用方法。对DNA序列拼接过程中需要用到的BWT的向前匹配算法进行了描述，设计了向后匹配算法，并分析了这些算法的时间和空间性能。然后就整个contig的生成过程进行了介绍。首先给出contig生成算法的整体流程，接下来就基于BWT的contig的最佳重叠查找算法进行了

5、具体叙述。然后讲述了contig的延伸算法，主要分正向延伸和反向延伸。并针对之前生成的contig集合里的重复问题提出了contig的修剪算法。最后，评价了算法输出的效果，并与EULER-SR算法进行对比。可以看出我们的序列拼接算法所产生的contig的长度较短，数量较多，仍然有很大的改进空间。但是时间和空间上有很大改善，这对于人类这种大型基因组的拼接有很大的实用意义。关键词：新一代测序技术；序列拼接；BWT；DNA重叠群-I-哈尔滨工业大学工学硕士学位论文AbstractWiththedevelopmentofgeneticsresearch,especiallyaftert

6、hecompletionoftheHumanGenomeProject,itisrecognizedthattoobtainthecompletegenomesequenceofvariousspecieshasaveryimportantrolefortheexplorationofthenatureoflife.Todaythenext-generationDNAsequencingtechnologieshasbeenfully-developedandwidelyused,itsunprecedentedspeedofsequencingpromotedthestudy

7、ofsequence-basedgenomicresearch,whilealsoincreasedthedemandofbioinformaticsalgorithms.Next-generationsequencingtechnologiesfeatureseveraladvantageswhencomparedwithtraditionalsequencingmethodsintermsofhighersequencingspeed,lowerperruncostandhigeracc