新一代dna测序数据的重叠群组装算法的研究与实现

《新一代dna测序数据的重叠群组装算法的研究与实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、硕士学位论文新一代DNA测序数据的重叠群组装算法的研究与实现RESEARCHANDIMPLEMENTATIONOFCONTIGASSEMBLYALGORITHMONNEXTGENERATIONDNASEQUENCINGDATA马云云哈尔滨工业大学2016年6月国内图书分类号：TP319学校代码：10213国际图书分类号：004.91密级：公开工程硕士学位论文新一代DNA测序数据的重叠群组装算法的研究与实现硕士研究生：马云云导师：权光日教授申请学位：工程硕士学科：计算机技术所在单位：计算机科学与技术学院答辩日期

2、：2016年6月授予学位单位：哈尔滨工业大学ClassifiedIndex:TP319U.D.C:004.91DissertationfortheMasterDegreeinEngineeringRESEARCHANDIMPLEMENTATIONOFCONTIGASSEMBLYALGORITHMONNEXTGENERATIONDNASEQUENCINGDATACandidate：MaYunyunSupervisor：Prof.QuanGuangriAcademicDegreeAppliedfor：Master

3、ofEngineeringSpecialty：ComputerTechnologyAffiliation：SchoolofComputerScienceandTechnologyDateofDefence：June,2016Degree-Conferring-Institution：HarbinInstituteofTechnology哈尔滨工业大学工程硕士学位论文摘要二十一世纪以来，新一代测序技术高通量、低成本的优点，极大地促进了生物信息学领域的发展。为了获取测序数据所包含的信息，基因组拼接组装算法成为了该

4、领域研究的核心，许多优秀的基因组拼接组装算法应运而生。近几年，测序技术在原来的基础上不断改革创新，产生的新数据发生了变化，它们不仅具备原本数据的高通量、错误率高的特点，还拥有了新的特性：出现配对信息和读长变长。然而，原有的基因组拼接组装算法却无法利用这些新的特点，因此设计一种能够充分利用新一代数据特性的基因组拼接组装算法成为了基因组领域一个迫切需要解决的问题。全基因组拼接组装分为两个阶段：将read拼接生成重叠群的重叠群生成阶段以及将重叠群组装生成支架的重叠群组装阶段。本文研究的重叠群组装算法针对第二个阶段，

5、在已有重叠群集合的基础上，利用配对数据，将其组装生成支架。通过重叠群组装，可以获取测序数据中的信息，还原得到目标生物的基因序列，具有十分重要的研究意义。本文针对新数据的特性，提出了一种新的重叠群组装算法。该算法首先利用插入距离较短的配对数据，寻找配对数据与重叠群之间的关联的关系，并根据这个关系设计关联关系评价方法，给出任意两个重叠群之间关联关系的得分，从而判定其相对位置关系。然后，针对组装过程中出现的位置关系进行处理，对组装结果进行优化；最后，利用插入距离较长的配对数据进行进一步的处理，最终输出组装生成的支架

6、序列。本文提出的重叠群组装算法，充分利用了新一代数据的特点，将重叠群序列组装成支架。在本文最后，将利用本文算法产生的结果与目前广泛使用的两款软件SOAPdenovo2、Velvet产生的结果作比较，发现利用本文算法组装的支架序列准确性更高，综合性能更好，从而具有较高的可信度，为后续基因组的分析奠定良好的基础。关键词：从头测序；重叠群组装；关联关系评价；配对数据-I-哈尔滨工业大学工程硕士学位论文AbstractSince21stcentury,theadvantagesofhighthroughputandl

7、owcostofthenextgenerationsequencingtechnologyhasgreatlypromotedthedevelopmentofbioinformatics.Inordertoobtaintheinformationcontainedinthesequencingdata,genomeassemblyalgorithmhasbecomethecoreoftheresearchinthisfiled.Manyexcellentgenomeassemblyalgorithmsemer

8、geasthetimesrequire.Inrecentyears,thecontinuousreformandinnovationonthebasisofsequencingtechnology,thenewsequencingdatahaschanged.Theynotonlyhavethecharacteristicsofhighthroughputandhigherrorrate,butal