Space-efficient and Exact De Bruijn Graph Representation Based on a Bloom Filter

Overview

Journal Algorithms Mol Biol

Publisher Biomed Central

Date 2013 Sep 18

PMID 24040893

Citations 132

Authors

Rayan Chikhi

Guillaume Rizk

Affiliations

Soon will be listed here.

Abstract

Background: 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).

Results: 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.

Conclusions: 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.

Citing Articles

Fast and Scalable Parallel External-Memory Construction of Colored Compacted de Bruijn Graphs with Cuttlefish 3.

Khan J, Dhulipala L, Patro R bioRxiv. 2025; .

PMID: 39975203 PMC: 11838517. DOI: 10.1101/2025.02.02.636161.

-mer approaches for biodiversity genomics.

Jenike K, Campos-Dominguez L, Bodde M, Cerca J, Hodson C, Schatz M Genome Res. 2025; 35(2):219-230.

PMID: 39890468 PMC: 11874746. DOI: 10.1101/gr.279452.124.

Phylogeographic and genetic insights into Sinonychia martensi: an endemic cave-dwelling harvestman in Beijing.

Xiao R, Zhao J, Zhao L, Derkarabetian S, Zhang F, Zhang C BMC Ecol Evol. 2025; 25(1):5.

PMID: 39773162 PMC: 11708087. DOI: 10.1186/s12862-024-02341-z.

A Whole-Genome Survey and the Mitochondrial Genome of Provide Insights into Its Phylogenetic Relationships in Priacanthiformes.

Mao W, Xu Z, Liu Q, Li N, Liu L, Ren B Animals (Basel). 2024; 14(22).

PMID: 39595310 PMC: 11590942. DOI: 10.3390/ani14223257.

Structural variation in the pangenome of wild and domesticated barley.

Jayakodi M, Lu Q, Pidon H, Rabanus-Wallace M, Bayer M, Lux T Nature. 2024; 636(8043):654-662.

PMID: 39537924 PMC: 11655362. DOI: 10.1038/s41586-024-08187-1.

References

Warren R, Holt R . Targeted assembly of short sequence reads. PLoS One. 2011; 6(5):e19816. PMC: 3092772. DOI: 10.1371/journal.pone.0019816. View

Kingsford C, Schatz M, Pop M . Assembly complexity of prokaryotic genomes using short reads. BMC Bioinformatics. 2010; 11:21. PMC: 2821320. DOI: 10.1186/1471-2105-11-21. View

Pell J, Hintze A, Canino-Koning R, Howe A, Tiedje J, Brown C . Scaling metagenome sequence assembly with probabilistic de Bruijn graphs. Proc Natl Acad Sci U S A. 2012; 109(33):13272-7. PMC: 3421212. DOI: 10.1073/pnas.1121464109. View

Idury R, Waterman M . A new algorithm for DNA sequence assembly. J Comput Biol. 1995; 2(2):291-306. DOI: 10.1089/cmb.1995.2.291. View

Peterlongo P, Chikhi R . Mapsembler, targeted and micro assembly of large NGS datasets on a desktop computer. BMC Bioinformatics. 2012; 13:48. PMC: 3514201. DOI: 10.1186/1471-2105-13-48. View

Rizk G, Lavenier D, Chikhi R . DSK: k-mer counting with very low memory usage. Bioinformatics. 2013; 29(5):652-3. DOI: 10.1093/bioinformatics/btt020. View

Li R, Zhu H, Ruan J, Qian W, Fang X, Shi Z . De novo assembly of human genomes with massively parallel short read sequencing. Genome Res. 2009; 20(2):265-72. PMC: 2813482. DOI: 10.1101/gr.097261.109. View

Peng Y, Leung H, Yiu S, Chin F . Meta-IDBA: a de Novo assembler for metagenomic data. Bioinformatics. 2011; 27(13):i94-101. PMC: 3117360. DOI: 10.1093/bioinformatics/btr216. View

Rizk G, Lavenier D . GASSST: global alignment short sequence search tool. Bioinformatics. 2010; 26(20):2534-40. PMC: 2951093. DOI: 10.1093/bioinformatics/btq485. View

10.

Sacomoto G, Kielbassa J, Chikhi R, Uricaru R, Antoniou P, Sagot M . KISSPLICE: de-novo calling alternative splicing events from RNA-seq data. BMC Bioinformatics. 2012; 13 Suppl 6:S5. PMC: 3358658. DOI: 10.1186/1471-2105-13-S6-S5. View

11.

Grabherr M, Haas B, Yassour M, Levin J, Thompson D, Amit I . Full-length transcriptome assembly from RNA-Seq data without a reference genome. Nat Biotechnol. 2011; 29(7):644-52. PMC: 3571712. DOI: 10.1038/nbt.1883. View

12.

Ye C, Ma Z, Cannon C, Pop M, Yu D . Exploiting sparseness in de novo genome assembly. BMC Bioinformatics. 2012; 13 Suppl 6:S1. PMC: 3369186. DOI: 10.1186/1471-2105-13-S6-S1. View

13.

Marcais G, Kingsford C . A fast, lock-free approach for efficient parallel counting of occurrences of k-mers. Bioinformatics. 2011; 27(6):764-70. PMC: 3051319. DOI: 10.1093/bioinformatics/btr011. View

14.

Conway T, Bromage A . Succinct data structures for assembling large genomes. Bioinformatics. 2011; 27(4):479-86. DOI: 10.1093/bioinformatics/btq697. View

15.

Iqbal Z, Caccamo M, Turner I, Flicek P, McVean G . De novo assembly and genotyping of variants using colored de Bruijn graphs. Nat Genet. 2012; 44(2):226-32. PMC: 3272472. DOI: 10.1038/ng.1028. View

16.

Salzberg S, Phillippy A, Zimin A, Puiu D, Magoc T, Koren S . GAGE: A critical evaluation of genome assemblies and assembly algorithms. Genome Res. 2011; 22(3):557-67. PMC: 3290791. DOI: 10.1101/gr.131383.111. View

17.

Simpson J, Wong K, Jackman S, Schein J, Jones S, Birol I . ABySS: a parallel assembler for short read sequence data. Genome Res. 2009; 19(6):1117-23. PMC: 2694472. DOI: 10.1101/gr.089532.108. View

18.

Miller J, Koren S, Sutton G . Assembly algorithms for next-generation sequencing data. Genomics. 2010; 95(6):315-27. PMC: 2874646. DOI: 10.1016/j.ygeno.2010.03.001. View