Pell, J., A. Hintze, R. Canino-Koning, A. Howe, J. M. Tiedje, and C. T. Brown. 2012. Scaling metagenome sequence assembly with probabilistic de Bruijn graphs. Proceedings of the National Academy of Sciences 109:13272-13277.
Deep sequencing has enabled the investigation of a wide range of environmental microbial ecosystems, but the high memory require- ments for de novo assembly of short-read shotgun sequencing data from these complex populations are an increasingly large practical barrier. Here we introduce a memory-efficient graph re- presentation with which we can analyze the k-mer connectivity of metagenomic samples. The graph representation is based on a probabilistic data structure, a Bloom filter, that allows us to effi- ciently store assembly graphs in as little as 4 bits per k-mer, albeit inexactly. We show that this data structure accurately represents DNA assembly graphs in low memory. We apply this data structure to the problem of partitioning assembly graphs into components as a prelude to assembly, and show that this reduces the overall mem- ory requirements for de novo assembly of metagenomes. On one soil metagenome assembly, this approach achieves a nearly 40-fold decrease in the maximum memory requirements for assembly. This probabilistic graph representation is a significant theoretical ad- vance in storing assembly graphs and also yields immediate lever- age on metagenomic assembly.
Download citation to endnote bibtex
Sign in to download PDF back to index