基于de Bruijn图的宏基因组序列拼接算法实现

发布时间：2018-03-16 00:12

本文选题：宏基因组　切入点：第二代测序技术　出处：《山东大学》2017年硕士论文　论文类型：学位论文

【摘要】：基因组测序技术为生物学研究提供了数据支持,从而有力的推动了对生命活动规律的理解和认识。宏基因组学是一门新兴的不依赖于实验室培养直接从环境中提取微生物群落的DNA进行研究的学科,这种大规模的基因组学技术实现了对不同环境中微生物的深入研究。然而受限于测序技术,测序仪每次只能读出基因组上一个短片段,而不是一次读出完整的基因组序列。因此,从短片段中恢复出多个物种的完整基因组的序列拼接是宏基因组学的一个基本问题。目前计算机技术方面,对宏基因组序列拼接算法的研究还仍然处于初步阶段,大多数序列拼接工作依然利用单基因组拼接软件来完成,然而绝大部分单基因组序列拼接在宏基因组上数据上存在很大的局限性。因此,本文针对宏基因组的序列拼接算法展开了一系列的工作并将之实现。本文的主要工作是在我们开发的单基因组拼接软件ARCS的基础上,加入了新的模块来处理针对宏基因组的数据,提出并实现一个有效的宏基因组序列拼接软件Meta-ARCS。我们设计了新的针对第二代数据的序列拼接的拆解deBruijn图形成contigs算法。主要是估计压缩边的序列重数,挑选unique压缩边,利用pair-kmer插入距离信息,并采用线性规划技术求得unique压缩边的最优排布,最终形成更长的contigs和scaffolds。针对这些填充了间隙的scaffolds,我们除去间隙,获得正确率更高的却更短的contigs,利用coverage信息将contigs进行binning操作,每个bin里的contigs都属于单一的物种。在真实数据集和模拟数据集上的实验表明:同已有拼接软件做系统比较,Meta-ARCS取得了比较好的结果。
[Abstract]:Genome sequencing technology provides data support for biological research, Macrogenomics is an emerging discipline that does not rely on laboratory culture to extract microbial communities directly from the environment for research. This large-scale genomics technique allows for in-depth research into microbes in different environments. However, limited to sequencing technology, sequencers can read only one short segment of the genome at a time. So it's a fundamental problem in macrogenomics to restore the complete genome sequence of multiple species from a short fragment. The research on the algorithm of macro genome sequence mosaic is still in the preliminary stage, and most of the sequence stitching work is still completed by single genome mosaic software. However, most of the single-genome sequence splicing on the macro genome has great limitations. In this paper, a series of work has been carried out on the sequence splicing algorithm of the macro genome, which is based on the single genome mosaic software ARCS, which is developed by us. A new module was added to process data for the macro genome, In this paper, we propose and implement an effective macro genome sequence mosaic software Meta-ARCS. we design a new contigs algorithm for the second generation data sequence splicing, which is mainly to estimate the sequence multiplicity of the compressed edges and select the unique compressed edges. By using the pair-kmer insertion distance information and linear programming technique, the optimal arrangement of unique compression edges is obtained, resulting in the formation of longer contigs and scaffolds. for these scaffoldsfilled with gaps, we remove the gaps. Get a higher accuracy but shorter contig, use the coverage information to binning the contigs, Contigs in each bin belongs to a single species. Experiments on real data sets and simulated data sets show that Meta-ARCS has better results compared with existing mosaic software systems.
【学位授予单位】：山东大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：Q811.4;TP319

【相似文献】