# FroM Superstring to Indexing: a space-efficient index for unconstrained k-mer sets using the Masked Burrows-Wheeler Transform (MBWT)

Ondřej Sladký, Pavel Veselý, Karel Břinda

► To cite this version:

Ondřej Sladký, Pavel Veselý, Karel Břinda. FroM Superstring to Indexing: a space-efficient index for unconstrained k-mer sets using the Masked Burrows-Wheeler Transform (MBWT). Bioinformatics Advances, 2025, pp.1-10. 10.1093/bioadv/vbaf290. hal-04764171v3

HAL Id: hal-04764171

https://inria.hal.science/hal-04764171v3

Submitted on 14 Nov 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Bioinformatics Advances, 2025, 1–10

doi: ...

# FroM Superstring to Indexing: a space-efficient index for unconstrained *k*-mer sets using the Masked Burrows-Wheeler Transform (MBWT)

Ondřej Sladký,¹,²,* Pavel Veselý²,* and Karel Břinda³,*

¹ETH Zurich, Switzerland, ²Charles University, Czechia and ³Inria, Irisa, Univ. Rennes, France

*Correspondence: ondra.sladky@gmail.com, vesely@iuuk.mff.cuni.cz, karel.brinda@inria.fr

## Abstract

The growing volumes and heterogeneity of genomic data call for scalable and versatile *k*-mer-set indexes. However, state-of-the-art indexes such as SBWT and SSHash depend on long non-branching paths in de Bruijn graphs, which limits their efficiency for small *k*, sampled data, or high-diversity settings. Here, we introduce FMSI, a superstring-based index for arbitrary *k*-mer sets that supports efficient membership and compressed dictionary queries with strong theoretical guarantees. FMSI builds on recent advances in *k*-mer superstrings and uses the Masked Burrows-Wheeler Transform, a novel extension of the classical Burrows-Wheeler Transform that incorporates position masking. Across a range of *k* values and dataset types – including genomic, pangenomic, and metagenomic – FMSI consistently achieves superior query space efficiency, using up to 2–3× less memory than state-of-the-art methods, while maintaining competitive query times. Only a space-optimized version of SBWT can match the FMSI’s footprint in some cases, but then FMSI is 2–3× faster. Our results establish superstring-based indexing as a robust, scalable, and versatile framework for arbitrary *k*-mer sets across diverse bioinformatics applications.

**Key words:** *k*-mer sets, shortest superstring, Burrows-Wheeler Transform, membership queries, compressed dictionary

## Introduction

The exponential growth of DNA sequencing data calls for efficient approaches for their compression and search (Loh et al., 2012; Stephens et al., 2015). To address the growing complexity of data, modern bioinformatics methods increasingly rely on *k*-mer tokenization for data storage and analysis. This strategy enables a unified representation of various types of genomic data, including sequencing reads, transcripts, assemblies, or species pangenomes. Notable applications of *k*-mer-based methods include large-scale data search (Bradley et al., 2019; Bingmann et al., 2019; Břinda et al., 2025; Karasikov et al., 2025), metagenomic classification (Wood and Salzberg, 2014; Břinda et al., 2017), rapid diagnostics (Bradley et al., 2015; Břinda et al., 2020), and transcript abundance quantification (Bray et al., 2016; Patro et al., 2017). An essential low-level functionality is the storage, and membership and dictionary queries on single *k*-mer sets (Marchet et al., 2021a).

A key challenge is to design *k*-mer set data structures that can scale with the set size and simultaneously adapt to the structural characteristics of different sets. Comprehensive databases now reach hundreds of billions of *k*-mers (Karasikov et al., 2025) and continue to grow rapidly. At the same time, their structural complexity is increasing due to denser sampling of genetic polymorphisms and

the accumulation of technological artifacts. Although advances in *k*-mer sampling (Wood and Salzberg, 2014) and sketching (Ondov et al., 2016) techniques sets can alleviate size issues in some applications, the resulting *k*-mer sets are then less amenable to standard compression techniques.

The efficiency of *k*-mer set data structures is tightly connected to the compressive properties of their support representations. Real-world *k*-mer sets are largely non-random, and a wisely chosen indexable representation allows one to exploit redundancies, going beyond the traditional information-theoretic lower bounds (Conway and Bromage, 2011). Of particular benefit has been the so-called *spectrum-like property*, stating that *k*-mer sets are typically generated by a small number of long strings (Chikhi et al., 2022). As these strings correspond to paths in the associated de Bruijn graphs (dBG), indexing dBG paths enables efficient indexes for the original *k*-mer sets.

State-of-the-art methods for indexing dBG paths typically use one of two approaches: either they proceed implicitly by indexing successor *k*-mers in the graph (Bowe et al., 2012; Alanko et al., 2023), or they enumerate a path cover of the dBG explicitly and then index it using either hash-based (Marchet et al., 2021b; Pibiri, 2022) or full-text (Chikhi et al., 2015; Rahman and Medvedev, 2021; Břinda et al., 2021; Marchet et al., 2021b; Pibiri, 2022) techniques.

<figure><img src="image_2.png" /></figure>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
We refer to such explicit path-cover representations as *Spectrum-Preserving String Sets* (SPSS), and refer to the literature for more details (Břinda et al., 2021; Rahman and Medvedev, 2021; Schmidt and Alanko, 2023; Schmidt et al., 2023). Efficient SPSS computation is now supported by a wide range of software tools (Chikhi et al., 2016; Minkin et al., 2016; Holley and Melsted, 2020; Břinda et al., 2021; Rahman and Medvedev, 2021; Schmidt and Alanko, 2023; Schmidt et al., 2023; Khan and Patro, 2021; Khan et al., 2022, 2025; Cracco and Tomescu, 2023).

However, the compression power of dBG-based methods is fundamentally limited by the existence of (k − 1)-long overlaps between the indexed k-mers. Even when a fraction of k-mers do not share (k − 1)-long overlaps with other k-mers, long paths in the graph cannot be formed, and the corresponding k-mer pairs cannot be jointly compressed, impacting all these indexing methods. The resulting fragmentation causes time and space inefficiencies at all levels, especially in applications involving complex metagenomic or pangenomic k-mer sets, or when the sets are subsampled.

Masked superstrings (Sladký et al., 2023) eliminate the dependency on (k − 1)-long overlaps. A masked superstring consists of a superstring of the original k-mer set, along with an associated mask that encodes the introduced “false positive” k-mers. Masked superstrings can represent arbitrary k-mer sets in text form while leveraging overlaps of all possible lengths. Conceptually, this corresponds to replacing dBGs with overlap graphs to construct the path cover. Masked superstrings thus unify all SPSS-based representations while enabling further data reduction by using shorter k-mer overlaps as well. Importantly, approximately shortest masked superstrings can be efficiently computed using greedy approaches implemented in KmerCamel (Sladký et al., 2023) (https://github.com/ondrejsladky/kmercamel), starting from either the original k-mer set or a precomputed SPSS.

However, masked superstrings are not indexable using existing methods. While the superstring itself can be indexed with full-text indexing, this yields an inexact data structure with false positives. A straightforward inclusion of masks would require recovering the positions of k-mers in the support superstring, which in turn necessitates auxiliary data structures, such as the subsampled suffix array, thereby increasing both the space and time requirements of queries (Salikhov et al., 2018; Břinda et al., 2021). Furthermore, efficient query processing in real-world applications often relies on streaming consecutive k-mers; yet, masked superstrings are incompatible with existing BWT-based streaming techniques (Salikhov et al., 2018; Salikhov, 2017; Alanko et al., 2023) due to complications arising from k-mer canonicity when minimizing index size. Finally, in downstream applications requiring index associativity, to retain high space efficiency even for subsampled k-mer sets, the index must support the full functionality of compressed k-mer dictionaries (Pibiri, 2022).

Here, we introduce FMSI, a scalable data structure and software for space-efficient membership and dictionary queries over k-mer sets with arbitrary structure, with support for accelerated streamed queries. FMSI combines compact k-mer set representation using approximately shortest masked superstrings (Sladký et al., 2023) with indexing via the Burrows-Wheeler Transform (BWT) (Burrows and Wheeler, 1994), extended to accommodate for masks. The resulting index provides strong theoretical guarantees on space for arbitrary k-mer sets, including those resulting from sampling and sketching. We implement this in a program called FMSI (https://github.com/ondrejsladky/fmsi) and demonstrate its superior

space efficiency across a broad range of datasets and use cases compared to current state-of-the-art k-mer-set indexing methods.

Methods

Problem formulation

Let us consider the nucleotide alphabet {A, C, G, T}. For a fixed $k > 0$, *k*-mers are strings of length *k* over this alphabet. We assume the *bidirectional model* (formalized, e.g., in (Chikhi et al., 2016, online suppl.), (Schmidt and Alanko, 2023)), where a *k*-mer and its reverse complement (RC) are considered equal, unless the *unidirectional model* is explicitly indicated. We are interested in providing the following indexing functionality for a *k*-mer set *K*.

(P1) **Membership.** Single $O(k)$-time operation:

▷ **MEMBER**(*Q*): Determine if a given *k*-mer *Q* is in *K*.

(P2) **Dictionary.** Two $O(k)$-time operations enabling a bijec-
tive mapping between *k*-mers $Q \in K$ and a discrete interval
of hash values $H = \{0, ..., |K| - 1\}$:

▷ **LOOKUP**(*Q*): Return the hash $h \in H$ of *Q*, or $-1$ if $Q \notin K$.

▷ **ACCESS**($h$): Return the *k*-mer *Q* corresponding to $h \in H$.

(P3) **Streaming.** **MEMBER/LOOKUP** in $O(1)$ time for a *k*-mer *Q* following a query for *k*-mer *Q'* when the (*k*−1)-long prefix of *Q* is a suffix of *Q'* and both *Q*, *Q'* ∈ *K*.

The dictionary index (P2) corresponds to evaluating a *minimal perfect hash function* with rejection and its inverse. (P2) is more general than (P1), but (P1) can be implemented more efficiently. (P3) corresponds to extending the core data structure for isolated queries by a component for rapid FWD or BWD operations (as defined in (Chikhi et al., 2022)), thus trading a small additional space for improving the time efficiency of positive streamed queries.

Our goal is to develop a data structure that simultaneously
addresses four challenges. First, it should minimize space require-
ments while maintaining competitive query speed. Second, it must
make no assumptions about the structure in the data, such as
about the presence of many (k − 1)-long overlaps. Third, when
structural regularities such as overlaps are available, the method
should be able to exploit them. Fourth, the data structure should
be available in four optimized variants, each targeting a specific
functionality: a membership index (P1), a compressed dictionary
(P2), and two extended versions with streaming support (P1+P3
and P2+P3, respectively).

Two core ingredients of FMSI

Our approach is based on indexing approximately shortest su-
perstrings of the input *k*-mers, using a technique based on the
BWT (Burrows and Wheeler, 1994) (Fig. 1). Depending on the
desired functionality (Fig. 1A), we compute a particular variant
of the masked superstring representation (Sladký et al., 2023),
obtain the BWT image of superstring together with an appropri-
ate mask transformation, and complete the data structure with
supporting rank and select data structures into an exact index
termed FMSI (Fig. 1B). FMSI shares similarities but is differ-
ent from existing BWT-based approaches such as dbgFM (Chikhi
et al., 2015; Rahman and Medvedev, 2021), BWA (Li, 2012; Břinda
et al., 2021)/ProPhex (Salikhov, 2017; Salikhov et al., 2018), and
SBWT (Alanko et al., 2023) (Fig. 1C, Tab. 1).
<figure><img src="image_3.png" /><figcaption>**Fig. 1:** Overview of the FMSI method. Concepts related to input *k*-mers and masks are shown in violet and green, respectively. **A) Core FMSI functionality.** FMSI indexes regular or subsampled *k*-mer sets and supports both membership or dictionary queries. Unlike other approaches, its representation remains compact even without (*k* − 1)-long overlaps. **B) FMSI index construction.** A greedy global algorithm (Sladký et al., 2023) approximates the shortest superstring of the input *k*-mer set; the resulting mask is optimized for the target functionality (P1 or P2). The masked superstring is transformed via the Masked BWT (**Def. 1** and **Alg. 1**) and equipped with rank/select data structures. Optionally, the *k*-LCP array (Salikhov, 2017) can be computed to accelerate streamed queries. **C) Comparison with other BWT-based indexes.** dbgFM (Chikhi et al., 2015; Rahman and Medvedev, 2021) indexes $-$separated SPSS using an FM index without a sampled inverse suffix array. BWA/ProPhex (Li, 2012; Břinda et al., 2021; Salikhov, 2017; Salikhov et al., 2018) index SPSS concatenations, avoiding false matches at simplitig borders by checking simplitigs' start positions. SBWT (Alanko et al., 2023) indexes dBG paths via *k*-mer successors. Only FMSI removes redundancy among *k*-mers with overlaps shorter than *k* − 1.</figcaption></figure>

1. Approximately shortest masked superstrings of k-mers

A masked superstring representation (Sladký et al., 2023) of a given
k-mer set K consists of two parts: a superstring S of the k-mers,
i.e., a single string containing all the k-mers in K as substrings, and
a binary mask M determining which of the k-mers appearing in S
are represented. A k-mer is considered represented by a masked
superstring (S, M) if at least one of its occurrences in S has the
corresponding mask symbol set to 1, and the set of represented k-
mers should be equal to K. Since it is sufficient to mask each k-mer
as present only once, this makes the mask nonunique, allowing for
additional mask optimization. Masked superstrings unify all SPSS
representations and provide a more general framework with better
compression properties (Sladký et al., 2023).

Here, we consider uniquely masked superstrings obtained via
greedily approximated shortest superstrings (Sladký et al., 2023)
and, based on the target functionality, masked to have either the
maximum or the minimum number of ones, termed max-one or
min-one masked superstrings, respectively (Steps 1, 2 in Fig. 1b).
Given input k-mer data, such a superstring can be efficiently ap-
proximated by the global greedy algorithm as implemented in
KmerCamel (Sladký et al., 2023), with possible acceleration via
parallelized SPSS precomputation. The output min-one masked
superstring can further be converted to max-one using a two-pass
algorithm (Sladký et al., 2023).

<table><caption>**Table 1.** Functional comparison of FMSI with state-of-the-art single-set *k*-mer indexes. BWA Fastmap (Li, 2012) on simplitigs (Břinda et al., 2021), dbgFM (Chikhi et al., 2015; Rahman and Medvedev, 2021), SSHash (Pibiri, 2022), CBL (Martayan et al., 2024), and SBWT (Alanko et al., 2023).</caption>
  <thead>
    <tr>
      <th></th>
      <th>P1: Memb.</th>
      <th>P2: Dict.</th>
      <th>P3: Stream.</th>
      <th>Scalable</th>
      <th>Dynamic</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td>BWA</td>
      <td>✓</td>
      <td>✗</td>
      <td>ProPhex<br>(Salikhov, 2017)<br>(Salikhov et al., 2018)</td>
      <td>✓</td>
      <td>✗</td>
    </tr>
    <tr>
      <td>dbgFM</td>
      <td>✓</td>
      <td>ABySS<br>(Simpson et al., 2009)</td>
      <td>✗</td>
      <td>✗</td>
      <td>✗</td>
    </tr>
    <tr>
      <td>SSHash</td>
      <td>✓</td>
      <td>✓</td>
      <td>✓</td>
      <td>✓</td>
      <td>✗</td>
    </tr>
    <tr>
      <td>CBL</td>
      <td>✓</td>
      <td>✗</td>
      <td>✓</td>
      <td>✓</td>
      <td>✓</td>
    </tr>
    <tr>
      <td>SBWT</td>
      <td>✓</td>
      <td>✗</td>
      <td>✓</td>
      <td>✓</td>
      <td>✗</td>
    </tr>
    <tr>
      <td>FMSI</td>
      <td>✓</td>
      <td>✓</td>
      <td>✓</td>
      <td>✓</td>
      <td>f-MS<br>(Sladký<br>et al., 2025)</td>
    </tr>
  </tbody>
</table>

2. Masked Burrows-Wheeler Transform

We index the resulting masked superstring using the *Masked Burrows Wheeler Transform*, an extension of the traditional BWT (Burrows and Wheeler, 1994) with support for masks in the suffix array (SA) order (Fig. 1b).
Second, we analyze the storage requirement of FMSI – first, in the general case of arbitrary *k*-mer sets, and then when the underlying superstring size approaches the number of distinct canonical *k*-mers (e.g., only 4% difference for the human genome and *k* = 31; **Tab. 3**).

**Lemma 3** (FMSI storage requirements) *Given a masked superstring (S, M) of a *k*-mer set K, the corresponding FMSI-memb and FMSI-dict indexes require $2|S| + \log(|S|)$ bits, which is at most $(3 + o(1)) \cdot |S|$. Furthermore, if $|S| = |K| + o(|K|)$, the index requires $2 + o(1)$ bits per distinct canonical *k*-mer.*

*Proof S'* stored as a plain bit-vector-based wavelet tree (Grossi et al., 2003) requires $2 + o(1)$ bits per character, including the rank and select support. *M'* stored using a zeroth-order entropy compression (Raman et al., 2007; Feigenblat et al., 2016) requires $\log(|S|)$ bits. Both rank and select for the compressed vector *M'* occupy only sublinear space (Raman et al., 2007; Feigenblat et al., 2016). Last, suppose that $|S| = |K| + \Delta$ with $\Delta \in o(|K|)$. Letting $\Delta = \frac{|K|}{f(|K|)}$ for $f(|K|) \to \infty$ as $|K| \to \infty$, the space complexity of *M'* is $\log(|S|)$, $\le \log(|K|+\Delta)$, $\le \Delta \log(\frac{2c|K|}{\Delta}) = |K| \frac{\log(2c f(|K|))}{f(|K|)} = o(|K|)$ and, thus, the index requires $2 + o(1)$ bits per distinct *k*-mer. □

## FMSI membership and dictionary queries

FMSI can act as two slightly different data structures, a membership index and a dictionary, with membership queries being slightly more space- and time-efficient (**Tab. 2**). In both cases, the search starts with the standard backward search, as used, e.g., in the FM index, resulting in a suffix array (SA) interval corresponding to occurrences of the query *k*-mer in the superstrings (**Alg. 2**). The backward search uses the “count” values for characters *c*, denoted $|S|_{<c}$ and equal to the total number of occurrences of all characters $c' < c$ in *S*, which can be computed during the FMSI construction in constant space. The candidate *k*-mer matches in the SA intervals, if non-empty, are subsequently validated against *M'* to exclude false positives or to obtain the *k*-mer’s hash (**Alg. 3**). In the bidirectional model, everything works the same way with only one difference: If the forward *k*-mer is not found in the superstring, we subsequently query also the RC of the *k*-mer.

**Membership queries.** In FMSI-memb, MEMBER is evaluated by inspecting the first bit of the SA-transformed mask within the interval $[i, j)$ obtained via backward search (**Alg. 3**). This is possible thanks to the max-one property of the mask, which ensures that all bits in the interval are set to the same value.

**Dictionary queries.** FMSI-dict supports the LOOKUP operation via additional rank data structure, required for two additional invocations of *M'*.*rank to compute $r_i = M'*.rank(1, i)$ and $r_j = M'*.rank(1, j)$ (**Alg. 3**). If $r_i = r_j$, the *k*-mer is not in *K* and is reported as absent from the dictionary; otherwise, $r_i$ is returned as its unique minimal hash. This is possible thanks to the min-one property of the mask, which ensures that $r_i$ equals the number of distinct represented *k*-mers appearing before the queried *k*-mer in the SA order, making $r_i$ both unique and minimal.

In the other direction, ACCESS requires select data structures for both *S'* and *M'*. It is evaluated via *M'*.*select(*h*), which returns the position *i* of the *h*-th occurrence of 1 in *M'*. This position marks the start of the SA interval corresponding to the queried *k*-mer *Q*,

<table><caption>**Table 2.** Query time and memory usage for membership vs. dictionary queries. Comparison of query time (per query *k*-mer, *μs*) and memory (bits per distinct canonical *k*-mer, in *italics*) on three datasets with *k* = 31. See Experimental Evaluation.</caption><thead><tr><th>Dataset</th><th>FMSI-memb</th><th>FMSI-dict</th></tr></thead><tbody><tr><td>ec-pg-hq</td><td>17.2 | 3.3</td><td>20.5 | 3.4</td></tr><tr><td>mtg-ilm</td><td>7.7 | 3.6</td><td>14.6 | 3.7</td></tr><tr><td>hg-t2t</td><td>11.4 | 2.4</td><td>14.8 | 2.4</td></tr></tbody></table>

<table><thead><tr><th>Method</th><th>SPSS</th><th>MS</th><th>Index</th><th>Overall</th></tr></thead><tbody><tr><td>CBL</td><td>-</td><td>-</td><td>38.4 | 101.1</td><td>38.4 | 101.1</td></tr><tr><td>SBWT-small</td><td>-</td><td>-</td><td>21.5* | 49.9</td><td>21.5* | 49.9</td></tr><tr><td>SBWT-fast</td><td>-</td><td>-</td><td>39.5* | 93.1</td><td>39.5* | 93.1</td></tr><tr><td>SSHash<sup>†</sup></td><td>30.5* | 21.6</td><td>-</td><td>14.6 | 10.9</td><td>45.1 | 21.6</td></tr><tr><td>FMSI-memb</td><td>30.5* | 21.6</td><td>25.3 | 39.0</td><td>15.4 | 44.2</td><td>71.2 | 44.2</td></tr><tr><td>FMSI-dict<sup>†</sup></td><td>30.5* | 21.6</td><td>14.1 | 1.7</td><td>18.8 | 44.2</td><td>63.4 | 44.2</td></tr></tbody></table>

<caption>**Table 3.** Index construction resources on human genome. CPU time of construction (usr+sys, minutes) and memory usage (GB, in *italics*) for the human genome dataset and *k* = 31. The greedily computed superstring had length $|S| = 2.602$ G, with $|K| = 2.512$ G. See Experimental Evaluation.</caption>

which we then reconstruct in *k* steps by iteratively applying select on *S'* (**Alg. 3**).

**Queries with unoptimized masks.** Membership operations are possible with masks other than max-one, but at the cost of additional time overhead due to two invocations of rank on *M'* to determine the presence of 1 in the SA interval via *M'*.*rank(1, *i*) < *M'*.*rank(1, *j*). Likewise, dictionary operations are possible with masks other than min-one, but at the cost of losing the contiguity and surjectivity of hash values, as their range length increases by $|M|_1 - |K|$.

## Streaming acceleration

In many practical scenarios, *k*-mers are queried in batches consisting of all overlapping *k*-mers of a given query string, such as a sequencing read or a genomic element. Streamed queries are often predominantly positive, e.g., when a query gene differs only in one nucleotide due to a single mutation. By positive streamed queries, we mean a query for (all occurrences of *k*-mers of) a string *T* such that all the *k*-mers of *T* are present in the represented *k*-mer set.

To accelerate positive streamed queries, we use the *k*LCP array technique, originally developed in the context of *k*-mer indexing with FM-indexes (Salikhov, 2017) and previously implemented in ProPhex (Salikhov et al., 2018). This technique is based on the bit-vector of the same length as *S* such that the *i*-th bit is set to 1 if and only if the longest common prefix between the *i*-th and (*i* + 1)-th suffixes of *S* in the lexicographic order has length at least *k* − 1. This allows us to obtain a range corresponding to a (*k* − 1)-mer obtained after deleting the last character. In the unidirectional model, this immediately gives fast positive streamed queries, in the bidirectional model, we need to ensure that we query most *k*-mers first in the direction in which they appear in the superstring.

**Unidirectional streaming via *k*LCP.** Without taking RCs into account, we traverse the query sequence in the reverse direction (**Alg. 2**). Starting from the last *k*-mer, after we have queried a present *k*-mer, we obtain the range for its prefix of size *k* − 1 by extending the range in the SA coordinates in both directions to the first 0 in the *k*LCP array using two rank and select operations. To get the range for the next *k*-mer, we perform an update of the range with its first character, i.e., one step of the backward search, which only costs *O*(1) time in total. Only when the current queried

<footnote><sup>†</sup> indexes supporting dictionary queries * with 8 threads (1 otherwise)</footnote>
<table><caption>**Table 4.** Memory and disk usage across *k*-mer sizes for membership query indexes. Reported values are in bits per canonical *k*-mer, measured across all benchmark datasets and indicated *k*-mer sizes. Space usage was measured in memory (via GNU time; larger numbers) and on disk (smaller, italicized numbers). The best lower and upper value for each dataset is indicated by asterisk (*). Due to memory constraints (>251 GiB), CBL could not be evaluated for **hg-t2t** at *k* > 39.</caption><thead><tr><th>Dataset</th><th>k</th><th>31-mers</th><th>CBL</th><th>SSHash</th><th>SBWT-fast</th><th>SBWT-small</th><th>FMSI</th></tr></thead><tbody><tr><td>sc2-pg</td><td>15, 17, ... 43</td><td>12.7 M</td><td>153.8-654.1</td><td>46.6-78.7</td><td>14.0-25.0</td><td>10.7-19.3</td><td>16.0-50.8</td><td>3.2*-5.0</td><td>5.5*-9.0*</td><td>3.4-3.7*</td></tr><tr><td>sp-pg</td><td>15, 17, ... 43</td><td>9.62 M</td><td>150.3-300.9</td><td>47.5-88.9</td><td>8.2-22.6</td><td>5.5-18.0</td><td>29.9-45.9</td><td>9.2-9.8</td><td>24.5-41.4</td><td>3.6-5.1</td><td>6.1*-7.4*</td><td>2.8*-3.4*</td></tr><tr><td>ec-pg-hq</td><td>15, 17, ... 43</td><td>551 M</td><td>34.3-173.0</td><td>20.7-80.9</td><td>6.6-22.7</td><td>6.6-22.6</td><td>9.0-9.7</td><td>8.5-8.6</td><td>3.4-7.8</td><td>3.1-6.6</td><td>3.1*-3.5*</td><td>2.8*-3.3*</td></tr><tr><td>ec-pg-all</td><td>15, 23, ... 31</td><td>1.32 G</td><td>25.5-69.0</td><td>18.7-48.9</td><td>7.6-22.0</td><td>7.5-21.9</td><td>8.8-9.2</td><td>8.5-8.6</td><td>3.1-7.8</td><td>2.9-7.1</td><td>2.9*-3.0*</td><td>2.7*-2.8*</td></tr><tr><td>mtg-ilm</td><td>15, 17, ... 31</td><td>355 M</td><td>37.1-65.5</td><td>21.0-50.9</td><td>7.8-22.7</td><td>7.7-22.6</td><td>9.5-10.8</td><td>8.6-10.1</td><td>3.7-7.3</td><td>3.1-6.1</td><td>3.0*-3.7*</td><td>2.8*-3.4*</td></tr><tr><td>rna-ilm</td><td>15, 23, ... 31</td><td>686 M</td><td>39.6-130.4</td><td>20.5-48.8</td><td>14.9-22.8</td><td>14.9-22.6</td><td>9.7-14.4</td><td>8.7-14.0</td><td>4.8-7.8</td><td>4.4-6.7</td><td>3.3*-6.2*</td><td>3.0*-5.9*</td></tr><tr><td>hg-ilm</td><td>15, 23, ... 31</td><td>3.56 G</td><td>25.1-341.1</td><td>18.6-48.5</td><td>10.8-20.6</td><td>10.8-20.6</td><td>9.2-10.5</td><td>8.5-10.4</td><td>3.5-8.5</td><td>3.4-7.8</td><td>2.9*-4.1*</td><td>2.6*-3.9*</td></tr><tr><td>hg-t2t</td><td>15, 17, ... 43</td><td>2.51 G</td><td>21.1-597.0</td><td>19.0-73.1</td><td>5.9-24.2</td><td>5.9-24.2</td><td>8.6-9.2</td><td>8.5-8.5</td><td>2.4*-8.0</td><td>2.3-7.3</td><td>2.4*-3.0*</td><td>2.2*-2.9*</td></tr><tr><td>Overall</td><td></td><td></td><td>21.1-654.1</td><td>18.6-88.9</td><td>5.9-25.0</td><td>5.5-24.2</td><td>8.6-56.0</td><td>8.5-14.0</td><td>2.4*-50.8</td><td>2.3-7.8</td><td>2.4*-9.0*</td><td>2.2*-5.9*</td></tr></tbody></table>

*k*-mer does not appear in the superstring, we perform the backward search for the next *k*-mer in time *O*(*k*).

**Streaming bidirectionality via saturating strand counters.** In the bidirectional model, consecutive queried *k*-mers may change directionality in the superstring; however, the *k*-LCP extension technique supports only one fixed direction. Nevertheless, streaming can still be accelerated locally if we can split queries into locally consistent parts and query them in the right direction. As a simple but effective heuristic, we split queries into blocks of size *B*, and for each block we estimate the likely dominating directionality of its *k*-mers via a saturating counter. Specifically, whenever a *k*-mer is found on the forward strand, we increment the counter, and decrement otherwise (and vice versa for the reverse strand). Then, the directionality of the next block can be estimated based on the statistics stored in this counter, informing whether the block should be first reverse-complemented or not.

This technique provides favorable theoretical time guarantees for positive streamed queries, both in the unidirectional and bidirectional model (Lemma 4). For the unidirectional model, we have slightly better guarantees; however, the difference vanishes as the size of the query sequence grows. The speedup in the bidirectional model assumes that consecutive *k*-mers do not change strand in the superstring too often; for example, this readily holds for greedy superstrings built from *k*-mer sets corresponding to dBGs with limited branching.

**Lemma 4** Given an FMSI index over a masked superstring (*S*, *M*) of a *k*-mer set *K*, and a query sequence *T* containing *t* = |*T*| - *k* + 1 occurrences of *k*-mers from *K*, streamed queries can be processed such that:

* In the unidirectional model, querying *T* takes time *O*(*t* + *k*) = *O*(|*T*|), or *O*(*t* + *k/t*) per *k*-mer.

* In the bidirectional model, if there are at most *O*(*t*/*k*²) pairs of consecutive *k*-mers *Q*ᵢ, *Q*ᵢ₊₁ in *T*, such that *Q*ᵢ₊₁ does not appear on the same strand as *Q*ᵢ in *S*, then querying *k*-mers in *T* takes time *O*(*t* + *k√t*), or *O*(*t* + *k/√t*) per *k*-mer.

**Proof sketch.** Querying the last *k*-mer of *T* takes *O*(*k*) time. In the unidirectional model, since all queries are positive, every other *k*-mer of *T* can be queried in *O*(*t*) time as explained above.

In the bidirectional model, let *B* = min(*√t*, *k*). We split *T* into blocks of size *Θ*(*B*). For each of these blocks, we predict whether the *k*-mer or its RC are in *S* using the saturating counter with

small constant saturation computed on previous blocks, which predicts to start with the strand with which the previous block ended with. We process the first block in time at most *O*(*B*·*k*). For other blocks, we spend time *O*(*k*) on the first *k*-mer. Then, if we predict the strand correctly and the strand does not change during the block, we spend time *O*(*k* + *B*) per block, and otherwise, we spend time *O*(*k*) for each *k*-mer. The total time spent on blocks in the former case is thus *O*(*t*/*B*·(*B* + *k*)) = *O*(*t* + *k*·√*t*). The latter can happen if consecutive *k*-mers switch strands either inside the block, in the previous block, or between blocks which may cause an incorrect prediction. However, such switching happens at most *O*(*t*/*k*²) times in total and hence, the total time complexity is bounded by *O*(*B*·*k* + *t* + *k*·√*t* + (*t*/*k*²)·*B*·*k*), which is always bounded by *O*(*t* + *k√t*). ☐

Implementation in the FMSI program

We implemented the FMSI index in a tool called FMSI, an abbreviation of ‘FroM Superstring to Indexing’. FMSI is developed in C++, provided on Github under the MIT licence (https://github.com/OndrejSladky/fmsi), deposited on Zenodo (https://doi.org/10.5281/zenodo.13905020), and distributed via Bioconda (Grüning et al., 2018). The version of FMSI used in this paper is 0.4.0. FMSI can calculate an index for user-provided masked superstring (*S*, *M*) for an arbitrary *k*, and then query it with Membership or Lookup queries, possibly streamed. The input masked superstring can be computed by KmerCamel, or alternatively inferred from any SPSS representation.

The index in the FMSI software consists of three components: *S'* as a BWT image of *S* (stored via a wavelet tree over non-compressed plain bit-vectors), *M'* as the corresponding SA-transformed mask (an RRR-compressed bit-vector (Raman et al., 2007)), and an optional *k*-LCP array (a plain bit-vector), all based on the sdsl-lite library (Gog et al., 2014). MBWT computation proceeds via suffix array construction using QSufSort (Larsson and Sadakane, 2007).

For single-*k*-mer queries, we also utilize the strand prediction technique we described for streamed queries. If a *k*-mer is not found in the superstring (Alg. 2 and 3), its RC is also queried, starting from a predicted strand (using a counter with saturation 7). FMSI uses two additional counters, to accumulate and predict only if the previous *k*-mer was found in the forward or reverse direction respectively. Streaming (Alg. 2) additionally simplifies the range extension: the *k*-LCP array is traversed in both directions until 0s are found, avoiding the additional rank data structures. Bidirectionality is supported via splitting each queried sequence of
length *l* into parts of size $|2\sqrt{l}|$. The initial query strand of each part is predicted from the saturating counters of the preceding parts, with only the first strand queried entirely and the other one only for the not-yet-found *k*-mers.

## Experimental Evaluation

**Experimental setup.** We benchmarked FMSI against three state-of-the-art indexes for single *k*-mer sets: SBWT (Spectral Burrows-Wheeler Transform (Alanko et al., 2023), commit b795178), SSHash (Pibiri, 2022), version 3.0.0), CBL (Conway-Bromage-Lyndon (Martayan et al., 2024), commit 328bcc6), each configured as recommended by their authors. Specifically, SSHash used minimizer sized as min{$[\log_4|K| + 1, k - 2$} and indexes based on optimal simplitigs (eulertigs) computed by GGCAT (Cacco and Tomescu, 2023). CBL was independently compiled per *k*-mer size, with SIMD support and 28 prefix bits. SBWT was evaluated in two distinct modes: a standard mode optimized for speed (SBWT-fast, with a plain matrix and index with RCs) and mode tuned for minimum memory (SBWT-small, with RRR-split and index without RCs), both considered with and without streaming support. DbgFM (Chikhi et al., 2015) was excluded due to scalability issues and recurrent index construction failures.

We selected eight datasets representative of diverse tradeoffs between *k*-mer set sizes and sets' structural properties common across bioinformatics applications: SARS-CoV-2 pangenome (sc2-pg; n=17M; GISAID; Shu and McCauley (2017)), S. pneumoniae pangenome (sp-pg; n=616; Croucher et al. (2015)), E.coli 661k pangenomes (Blackwell et al., 2021) with (ec-pg-hq; n=86K) and without (ec-pg-all; n=89K) quality filtering, metagenomic Illumina reads of a human tongue microbiome (mtg-ilm; SRX023459), RNA-seq Illumina reads (rna-ilm; SRX348811), human T2T assembly (hg-t2t; chm13v2.0; Nurk et al. (2022)), and human WGS Illumina reads (hg-ilm; SRX016231). Each dataset was preprocessed with GGCAT (Cacco and Tomescu, 2023) to compute an SPSS, followed by KmerCamel (Sladký et al., 2023) to compute greedy masked superstrings for FMSI. Illumina raw-read datasets (*-ilm) were cleaned via *k*-mer filtering (*k* = 32, min-freq 2). Example summary of construction resources for **hg-t2t** and *k* = 31 are provided in **Tab. 3**. Benchmarks were performed on an AMD EPYC 7302 (3 GHz) server with 251 GB RAM and SSD storage. Comprehensive protocols and pre-processed datasets are provided in **Supplementary material**.

**FMSI consistently achieves best space efficiency.** We systematically evaluated the memory usage of FMSI, SBWT-small, SBWT-fast, SSHash, and CBL queries across dataset types (without subsampling) and various *k*-mer sizes (Tab. 4). FMSI consistently showed the lowest memory footprint. Specifically, it was by 1–2 orders of magnitude more space-efficient than CBL, over 2.5× more space-efficient than SSHash, and over 3× more space-efficient than SBWT-fast. The only method competitive in space with FMSI was SBWT-small, but only on large *k*-mer sets with dBG dominated by long paths (e.g., the human genome assembly **hg-t2t** and the *E.coli* pangenome without contamination filtering **ec-pg-all**, both only at large *k*). Since index serialization on disk enables additional compression and omits recomputable index parts and buffers, we also evaluated on-disk index sizes (smaller values in Tab. 4). The results were consistent, except for **sc2-pg**, where the SBWT-small serialized index was marginally smaller than FMSI's at large *k*.

<figure><img src="image_4.png" /><figcaption>**Fig. 2: Memory usage of indexes across *k*-mer lengths.** Memory usage is reported in bits per canonical *k*-mer, shown as a function of *k*. Corresponding on-disk sizes are indicated in lighter color. For **mtg-ilm**, evaluation is limited to *k* ≤ 32 due to initial *k*-mer filtering. The gray dashed line indicates two bits per *k*-mer.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>**Fig. 3: Time-memory trade-offs for membership queries for a) regular and b) subsampled *k*-mer sets (10%).** Query time (per *k*-mer) and memory usage are shown for selected datasets with *k* = 23, with and without streaming acceleration, and with and without reference set subsampling.</figcaption></figure>

**FMSI is robust to *k*.** We next examined how memory usage varied with *k* (Fig. 2). FMSI and SBWT-fast exhibited stable memory consumption per *k*-mer, remaining within a narrow range of the minimum observed value (except **rna-ilm**). SSHash' performance varied largely with *k*, with the best space requirements achieved for large values of *k*; otherwise, it required up to 2–4 times more space. SBWT-small remained space efficient at large *k*, but performance was degraded by a factor of 1.6–3.3 at smaller *k*. In contrast, CBL showed the opposite trend – beyond *k* > 23, its memory exceeded 40 bits per *k*-mer. We note SSHash and CBL performance may be further tuned via targeted (dataset, *k*)-specific optimization of the minimizer-size and prefix-bit parameters, respectively.
<figure><img src="image_6.png" /><figcaption>**Fig. 4: Disk usage of LCA indexes on MiniKraken database.**
Comparison of disk size for Kraken, FMSI, and SSHash indexes on subsampled MiniKraken v20171019 ($k = 31$). FMSI and SSHash include an additional two bytes per $k$-mer to associate each hash with the lowest common ancestor in the taxonomic tree.</figcaption></figure>

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

**FMSI maintains competitive query times.** Next, we evaluated whether FMSI maintains competitive query times compared to other methods (Fig. 3a). We selected $k = 23$ as a representative setting where all indexes achieve reasonable space usage and compared their positive and negative query times, with and without streaming acceleration. Overall, FMSI's query speed was in the mid-range relative to the other methods. SSHash and SBWT-fast were generally the fastest, outperforming FMSI by a factor of 2–4. At the same time, FMSI was usually 2–4× faster than the second best space-efficient tool, SBWT-small, although ties occurred, e.g., for E. coli pangenomic datasets with streaming support. FMSI's use of kLCP for accelerated streaming improved queries 2–4× (and similarly for SBWT), but at the cost of an additional bit per superstring character. In contrast, SSHash and CBL accelerate streaming without additional memory overhead. Importantly, the relative performance of methods under streaming remained consistent with that observed in isolated query mode. Interestingly, for **hg-t2t** with accelerated streaming, FMSI achieved comparable query times as SSHash, both being approximately 2× faster than SBWT-fast.

**Membership on subsampled $k$-mer sets.** Next, we sought to understand the effect of sampling on the query time and space of all indexes. We uniformly subsampled the $k$-mer sets to 10% on the previous $k$-mer sets (Fig. 3b). This resulted in a substantial increase in memory per $k$-mer of all tested tools, except for CBL on **hg-t2t**. The memory increase is primarily due to missing overlaps of length $k-1$ in the dataset, resulting in substantially larger representation lengths, when normalized by the $k$-mer set size. FMSI typically used at most half the space of the second best tool, SBWT-small, while also being 2× faster. FMSI was approximately 4× more space-efficient than SBWT-fast and SSHash, while being 2–3× slower on isolated queries. FMSI was particularly efficient on streamed queries, similarly fast as SSHash while using about 4× less space, achieved thanks to the “$k$-mer interpolation” nature of superstrings.

FMSI reduces the MiniKraken index size 2×. Finally, we sought to demonstrate the utility of FMSI as a dictionary of sampled $k$-mer sets, and evaluated its compressive properties on the subsampled database of the Kraken metagenomic classifier (Wood and Salzberg, 2014) termed the MiniKraken databases (Fig. 4). We built FMSI-dict and SSHash 31-mer dictionaries for both MiniKraken 31-mer databases available online (with an additional two bytes per $k$-mer for taxid arrays), and compared them to the size of the original indexes. We found that while SSHash moderately increased memory requirements compared to the Kraken index, FMSI provided more than a twofold memory improvement in both cases.

## Discussion and Conclusions

$k$-mer-based methods are central to modern bioinformatics, and efficient $k$-mer set indexing is therefore a critical objective. In this work, we introduced FMSI, a data structure and its implementation for space-efficient indexing of single $k$-mer sets. FMSI consistently achieved lower space usage than all other state-of-the-art methods across a broad operational range, while maintaining competitive query times. This was possible thanks to approximately shortest superstrings and BWT indexing – two techniques that had not previously been combined in this context.

Several performance tradeoffs in FMSI could be further improved. First, index construction currently depends on QSUF-Sort (Larsson and Sadakane, 2007), which limits its scalability, whereas modern BWT construction algorithms already scale to terabyte-sized inputs (Li, 2024). Second, query speed would benefit from parallelization, implemented similarly to BWT-based indexes (Li, 2012; Alanko et al., 2023). Third, space usage may be further reduced by applying Elias-Fano (Elias, 1974; Fano, 1971) to the SA-transformed mask instead of RRR (Raman et al., 2007). Finally, FMSI could be re-optimized for speed instead of space – for instance, by adding a reverse complement superstring to the index or replacing wavelet trees with 2-bit encoding, in analogy to the fast modes in SBWT.

Despite decades of work and a rich palette of available methods, $k$-mer indexing remains an exciting problem with substantial room for improvement. This is particularly relevant in settings with subsampling, sketching, or high levels of genetic polymorphisms and technological artifacts, such as metagenomics and pangenomics. In these cases, superstrings offer an elegant means to bypass the limitations of traditional methods, representing a major weapon in the algorithmic arsenal for future generic, space-efficient, and parameter-free $k$-mer-based data structures. Their potential impact may extend well beyond bioinformatics, into domains such as indexing in large language models.

**Author contributions statement.** O.S., P.V., K.B. developed the methodology, designed and conducted the experiments, analyzed the results, and wrote the manuscript. O.S. developed the software.

**Acknowledgments.** This work was supported by the French National Research Agency [ANR-24-CE45-1226; REALL]; Czech Science Foundation [22-22997S]; Czech Ministry of Education, Youth and Sports [ERC-CZ LL2406]; Charles University [UNCE 24/SCI/008]; French Ministry for Europe and Foreign Affairs, French Ministry for Higher Education and Research, and Czech Ministry for Education, Youth and Sports [PHC BARRANDE 2025 grant no. 52374TC; EFFIMAS]. Portions of this research were conducted at the GenOuest bioinformatics core facility (https://www.genouest.org). We are grateful to Camille Marchet, Igor Martayan, Giulio Pibiri, Jarno Alanko, and Paul Medvedev for their constructive comments.
References

Alanko, J. N., Puglisi, S. J., and Vuohtoniemi, J. (2023). Small searchable *κ*-spectra via subset rank queries on the spectral Burrows-Wheeler transform. In *ACDA '23*. SIAM.

Bingmann, T., Bradley, P., Gauger, F., and Iqbal, Z. (2019). COBS: a compact bit-sliced signature index. In *SPIRE'19*. Springer.

Blackwell, G. A., Hunt, M., Malone, K. M., Lima, L., Horesh, G., Alako, B. T. F., Thomson, N. R., and Iqbal, Z. (2021). Exploring bacterial diversity via a curated and searchable snapshot of archived dna sequences. *PLOS Biology*, 19(11).

Bowe, A., Onodera, T., Sadakane, K., and Shibuya, T. (2012). Succinct de Bruijn graphs. In *WABI '12*, LNCS. Springer.

Bradley, P., Den Bakker, H. C., Rocha, E. P., McVean, G., and Iqbal, Z. (2019). Ultrafast search of all deposited bacterial and viral genomic data. *Nature Biotechnology*, 37(2).

Bradley, P., Gordon, N. C., Walker, T. M., Dunn, L., Heys, S., Huang, B., Earle, S., Pankhurst, L. J., Anson, L., De Cesare, M., et al. (2015). Rapid antibiotic-resistance predictions from genome sequence data for Staphylococcus aureus and Mycobacterium tuberculosis. *Nature Communications*, 6(1).

Bray, N. L., Pimentel, H., Melsted, P., and Pachter, L. (2016). Near-optimal probabilistic RNA-seq quantification. *Nature Biotechnology*, 34(5).

Brinda, K., Baym, M., and Kucherov, G. (2021). Simplitigs as an efficient and scalable representation of de Bruijn graphs. *Genome Biology*, 22(96).

Brinda, K., Callendrello, A., Ma, K. C., MacFadden, D. R., Charalampous, T., Lee, R. S., Cowley, L., Wadsworth, C. B., Grad, Y. H., Kucherov, G., et al. (2020). Rapid inference of antibiotic resistance and susceptibility by genomic neighbour typing. *Nature Microbiology*, 5(3).

Brinda, K., Lima, L., Pignotti, S., Quinones-Olvera, N., Salikhov, K., Chikhi, R., Kucherov, G., Iqbal, Z., and Baym, M. (2025). Efficient and robust search of microbial genomes via phylogenetic compression. *Nature Methods*, (4):692-697.

Brinda, K., Salikhov, K., Pignotti, S., and Kucherov, G. (2017). Prophyle 0.3.1.0: An accurate, resource-frugal and deterministic DNA sequence classifier. https://doi.org/10.5281/zenodo.1045429.

Burrows, M. and Wheeler, D. (1994). A block-sorting lossless data compression algorithm. Technical Report 124, Digital Equipment Corporation.

Chikhi, R., Holub, J., and Medvedev, P. (2022). Data structures to represent a set of *k*-long DNA sequences. *ACM Computing Surveys*, 54(1).

Chikhi, R., Limasset, A., Jackman, S., Simpson, J. T., and Medvedev, P. (2015). On the representation of de Bruijn graphs. *Journal of Computational Biology*, 22(5).

Chikhi, R., Limasset, A., and Medvedev, P. (2016). Compacting de Bruijn graphs from sequencing data quickly and in low memory. *Bioinformatics*, 32(12).

Conway, T. C. and Bromage, A. J. (2011). Succinct data structures for assembling large genomes. *Bioinformatics*, 27(4).

Cracco, A. and Tomescu, A. I. (2023). Extremely fast construction and querying of compacted and colored de Bruijn graphs with ggcat. *Genome Research*.

Croucher, N. J., Finkelstein, J. A., Pelton, S. I., Parkhill, J., Bentley, S. D., Lipsitch, M., and Hanage, W. P. (2015). Population genomic datasets describing the post-vaccine evolutionary epidemiology of Streptococcus pneumoniae. *Scientific Data*, 2.

Elias, P. (1974). Efficient storage and retrieval by content and address of static files. *J. ACM*, 21(2).

Fano, R. M. (1971). On the number of bits required to implement an associative memory. MIT, Project MAC.

Feigenblat, G., Porat, E., and Shiftan, A. (2016). Linear time succinct indexable dictionary construction with applications. In *2016 Data Compression Conference (DCC)*, pages 13–22.

Gog, S., Beller, T., Moffat, A., and Petri, M. (2014). From theory to practice: Plug and play with succinct data structures. In *SEA '14*.

Grossi, R., Gupta, A., and Vitter, J. S. (2003). High-order entropy-compressed text indexes. In *SODA '03*. SIAM.

Grüning, B., Dale, R., Sjödin, A., Chapman, B. A., Rowe, J., Tomkins-Tinch, C. H., Valieris, R., Köster, J., and Team, B. (2018). Bioconda: sustainable and comprehensive software distribution for the life sciences. *Nature Methods*, 15(7).

Holley, G. and Melsted, P. (2020). Bifrost: highly parallel construction and indexing of colored and compacted de Bruijn graphs. *Genome Biology*, 21(1).

Karasikov, M., Mustafa, H., Danciu, D., Kulkov, O., Zimmermann, M., Barber, C., Rätsch, G., and Kahles, A. (2025). Efficient and accurate search in petabase-scale sequence repositories. *Nature*, pages 1–9.

Khan, J., Dhulipala, L., and Patro, R. (2025). Fast and scalable parallel external-memory construction of colored compacted de Bruijn graphs with Cuttlefish 3. *bioRxiv*.

Khan, J., Kokot, M., Deorowicz, S., and Patro, R. (2022). Scalable, ultra-fast, and low-memory construction of compacted de Bruijn graphs with Cuttlefish 2. *Genome Biology*, 23(1).

Khan, J. and Patro, R. (2021). Cuttlefish: fast, parallel and low-memory compaction of de Bruijn graphs from large-scale genome collections. *Bioinformatics*, 37(Supplement_1):i177–i186.

Larsson, N. J. and Sadakane, K. (2007). Faster suffix sorting. *Theoretical Computer Science*, 387(3).

Li, H. (2012). Exploring single-sample SNP and INDEL calling with whole-genome de novo assembly. *Bioinformatics*, 28(14).

Li, H. (2024). BWT construction and search at the terabase scale. *Bioinformatics*, 40(12).

Loh, P.-R., Baym, M., and Berger, B. (2012). Compressive genomics. *Nature Biotechnology*, 30(7).

Marchet, C., Boucher, C., Puglisi, S. J., Medvedev, P., Salson, M., and Chikhi, R. (2021a). Data structures based on k-mers for querying large collections of sequencing data sets. *Genome Research*, 31(1).

Marchet, C., Kerbiriou, M., and Limasset, A. (2021b). Blight: efficient exact associative structure for k-mers. *Bioinformatics*, 37(18).

Martayan, I., Cazaux, B., Limasset, A., and Marchet, C. (2024). Conway–Bromage–Lyndon (CBL): an exact, dynamic representation of k-mer sets. *Bioinformatics*, 40:i48–i57.

Minkin, I., Pham, S., and Medvedev, P. (2016). Twopaco: an efficient algorithm to build the compacted de Bruijn graph from many complete genomes. *Bioinformatics*, 33(24):4024–4032.

Nurk, S., Koren, S., Rhie, A., Rautiainen, M., Bzikadze, A. V., Mikheenko, A., Vollger, M. R., Altemose, N., Uralsky, L., Gershman, A., et al. (2022). The complete sequence of a human genome. *Science*, 376(6588).

Ondov, B. D., Treangen, T. J., Melsted, P., Mallonee, A. B., Bergman, N. H., Koren, S., and Phillippy, A. M. (2016). Mash: fast genome and metagenome distance estimation using minhash. *Genome Biology*, 17(1).

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58
1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

Patro, R., Duggal, G., Love, M. I., Irizarry, R. A., and Kingsford, C. (2017). Salmon provides fast and bias-aware quantification of transcript expression. *Nature Methods*, 14(4).

Pibiri, G. E. (2022). Sparse and skew hashing of K-mers. *Bioinformatics*, 38(Supplement_1).

Rahman, A. and Medvedev, P. (2021). Representation of k-mer sets using spectrum-preserving string sets. *Journal of Computational Biology*, 28(4).

Raman, R., Raman, V., and Satti, S. R. (2007). Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. *ACM Trans. Algorithms*, 3(4).

Salikhov, K. (2017). Efficient algorithms and data structures for indexing DNA sequence data. PhD thesis, Université Paris-Est, France.

Salikhov, K., Břinda, K., Pignotti, S., and Kucherov, G. (2018). Prophex 0.1.1. https://doi.org/10.5281/zenodo.1247431.

Schmidt, S. and Alanko, J. N. (2023). Eulertigs: minimum plain text representation of k-mer sets without repetitions in linear time. *Algorithms for Molecular Biology*, 18(1).

Schmidt, S., Khan, S., Alanko, J. N., Pibiri, G. E., and Tomescu, A. I. (2023). Matchtigs: minimum plain text representation of

k-mer sets. *Genome Biology*, 24(1).

Shu, Y. and McCauley, J. (2017). GISAID: global initiative on sharing all influenza data-from vision to reality. *Eurosurveillance*, 22(13).

Simpson, J. T., Wong, K., Jackman, S. D., Schein, J. E., Jones, S. J., and Birol, I. (2009). ABySS: a parallel assembler for short read sequence data. *Genome Research*, 19(6).

Sladký, O., Veselý, P., and Břinda, K. (2023). Masked superstrings as a unified framework for textual k-mer set representations. *bioRxiv*, 2023.02.01.526717.

Sladký, O., Veselý, P., and Břinda, K. (2025). Towards efficient k-mer set operations via function-assigned masked superstrings. In *Proceedings of the Prague Stringology Conference 2025*, pages 26-40. Czech Technical University in Prague.

Stephens, Z. D., Lee, S. Y., Faghri, F., Campbell, R. H., Zhai, C., Efron, M. J., Iyer, R., Schatz, M. C., Sinha, S., and Robinson, G. E. (2015). Big data: Astronomical or genomical? *PLoS Biology*, 13(7).

Wood, D. E. and Salzberg, S. L. (2014). Kraken: ultrafast metagenomic sequence classification using exact alignments. *Genome Biology*, 15(3).