Compressed Weighted de Bruijn Graphs

Giuseppe F Italiano (1, 2) , Nicola Prezza (3) , Blerina Sinaimeri (1, 2) , Rossano Venturini (4)

1 LUISS - Libera Università Internazionale degli Studi Sociali Guido Carli [Roma]
2 ERABLE - Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale
3 DAIS - Dipartimento di Scienze Ambientali, Informatica e Statistica [Venezia]
4 DI - Dipartimento di Informatica [Pisa]

We propose a new compressed representation for weighted de Bruijn graphs, which is based on the idea of delta-encoding the variations of k-mer abundances on a spanning branching of the graph. Our new data structure is likely to be of practical value: to give an idea, when combined with the compressed BOSS de Bruijn graph representation, it encodes the weighted de Bruijn graph of a 16x-covered DNA read-set (60M distinct k-mers, k = 28) within 4.15 bits per distinct k-mer and can answer abundance queries in about 60 microseconds on a standard machine. In contrast, state of the art tools declare a space usage of at least 30 bits per distinct k-mer for the same task, which is confirmed by our experiments. As a by-product of our new data structure, we exhibit efficient compressed data structures for answering partial sums on edge-weighted trees, which might be of independent interest.

Domaines: Informatique [cs]; Génétique

Giuseppe F Italiano, Nicola Prezza, Blerina Sinaimeri, Rossano Venturini. Compressed Weighted de Bruijn Graphs. CPM 2021 - 32nd Annual Symposium on Combinatorial Pattern Matching, Jul 2021, Wroclaw, Poland. pp.1-16, ⟨10.4230/LIPIcs.CPM.2021.16⟩. ⟨hal-03395413⟩