【作者】 张丽君；

【导师】 于长永；

【作者基本信息】 东北大学 ， 计算机软件与理论， 2015， 硕士

【摘要】 随着人类基因组计划的顺利完成,基因组学也随之进入了对于基因结构和功能分析的后基因组时代。与此同时,基因组的测序技术也向着更加快速、准确和经济的目标发展。如何快速、高通量以及低消耗地实现基因组的测序仍然是基因组学中一个基础而又十分重要的环节。新一代测序技术的序列数据(read)具有数据量大、序列长度短和准确性相对较低等特点,已有的序列拼接算法并不适应上述的数据特点。因此,适应新一代测序技术的序列拼接算法的进一步研究势在必行。目前,基于deBruijn图的序列拼接算法是基因组de novo测序拼接算法中的主要方法。该类方法利用deBruijn图来存储基因序列,具有节省内存开销、高准确性和高覆盖率等特点。本文针对基于新一代测序技术的基因组de novo测序拼接问题进行了较深入的研究,并取得了一些研究结果,具体归纳如下:首先,深入调研了生物信息学的产生、定义和发展过程;调研了基因组测序和DNA序列拼接中的主要技术;深入研究了基于de Bruijn图序列拼接算法的原理和对应的算法的计算流程。其次,针对新一代DNA测序数据的短序列、高通量、数据量大等特点,引入了决策表的概念以及用四叉树进行后继k-mer的选取方法,优化了基于deBruijn图序列拼接算法。再次,深入调研了基于MapReduce模型的deBruijn图序列拼接算法。并且,基于该模型提出了避免deBruijn图分块的具体方法和并行化方法,采用变化的K值构建de Bruijn图,实现了基于de Bruijn图的并行de novo拼接程序,并获取了拼接效率最高的拼接结果序列,最后,进行了大量的实验,并将实验结果和现有的算法的结果相比较。本文提出的基于deBruijn图的序列拼接算法的优化技术能够在一定程度上提高序列拼接的效率和准确率。基于MapReduce模型的de Bruijn图的序列拼接算法的并行化研究提高了 denovo算法的扩展性,大大提高了序列拼接的速度。基因组de novo拼接方法不利用任何参考序列,直接地基于基因组测序序列(reads)推导DNA序列,对于没有DNA参考序列的物种的基因组测序是唯一的方法。本文的研究结果对于更加准确、快速和高通量地DNA新一代测序具有一定的理论价值和实用价值。更多还原

【Abstract】 Along with the successful completion of the human genome project,genomics has also started the post genomic era for gene structure and functional analysis.At the same time,the sequencing technology of genome is developing rapidly,accuracy and economy.How to achieve the sequence of the genome rapidly,high flux and low consumption is still a basic and an important link in genomics.The sequence data(read)of the new generation sequencing technology has the characteristics of large amount of data,short sequence length and low accuracy.The existing sequence assembly technology is not adapted to the above data features.Therefore,it is imperative to study the further research of the sequence of the new generation sequencing technology.At present,the sequence assembly algorithm based on de Bruijn graph is the main method in genome sequencing.This method uses the de Bruijn graph to store the gene sequences,and has the features of saving memory,high accuracy and high coverage.In this thesis,based on the new generation of sequencing technology,the genome sequencing problems from the beginning of a deeper study,and some research results are made,as follows:Firstly,the emergence,definition and development of bioinformatics were deeply investigated.The main techniques of genome sequencing and assembling were investigated.The principle based on de Bruijn graph sequence assembly algorithm and the corresponding software is deeply studied.Secondly,for characteristic of short sequences,high throughput and the amount of data of next-generation DNA sequencing data,we introduce the concept of decision table and the subsequent k-mer selection method,and optimalize sequence assembly algorithm based on de Bruijn graph.Thirdly,The Bruijn de graph sequence assembly algorithm based on MapReduce model is deeply investigated.Moreover,based on the proposed model,the specific method and the parallelization method of avoiding the block de Bruijn graph are proposed,the de Bruijn graph was constructed by the change of K values,and the maximum assembly efficiency was obtained,and the parallel de novo assembly program based on de Bruijn graph is realized.Finally,a large number of experiments are carried out and the experimental results are compared with the results of the existing algorithms.This thesis presents the optimization technology of sequence assembly algorithm for de Bruijn graph,which can improve the efficiency and accuracy of sequence assembly to some extent.The parallelization of sequence assembly algorithm based on de Bruijn graph,which is based on MapReduce model,improves the scalability of de novo algorithm,and greatly improves the speed of sequence assembly.Genome de novo sequencing method(de novo sequencing)does not use any reference sequence,and gets DNA sequences directly based on genome sequencing(reads).For new species of genome sequencing this method is the only way.The results of this study have some theoretical value and practical value for more accurate,rapid and high throughout DNA sequencing.更多还原