基于de bruijn graph梳理的宏基因组拼接算法开发

Metagenomic sequencing allows reconstruction of microbial genomes directly from environmental samples. A number of assemblers for reconstructing metagenomes using NGS sequencing data have been developed, but they are all too limited to be used in practice. The computational study of the problem is now facing a bottleneck in both effectiveness and efficiency. In this project we aim at revolutionizing the traditional approaches to challenge the fundamental problem based on a dynamically changed de Bruijn graph..The main goal of the project is to develop an innovative algorithm for assembling metagenomes using NGS sequencing data leveraging four basic operations on a dynamically changed de Bruijn graph, followed by a software pipeline which can be freely used by users who are in need of metagenomics analysis for academic purposes. Concretely, we will 1) complete de Bruijn graph by bridging between tips using mate-pair reads; 2) transform the completed de Bruijn graph into a canonical de Bruijn graph by tearing and contracting each sub-path matching a mate-pair such that each mate-pair belongs to a single contracted edge of the canonical de Bruijn graph; 3) transform the canonical de Bruijn graph into a set of parallel contracted edges by combing the canonical de Bruijn graph at each node and contracting simple paths; 4) stretching these contracted edges back to genome-representing paths by tracing back the contractions. In addition, we will also estimate the abundances of individual genomes within a metagenome to be assembled by keeping the coverage depths for the contracted edges. The software pipeline will be developed as an open source like those we did before. This project starts a new approach with the unique features: 1) of capability of rescuing those genomes which are not fully sequenced by completing the de Bruijn graph using mate-pairs; 2) of capability of effectively and efficiently integrating coverage depth and mate-pair information by combination of tearing, combing, contracting and stretching techniques. .We benchmarked the preliminary results on simulated datasets, demonstrating that the proposed approach in this project would be highly promising in reconstruction of metagenomes using NGS short sequences. It is the first attempt to accurately reconstruct the whole genomes within a metagenome. It has been roughly estimated based on our experiences of assembling transcriptomes that the planed project would substantially revolutionize the state of the art of same kind. Taking advantage of the techniques proposed in this project, the new metagenome assembler will play a crucial role for new discoveries in metagenome study after it is fully accomplished.

从环境中直接取样的样品中含有多种未知的、不可分离的微生物，宏基因组测序技术使得重构样品中的微生物基因组成为可能。然而，目前有很少几个基于二代测序数据的宏基因组拼接算法或软件，并且在实际应用中遇到了难以克服的两大瓶颈：拼接效果和计算效率。我们将挑战这一计算难题，通过建立新的数学模型和研制新的算法技术，实现突破宏基因组重构的计算瓶颈。本项目将研发一个基于二代测序的全新的宏基因组拼接算法，其核心思想是建立一个动态变化的de bruijn graph，通过研发de bruijn graph的梳理技术实现宏基因组的计算重构。新拼接算法将独有如下特征：1）能合理使用双端测序信息完善de bruijn graph，从而拼接出没有被全长测序的基因组；2）通过子路移除，点的梳理，路径收缩以及收缩边的展开等技术，能高效的将覆盖度信息和双端测序信息有机结合起来。在模拟数据上对初步结果的测试显示，本项目提出的方法

从环境中直接取样的样品中含有多种未知的、不可分离的微生物，宏基因组测序技术使得重构样品中的微生物基因组成为可能。然而，目前有很少几个基于二代测序数据的宏基因组拼接算法或软件，并且在实际应用中遇到了难以克服的两大瓶颈：拼接效果和计算效率。我们挑战了这一计算难题，通过建立新的数学模型和研制新的算法技术，实现了突破宏基因组重构的计算技术。本项目研发了一系列基于二代测序的转录组拼接算法，其核心思想是建立一个动态变化的德补路径图，通过研发德补路径图的梳理技术实现了转录组重构的组装算法，而重构宏基因组的组装计算将由此出发。新拼接算法的确独有如下特征：1）能合理使用双端测序信息完善德补路径图，从而拼接出没有被全长测序的基因组；2）通过子路移除，点的梳理，路径收缩以及收缩边的展开等技术，能高效的将覆盖度信息和双端测序信息有机结合起来。在模拟数据上对初步结果的测试显示，本项目提出的方法能够有效的利用二代测序数据完成微生物宏基因组的重构。发表相关学术论文十余篇。