A parallel connectivity algorithm for de Bruijn graphs in metagenomic applications
A parallel connectivity algorithm for de Bruijn graphs in metagenomic applications
复制标题
宏基因组应用中 de Bruijn 图的并行连接算法
DOI：
10.1145/2807591.2807619
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
S. Aluru
中科院分区：
文献类型：
--
作者：
P. Flick;Chirag Jain;Tony Pan;S. Aluru
DNA测序技术的巨大进步使得通过直接测序环境DNA样品来研究微生物环境成为可能。然而，由于巨大的体积和高的数据复杂性，目前的从头组装器不能处理大型宏基因组数据集或不能以可接受的质量执行组装。本文提出了第一个并行解决方案，用于分解宏基因组组装问题，而不影响组装后的质量。我们把这个问题转化为在de Bruijn图中寻找弱连通分量的问题。我们提出了一种新的分布式存储算法来识别连通子图，并提出了策略，以尽量减少通信量。我们证明了我们的算法在土壤宏基因组数据集上的可扩展性，该数据集具有18亿次读取。我们的方法使用1280个Intel Xeon核心实现了22分钟的运行时间，用于421 GB未压缩的FASTQ数据集。此外，我们的解决方案是可推广到寻找连通组件在任意无向图。
Dramatic advances in DNA sequencing technology have made it possible to study microbial environments by direct sequencing of environmental DNA samples. Yet, due to the huge volume and high data complexity, current de novo assemblers cannot handle large metagenomic datasets or fail to perform assembly with acceptable quality. This paper presents the first parallel solution for decomposing the metagenomic assembly problem without compromising the post-assembly quality. We transform this problem into that of finding weakly connected components in the de Bruijn graph. We propose a novel distributed memory algorithm to identify the connected subgraphs, and present strategies to minimize the communication volume. We demonstrate the scalability of our algorithm on a soil metagenome dataset with 1.8 billion reads. Our approach achieves a runtime of 22 minutes using 1280 Intel Xeon cores for a 421 GB uncompressed FASTQ dataset. Moreover, our solution is generalizable to finding connected components in arbitrary undirected graphs.