2026-08-28T20:53:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27522 2026-08-27T06:04:07Z ddc:004 open_access

Fast Set Operations for Compact k-mer Sets Alanko, Jarno N. Depuydt, Lore Marchet, Camille Puglisi, Simon J. Data Structures efficient Algorithms The k-mer spectrum of a set of sequences is the set of k-length substrings the sequences contain. This lossy representation of sequence content pervades modern genomics. Recently, the spectral Burrows-Wheeler transform (SBWT) has emerged as a space-efficient representation of k-spectra that also supports efficient k-mer lookup queries and, more generally, easy navigation of the de Bruijn graph of the k-spectrum. In this paper, we examine primitive set operations, such as intersection, union, and set difference, on SBWT-encoded k-spectra and show that these operations can be supported efficiently. Moreover, efficient merging leads directly to a new memory-efficient algorithm for SBWT construction, which was able to build the SBWT for the 661K bacterial dataset containing 88 billion distinct k-mers in 50 hours using 186 GiB of RAM and 112 GiB of disk space. Given the pervasiveness of k-mer sets in genomics and the continued rapid growth of genomic databases, our work opens the door to a wide array of future applications that manipulate and reason about genomic data by dealing directly with simultaneously compact and searchable k-mer set representations offered by the SBWT. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jarno N. Alanko and Lore Depuydt and Camille Marchet and Simon J. Puglisi 2026 Is Part Of LIPIcs, Volume 390, 26th International Conference on Algorithms for Bioinformatics (WABI 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WABI.2026.18 urn:nbn:de:0030-drops-275220 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2026.18 eng https://creativecommons.org/licenses/by/4.0/legalcode