Simplitigs As an Efficient and Scalable Representation of De Bruijn Graphs

Overview

Journal Genome Biol

Specialties Biology
Genetics

Date 2021 Apr 7

PMID 33823902

Citations 19

Authors

Karel Brinda

Michael Baym

Gregory Kucherov

Affiliations

Soon will be listed here.

Abstract

de Bruijn graphs play an essential role in bioinformatics, yet they lack a universal scalable representation. Here, we introduce simplitigs as a compact, efficient, and scalable representation, and ProphAsm, a fast algorithm for their computation. For the example of assemblies of model organisms and two bacterial pan-genomes, we compare simplitigs to unitigs, the best existing representation, and demonstrate that simplitigs provide a substantial improvement in the cumulative sequence length and their number. When combined with the commonly used Burrows-Wheeler Transform index, simplitigs reduce memory, and index loading and query times, as demonstrated with large-scale examples of GenBank bacterial pan-genomes.

Citing Articles

Fractional hitting sets for efficient multiset sketching.

Rouze T, Martayan I, Marchet C, Limasset A Algorithms Mol Biol. 2025; 20(1):1.

PMID: 39923117 PMC: 11807336. DOI: 10.1186/s13015-024-00268-0.

Applications of de Bruijn graphs in microbiome research.

Dufault-Thompson K, Jiang X Imeta. 2024; 1(1):e4.

PMID: 38867733 PMC: 10989854. DOI: 10.1002/imt2.4.

Compression algorithm for colored de Bruijn graphs.

Rahman A, Dufresne Y, Medvedev P Algorithms Mol Biol. 2024; 19(1):20.

PMID: 38797858 PMC: 11129398. DOI: 10.1186/s13015-024-00254-6.

Compression Algorithm for Colored de Bruijn Graphs.

Rahman A, Dufresne Y, Medvedev P Lebniz Int Proc Inform. 2024; 273.

PMID: 38712341 PMC: 11071130. DOI: 10.4230/LIPIcs.WABI.2023.17.

Space-efficient computation of k-mer dictionaries for large values of k.

Diaz-Dominguez D, Leinonen M, Salmela L Algorithms Mol Biol. 2024; 19(1):14.

PMID: 38581000 PMC: 10996146. DOI: 10.1186/s13015-024-00259-1.

References

Kokot M, Dlugosz M, Deorowicz S . KMC 3: counting and manipulating k-mer statistics. Bioinformatics. 2017; 33(17):2759-2761. DOI: 10.1093/bioinformatics/btx304. View

Souvorov A, Agarwala R, Lipman D . SKESA: strategic k-mer extension for scrupulous assemblies. Genome Biol. 2018; 19(1):153. PMC: 6172800. DOI: 10.1186/s13059-018-1540-z. View

. Computational pan-genomics: status, promises and challenges. Brief Bioinform. 2016; 19(1):118-135. PMC: 5862344. DOI: 10.1093/bib/bbw089. View

Paten B, Novak A, Eizenga J, Garrison E . Genome graphs and the evolution of genome inference. Genome Res. 2017; 27(5):665-676. PMC: 5411762. DOI: 10.1101/gr.214155.116. View

Rahman A, Medevedev P . Representation of -Mer Sets Using Spectrum-Preserving String Sets. J Comput Biol. 2020; 28(4):381-394. PMC: 8066325. DOI: 10.1089/cmb.2020.0431. View

Zerbino D, Birney E . Velvet: algorithms for de novo short read assembly using de Bruijn graphs. Genome Res. 2008; 18(5):821-9. PMC: 2336801. DOI: 10.1101/gr.074492.107. View

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

Pevzner P . 1-Tuple DNA sequencing: computer analysis. J Biomol Struct Dyn. 1989; 7(1):63-73. DOI: 10.1080/07391102.1989.10507752. View

Li H, Durbin R . Fast and accurate short read alignment with Burrows-Wheeler transform. Bioinformatics. 2009; 25(14):1754-60. PMC: 2705234. DOI: 10.1093/bioinformatics/btp324. View

10.

Zielezinski A, Vinga S, Almeida J, Karlowski W . Alignment-free sequence comparison: benefits, applications, and tools. Genome Biol. 2017; 18(1):186. PMC: 5627421. DOI: 10.1186/s13059-017-1319-7. View

11.

Chikhi R, Limasset A, Jackman S, Simpson J, Medvedev P . On the representation of de Bruijn graphs. J Comput Biol. 2015; 22(5):336-52. DOI: 10.1089/cmb.2014.0160. View

12.

Ames S, Hysom D, Gardner S, Lloyd G, Gokhale M, Allen J . Scalable metagenomic taxonomy classification using a reference genome database. Bioinformatics. 2013; 29(18):2253-60. PMC: 3753567. DOI: 10.1093/bioinformatics/btt389. View

13.

Yu Y, Liu J, Liu X, Zhang Y, Magner E, Lehnert E . SeqOthello: querying RNA-seq experiments at scale. Genome Biol. 2018; 19(1):167. PMC: 6194578. DOI: 10.1186/s13059-018-1535-9. View

14.

Pandey P, Bender M, Johnson R, Patro R, Berger B . Squeakr: an exact and approximate k-mer counting system. Bioinformatics. 2018; 34(4):568-575. DOI: 10.1093/bioinformatics/btx636. View

15.

Merchant S, Wood D, Salzberg S . Unexpected cross-species contamination in genome sequencing projects. PeerJ. 2014; 2:e675. PMC: 4243333. DOI: 10.7717/peerj.675. View

16.

Li D, Liu C, Luo R, Sadakane K, Lam T . MEGAHIT: an ultra-fast single-node solution for large and complex metagenomics assembly via succinct de Bruijn graph. Bioinformatics. 2015; 31(10):1674-6. DOI: 10.1093/bioinformatics/btv033. View

17.

Bray N, Pimentel H, Melsted P, Pachter L . Near-optimal probabilistic RNA-seq quantification. Nat Biotechnol. 2016; 34(5):525-7. DOI: 10.1038/nbt.3519. View

18.

Melsted P, Pritchard J . Efficient counting of k-mers in DNA sequences using a bloom filter. BMC Bioinformatics. 2011; 12:333. PMC: 3166945. DOI: 10.1186/1471-2105-12-333. View

19.

Brinda K, Baym M, Kucherov G . Simplitigs as an efficient and scalable representation of de Bruijn graphs. Genome Biol. 2021; 22(1):96. PMC: 8025321. DOI: 10.1186/s13059-021-02297-z. View

20.

Pan T, Nihalani R, Aluru S . Fast de Bruijn Graph Compaction in Distributed Memory Environments. IEEE/ACM Trans Comput Biol Bioinform. 2018; 17(1):136-148. DOI: 10.1109/TCBB.2018.2858797. View