Compacting de Bruijn graphs from sequencing data quickly and in low memory.
Compacting de Bruijn graphs from sequencing data quickly and in low memory.
复制标题
DOI：
10.1093/bioinformatics/btw279
复制
发表时间：
2016-06-15
期刊：
影响因子：
--
通讯作者：
Medvedev P
中科院分区：
文献类型：
--
作者：
Chikhi R;Limasset A;Medvedev P
动机：随着每个测序实验的数据量增加，片段组装的挑战变得越来越计算性。De Bruijn图是片段组装算法中广泛使用的数据结构，用于表示来自一组读取的信息。在大多数基于de Bruijn图的算法中，压缩是一个重要的数据约简步骤，在这些算法中，简单的长路径被压缩成单个顶点。压缩已成为装配流水线的瓶颈，提高其运行时间和内存使用率是一个重要的问题。结果：给出了一个用于De Bruijn图压缩的算法和工具BCalm 2。BCalm 2是一个并行算法，它基于最小化散列技术分发输入，允许在整个执行过程中很好地平衡内存使用。对于人类测序数据，BCalm 2将压缩de Bruijn图的计算负担减少到大约一个小时和3 GB的内存。我们还将BCalm 2应用于22 GBP火炬松和20 GBP白云杉测序数据集。在一台机器上使用不到2天的原始读取和40 GB的内存构建了压缩图。因此，BCalm 2的效率至少比其他可用的方法高一个数量级。可获得性和实现：BCalm2的源代码可在以下网址免费获得：https://github.com/GATB/bcalm联系人：rayan.chikhi@univ-lille1.fr
Motivation: As the quantity of data per sequencing experiment increases, the challenges of fragment assembly are becoming increasingly computational. The de Bruijn graph is a widely used data structure in fragment assembly algorithms, used to represent the information from a set of reads. Compaction is an important data reduction step in most de Bruijn graph based algorithms where long simple paths are compacted into single vertices. Compaction has recently become the bottleneck in assembly pipelines, and improving its running time and memory usage is an important problem. Results: We present an algorithm and a tool bcalm 2 for the compaction of de Bruijn graphs. bcalm 2 is a parallel algorithm that distributes the input based on a minimizer hashing technique, allowing for good balance of memory usage throughout its execution. For human sequencing data, bcalm 2 reduces the computational burden of compacting the de Bruijn graph to roughly an hour and 3 GB of memory. We also applied bcalm 2 to the 22 Gbp loblolly pine and 20 Gbp white spruce sequencing datasets. Compacted graphs were constructed from raw reads in less than 2 days and 40 GB of memory on a single machine. Hence, bcalm 2 is at least an order of magnitude more efficient than other available methods. Availability and Implementation: Source code of bcalm 2 is freely available at: https://github.com/GATB/bcalm Contact: rayan.chikhi@univ-lille1.fr