Aug 1, 2012

Scaling metagenome sequence assembly with probabilistic de Bruijn graphs

Proceedings of the National Academy of Sciences of the United States of America
Jason PellC Titus Brown

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.

  • References29
  • Citations72

Citations

Mentioned in this Paper

Alkalescens-Dispar Group
Metagenome
Microbiome
Chaos Theory
Sequence Determinations, DNA
Deep Sequencing
Chromosomes, Bacterial
Microbial
Base Pairing
Information Theory

Trending Feeds

COVID-19

Coronaviruses encompass a large family of viruses that cause the common cold as well as more serious diseases, such as the ongoing outbreak of coronavirus disease 2019 (COVID-19; formally known as 2019-nCoV). Coronaviruses can spread from animals to humans; symptoms include fever, cough, shortness of breath, and breathing difficulties; in more severe cases, infection can lead to death. This feed covers recent research on COVID-19.

Coronavirus Protein Structures

Deciphering and comparing the proteins of different coronaviruses forms a basis for understanding SARS-CoV-2 evolution and virus-receptor interactions. This feed follows studies analyzing the structures of coronavirus proteins, thereby revealing potential drug target sites.

DDX3X Syndrome

DDX3X syndrome is caused by a spontaneous mutation at conception that primarily affects girls due to its location on the X-chromosome. DDX3X syndrome has been linked to intellectual disabilities, seizures, autism, low muscle tone, brain abnormalities, and slower physical developments. Here is the latest research.

ALS: Stress Granules

Amyotrophic Lateral Sclerosis (ALS) is a neurodegenerative disease characterized by cytoplasmic protein aggregates within motor neurons. TDP-43 is an ALS-linked protein that is known to regulate splicing and storage of specific mRNAs into stress granules, which have been implicated in formation of ALS protein aggregates. Here is the latest research.

Fusion Oncoproteins in Childhood Cancers

This feed explores the function of fusion oncoproteins in specific childhood cancers, including those from racial/ethnic minority and underserved groups, and to provide preclinical assessment of potential therapeutics and how fusion oncoproteins influence gene expression to perturb normal cellular programs to block lineage differentiation and development

Applications of Molecular Barcoding

The concept of molecular barcoding is that each original DNA or RNA molecule is attached to a unique sequence barcode. Sequence reads having different barcodes represent different original molecules, while sequence reads having the same barcode are results of PCR duplication from one original molecule. Discover the latest research on molecular barcoding here.

Regulation of Vocal-Motor Plasticity

Dopaminergic projections to the basal ganglia and nucleus accumbens shape the learning and plasticity of motivated behaviors across species including the regulation of vocal-motor plasticity and performance in songbirds. Discover the latest research on the regulation of vocal-motor plasticity here.

Mitotic-exit networks with cytokinesis

Cytokinesis is the highly regulated process that physically separates daughter and mother cells in late mitosis. The mitotic-exit network (MEN), the signalling pathway that drives mitotic exit, directly regulates cytokinesis. Discover the latest research on mitotic-exit networks with cytokinesis here.

DNA Replication Origin

DNA replication is initiated as specific gene sequences, called origins, that function to start DNA replication. Pre-replication complexes are assembled at these origins during the G1 phase of the cell cycle. These sequences allow for targeted activation or deactivation of replication. Discover the latest research on DNA replication origins here.