title: Scaling metagenome sequence assembly with probabilistic de Bruijn graphs.
abstract: Deep sequencing has enabled the investigation of a wide range of environmental microbial ecosystems, but the high memory requirements 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 representation 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 efficiently 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 memory 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 advance in storing assembly graphs and also yields immediate leverage on metagenomic assembly.
authors: Computer Science and Engineering, Michigan State University, East Lansing, MI 48824, USA.
authors: Jason
authors: J
authors: Pell
authors: Arend
authors: A
authors: Hintze
authors: Rosangela
authors: R
authors: Canino-Koning
authors: Adina
authors: A
authors: Howe
authors: James M
authors: JM
authors: Tiedje
authors: C Titus
authors: CT
authors: Brown
mesh_terms: D020029:Base Pairing / Q000235:genetics; D002876:Chromosomes, Bacterial / Q000235:genetics; D019295:Computational Biology; D004270:DNA, Circular / Q000235:genetics; D004926:Escherichia coli / Q000235:genetics; D016680:Genome, Bacterial / Q000235:genetics*; D007257:Information Theory; D054892:Metagenome / Q000235:genetics*; D017711:Nonlinear Dynamics; D017422:Sequence Analysis, DNA / Q000379:methods*; D012988:Soil Microbiology
chemical_list: D004270:DNA, Circular