Space-efficient and exact de Bruijn graph representation based on a Bloom filter

The de Bruijn graph data structure is widely used in next-generation sequencing (NGS). Many programs, e.g. de novo assemblers, rely on in-memory representation of this graph. However, current techniques for representing the de Bruijn graph of a human genome require a large amount of memory (≥30 GB). We propose a new encoding of the de Bruijn graph, which occupies an order of magnitude less space than current representations. The encoding is based on a Bloom filter, with an additional structure to remove critical false positives. An assembly software implementing this structure, Minia, performed a complete de novo assembly of human genome short reads using 5.7 GB of memory in 23 hours.

• Publication year

  2012

• Venue

  Algorithms for Molecular Biology

• Publication date

  2012-09-10

• Fields of study

  Medicine, Computer Science

• Identifiers
  DOI 10.1186/1748-7188-8-22PMID 24040893PMCID 3848682
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar, PubMed

• No claims are published for this paper.

• No concepts are published for this paper.

• DSK: k-mer counting with very low memory usage

  2013cited by this paper
• Correlation of Stroke Volume Measurement between Sonosite Portable Echocardiogram and Edwards Flotrac Sensor-Vigileo Monitor in an Intensive Care Unit

  2013cited by this paper
• Theme: Computational Biology and Bioinformatics Computational Sciences for Biology, Medicine and the Environment

  2012cited by this paper
• KISSPLICE: de-novo calling alternative splicing events from RNA-seq data

  2012cited by this paper
• Mapsembler, targeted and micro assembly of large NGS datasets on a desktop computer

  2012cited by this paper
• Succinct de Bruijn Graphs

  2012cited by this paper
• Exploiting sparseness in de novo genome assembly

  2012influential reference
• GAGE: A critical evaluation of genome assemblies and assembly algorithms.

  2012cited by this paper
• De novo assembly and genotyping of variants using colored de Bruijn graphs

  2011cited by this paper
• Localized Genome Assembly from Reads to Scaffolds: Practical Traversal of the Paired String Graph

  2011cited by this paper
• Meta-IDBA: a de Novo assembler for metagenomic data

  2011cited by this paper
• Scaling metagenome sequence assembly with probabilistic de Bruijn graphs

  2011cited by this paper
• A fast, lock-free approach for efficient parallel counting of occurrences of k-mers

  2011cited by this paper
• Targeted Assembly of Short Sequence Reads

  2011cited by this paper
• Trinity: reconstructing a full-length transcriptome without a genome from RNA-Seq data

  2011cited by this paper
• Assembly complexity of prokaryotic genomes using short reads

  2010cited by this paper
• De novo assembly of human genomes with massively parallel short read sequencing.

  2010influential reference
• Identifying SNPs without a Reference Genome by Comparing Raw Reads

  2010cited by this paper
• GASSST: global alignment short sequence search tool

  2010cited by this paper
• Succinct data structures for assembling large genomes

  2010influential reference
• Assembly algorithms for next-generation sequencing data.

  2010cited by this paper
• ABySS: a parallel assembler for short read sequence data.

  2009cited by this paper
• Algorithms Gage: a Critical Evaluation of Genome Assemblies and Assembly Material Supplemental

  2008cited by this paper
• Less hashing, same performance: Building a better Bloom filter

  2006cited by this paper
• The Bloomier filter: an efficient data structure for static support lookup tables

  2004cited by this paper
• A New Algorithm for DNA Sequence Assembly

  1995cited by this paper
• Abyss: a Parallel Assembler for Short Read Sequence Data Material Supplemental Open Access

  year unknowninfluential reference

• Minimum virtual dataset for reproducible triploid de novo genome assembly.

  2026cites this paper
• Phylogenetic and Divergence Time Estimation of Muscomorpha with Low-Coverage Whole-Genome Sequencing of Syrphidae (Diptera: Brachycera)

  2026cites this paper
• Molecular Characterization of Complete Simian Foamy Virus Genomes from Three Colobine Monkeys Reveals Highly Divergent Evolutionary Trajectories and Identifies Transmission to Humans

  2026cites this paper
• MoleMap: fast alignment-free molecule mapping for long-read and linked-read sequencing data

  2026influential citation
• Identification of Significant Genomic Changes and Compartmentalization of Simian Foamy Virus in a Human Zoonotically Infected by a Chimpanzee (Pan troglodytes troglodytes).

  2026cites this paper
• Phylogenomics reveals the backbone phylogeny of Systellognatha (Insecta: Plecoptera).

  2026cites this paper
• Molecular detection of insecticide resistance markers in Aedes aegypti (Diptera: Culicidae) populations from Haiti.

  2026cites this paper
• Density-reducing Jaccard estimators for sketch-based long read applications

  2025cites this paper
• The Genome Survey Analysis of Female and Male Sepiella japonica

  2025cites this paper
• On the Coverage Required for Diploid Genome Assembly

  2025cites this paper
• Phylogeographic and genetic insights into Sinonychia martensi: an endemic cave-dwelling harvestman in Beijing

  2025influential citation
• Unveiling the Genetic Diversity and Population Structure of the Endangered Fern Angiopteris fokiensis Through Genome Survey and Genomic SSR Markers

  2025influential citation
• Phylogenomics reveals climate-driven range expansion of the antlion tribe Megistopini (Neuroptera: Myrmeleontidae: Nemoleontinae) during the Oligocene-Miocene transition.

  2025cites this paper
• SSR_VibraProfiler: a Python package for accurate classification of varieties using SSRs with intra-variety specificity and inter-variety polymorphism

  2025influential citation
• Intra-specific NLR allelic diversity and genomic landscape for plant resistance association studies

  2025cites this paper
• Inconsistent performance of multi‐type genomic data in phylogenomics of neuropteridan insects, with solutions toward conflicting results

  2025cites this paper
• Logan: Planetary-Scale Genome Assembly Surveys Life’s Diversity

  2025cites this paper
• A randomized transformation for data processing on quantum computers

  2025cites this paper
• Phylogenomics offers new insights into the classification of Phytoseiidae (Acari: Mesostigmata).

  2025cites this paper
• Phylogenetic relationship analysis of leafhopper subfamily Iassinae (Hemiptera: Cicadellidae) based on low-coverage whole-genome data

  2025influential citation
• A comparison of phylogenomic inference pipelines for low‐coverage whole‐genome sequencing in Formica ants

  2025influential citation
• DVOUG enables robust DNA sequence assembly and reconstruction with a dynamic, variable-order graph

  2025cites this paper
• Fast and Scalable Parallel External-Memory Construction of Colored Compacted de Bruijn Graphs with Cuttlefish 3

  2025cites this paper
• Phylogenomics of an early-branching clade of Orthocladiinae (Diptera: Chironomidae).

  2025cites this paper
• Loss of mitochondrial single stranded DNA-binding protein (mtSSB) gene is associated with mitochondrial genome fragmentation in Psocodea (bark lice, book lice, and parasitic lice)

  2025cites this paper
• k-mer approaches for biodiversity genomics

  2025cites this paper
• Non-adaptive Radiation Promotes Phenotypic Diversification and Convergent Evolution of Aposematic Mimicry in a Highly Diverse Genus of Megaloptera

  2025influential citation
• 基于邻接跳变德布鲁因序列的结构光编解码算法

  2024cites this paper
• Population genomics of seal lice provides insights into the postglacial history of northern European seals

  2024influential citation
• Phylogenetic analysis of Syrphidae (Insecta, Diptera) based on low-coverage whole genomes

  2024influential citation
• Label-guided seed-chain-extend alignment on annotated De Bruijn graphs

  2024cites this paper
• Whole-genome resequencing identifies exonic single-nucleotide variations in terpenoid biosynthesis genes of the medicinal and aromatic plant common sage (Salvia officinalis L.)

  2024cites this paper
• Adaptive Quotient Filters

  2024cites this paper
• Beyond Bloom: A Tutorial on Future Feature-Rich Filters

  2024cites this paper
• Genome sequencing and assembly of Indian golden silkmoth, Antheraea assamensis Helfer (Saturniidae, Lepidoptera).

  2024cites this paper
• Maptcha: an efficient parallel workflow for hybrid genome scaffolding

  2024cites this paper
• Guide to k-mer approaches for genomics across the tree of life

  2024cites this paper
• On the Coverage Required for Diploid Genome Assembly

  2024cites this paper
• A Distributed Cloud Architecture Based on General De Bruijn Overlay Network

  2024cites this paper
• Conway–Bromage–Lyndon (CBL): an exact, dynamic representation of k-mer sets

  2024cites this paper
• Whole-genome-based phylogenetic analyses provide new insights into the evolution of springtails (Hexapoda: Collembola).

  2024cites this paper
• Phylogeny and evolution of hemipteran insects based on expanded genomic and transcriptomic data

  2024cites this paper
• A phylogenetic analysis of scale insects (Hemiptera, Coccoidea) based on genomic and transcriptomic data

  2024cites this paper
• Illumina reads correction: evaluation and improvements

  2024cites this paper
• Structural variation in the pangenome of wild and domesticated barley

  2024influential citation
• A Whole-Genome Survey and the Mitochondrial Genome of Acanthocepola indica Provide Insights into Its Phylogenetic Relationships in Priacanthiformes

  2024influential citation
• Global exact optimisations for chloroplast structural haplotype scaffolding

  2024cites this paper
• Leveraging HBM2 for Accelerating k-mer Counting with oneAPI on FPGAs

  2024cites this paper
• Phylogenomics resolves a 100-year-old debate regarding the evolutionary history of caddisflies (Insecta: Trichoptera)

  2024influential citation
• A bacterial genome assembly and annotation laboratory using a virtual machine

  2023cites this paper
• A novel probe set for the phylogenomics and evolution of RTA spiders

  2023influential citation
• KmerCo: A lightweight K-mer counting technique with a tiny memory footprint

  2023cites this paper
• Theoretical Analysis of Sequencing Bioinformatics Algorithms and Beyond

  2023cites this paper
• The Effect of Methodological Considerations on the Construction of Gene-Based Plant Pan-genomes

  2023influential citation
• An Efficient Parallel Sketch-based Algorithmic Workflow for Mapping Long Reads

  2023cites this paper
• The Genome of the Blue Death-Feigning Beetle, Asbolus verrucosus Leconte, 1851 (Coleoptera: Tenebrionidae)

  2023cites this paper
• A practical assembly guideline for genomes with various levels of heterozygosity

  2023cites this paper
• An Efficient Parallel Sketch-based Algorithm for Mapping Long Reads to Contigs

  2023influential citation
• Global exact optimisations for chloroplast genome multimeric forms scaffolding

  2023cites this paper
• Adjacency-hopping de Bruijn Sequences for Non-repetitive Coding

  2023cites this paper
• A Comprehensive Bioinformatics Resource Guide for Genome-Based Antimicrobial Resistance Studies

  2023cites this paper
• Comparative genomics of bacteria from amphibian skin associated with inhibition of an amphibian fungal pathogen, Batrachochytrium dendrobatidis

  2023cites this paper
• Gapless provides combined scaffolding, gap filling, and assembly correction with long reads

  2023cites this paper
• Mitogenome of Xya pfaendleri (Orthoptera: Caelifera): Its comparative description and phylogenetic position within Tridactylidea.

  2023cites this paper
• BunchBloomer: Cost-Effective Bloom Filter Accelerator for Genomics Applications

  2022influential citation
• LMAS: evaluating metagenomic short de novo assembly methods through defined communities

  2022cites this paper
• Phylogenomics and systematics of Entomobryoidea (Collembola): marker design, phylogeny and classification

  2022influential citation
• Sex chromosomes in the tribe Cyprichromini (Teleostei: Cichlidae) of Lake Tanganyika

  2022cites this paper
• Comparative genomics of Lactobacillaceae from the gut of honey bees, Apis mellifera, from the Eastern United States

  2022cites this paper
• On the Hardness of Sequence Alignment on De Bruijn Graphs

  2022cites this paper
• Lightweight Pattern Matching Method for DNA Sequencing in Internet of Medical Things

  2022cites this paper
• Assembler artifacts include misassembly because of unsafe unitigs and underassembly because of bidirected graphs

  2022cites this paper
• Whole genome assembly of the armored loricariid catfish Ancistrus triradiatus highlights herbivory signatures

  2022cites this paper
• Recent advances in metagenomic analysis of different ecological niches for enhanced biodegradation of recalcitrant lignocellulosic biomass.

  2022cites this paper
• BOA: A partitioned view of genome assembly

  2022influential citation
• RResolver: efficient short-read repeat resolution within ABySS

  2022cites this paper
• The limitations of the theoretical analysis of applied algorithms

  2022cites this paper
• Recovering metagenome-assembled genomes from shotgun metagenomic sequencing data: Methods, applications, challenges, and opportunities.

  2022cites this paper
• Phylogenomic Analyses of the Tenthredinoidea Support the Familial Rank of Athaliidae (Insecta, Tenthredinoidea)

  2022cites this paper
• Coverage-preserving sparsification of overlap graphs for long-read assembly

  2022cites this paper
• The ViReflow pipeline enables user friendly large scale viral consensus genome reconstruction

  2022cites this paper
• Space-efficient representation of de Bruijn graphs for data streams

  2022cites this paper
• StrainXpress: strain aware metagenome assembly from short reads

  2022influential citation
• Testing the systematic status of Homalictus and Rostrohalictus with weakened cross‐vein groups within Halictini (Hymenoptera: Halictidae) using low‐coverage whole‐genome sequencing

  2022influential citation
• BEACON: Scalable Near-Data-Processing Accelerators for Genome Analysis near Memory Pool with the CXL Support

  2022cites this paper
• Human disease prediction from microbiome data by multiple feature fusion and deep learning

  2022cites this paper
• Optimal Scaffolding for Chloroplasts’ Inverted Repeats

  2022cites this paper
• Inverting the model of genomics data sharing with the NHGRI Genomic Data Science Analysis, Visualization, and Informatics Lab-space

  2022cites this paper
• The Complexity of Approximate Pattern Matching on De Bruijn Graphs

  2022cites this paper
• Multiplex de Bruijn graphs enable genome assembly from long, high-fidelity reads

  2022cites this paper
• Uncovering hidden assembly artifacts: when unitigs are not safe and bidirected graphs are not helpful

  2022cites this paper
• Graph theoretical Strategies in De Novo Assembling

  2022cites this paper
• Genomic Resources for Salminus brasiliensis

  2022cites this paper
• Inverted Repeats Scaffolding for a Dedicated Chloroplast Genome Assembler

  2022cites this paper
• Molecular organization of recombinant human-Arabidopsis chromosomes in hybrid cell lines

  2021cites this paper
• Population-scale detection of non-reference sequence variants using colored de Bruijn graphs

  2021cites this paper
• De novo assembled salivary gland transcriptome and expression pattern analyses for Rhipicephalus evertsi evertsi Neuman, 1897 male and female ticks

  2021cites this paper
• Topology-based sparsification of graph annotations

  2021cites this paper
• Identification of an Exopolysaccharide Biosynthesis Gene in Bradyrhizobium diazoefficiens USDA110

  2021cites this paper
• BLight: efficient exact associative structure for k-mers

  2021cites this paper