2026-08-07T05:10:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13967 2024-03-12T11:59:52Z ddc:004 open_access

Compressed Weighted de Bruijn Graphs Italiano, Giuseppe F. Prezza, Nicola Sinaimeri, Blerina Venturini, Rossano weighted de Bruijn graphs k-mer annotation compressed data structures partial sums 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Giuseppe F. Italiano and Nicola Prezza and Blerina Sinaimeri and Rossano Venturini 2021 Is Part Of LIPIcs, Volume 191, 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2021.16 urn:nbn:de:0030-drops-139675 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2021.16 eng https://creativecommons.org/licenses/by/4.0/legalcode