Answers are grounded in this paper and cite their sources.
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. 2012 ACM Subject Classification Theory of computation → Design and analysis of algorithms Digital Object Identifier 10.4230/LIPIcs.WABI.2026. Supplementary Material Software (Source Code) : https://github.com/LoreDepuydt/sbwt-set-operations Funding This work has benefited from funding from the French State under the France 2030 program, reference ANR-21-IDES-0006. The European Metropolis of Lille and the University of Lille are also acknowledged for their funding and support of the project WILL-CHAIRES-25-001-BOSSA.
No takes yet. Share an insight, caveat, or question.
Alanko et al. (2026) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: