# Masked Superstrings as a compact, indexable, and dynamic representation of unconstrained k-mer sets

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

► To cite this version:

Ondřej Sladký, Pavel Veselý, Karel Břinda. Masked Superstrings as a compact, indexable, and dynamic representation of unconstrained k-mer sets. RECOMB 2025 - 29th International Conference of Research in Computational Molecular Biology, Apr 2025, Seoul, Korea, South Korea. pp.1-1, 2025. hal-05044964

HAL Id: hal-05044964

https://hal.science/hal-05044964v1

Submitted on 24 Apr 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
# MASKED SUPERSTRINGS
AS A COMPACT, INDEXABLE, AND DYNAMIC REPRESENTATION OF UNCONSTRAINED *k*-MER SETS

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

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

¹Charles University, Prague, Czech Republic,

²ETH Zurüch, Switzerland

³Inria, Rennes, France

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

## k-mer sets

### Core of alignment-free methods

E.g.: Large-scale data search [Bradley&al, Nat. Biotechnol.'19] Metagenomic classification [Wood&Salzberg, Genome Biol.'14] Infectious disease diagnostics [Břinda&al, Nat. Microbiol.'20] Transcript abundance quantification [Bray&al, Nat. Biotechnol.'16], [Patro&al, Nat. Methods'17]

### Characteristics of k-mer sets

* Often satisfy **Spectrum-Like Property** (SLP) = generated by rel. few long strings
  ⇒ efficient representations based on paths in the de Bruijn graph:

* unitigs, simplitigs/Spectrum Preserving String Sets (SPSS) [Rahman&Medvedev'21], [Břinda&al, Nat. Microbiol.'20] Transcript abundance quantification [Bray&al, Nat. Biotechnol.'16], [Patro&al, Nat. Methods'17]

* Limitation: (r)SPSS only work well if there are many overlaps of len. *k* − 1

### Main challenges

**Compaction:** highly compressed storage format for *k*-mers

**Data structures:** efficient membership index / compressed dictionary
+ support for **dynamicity** / **set operations**

**Non-traditional k-mer sets:** subsampling or sketching breaks Spectrum-Like Property!

## Concept of masked superstrings

* *S* = **superstring** of *k*-mers *K* — based on the **overlap graph** ⇒ exploiting overlaps of all lengths

* *M* = binary **mask** to determine “false positive” *k*-mers — **highly compressible**

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

### Masked superstring workflow

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

### Computation of masked superstrings: KmerCamel

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

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

at GitHub:

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

1. **Approximate superstring:** greedy using hash tables – **new speedups**

* For genomic data: up to < 1% to the actual shortest superstrings

* New: **fast computation from simplitigs!** 11 min. on human genome (T2T, *k* = 31)

2. **Optimize the mask** (optional): e.g., **minimize/maximize** #1's (1/2-pass alg.)

## Improved compressibility of *k*-mer sets

<figure><img src="image_9.png" /><figcaption>Example: human genome, *k*=31 (2.51G distinct canonical 31-mers)</figcaption></figure>

ms-geco – an optimized protocol combining: 1) approximated shortest masked superstrings + 2) bzip2 for the mask + 3) GeCo3 for the superstring [Silva & al, GigaScience, 2020]

**Masked superstring paper:**
MS concept + computation +

*k*-mer set compression,
*new version in preparation*

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

**FMSI paper on indexing:**
MBWT + membership index +
compressed dictionary

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

**f-MS paper on set operations:**
function-assigned MS + algebraic
framework for set operations with FMSI,
limitation: merging FMSI indexes not
efficient yet

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

## Memory-efficient indexing of single *k*-mer sets

**FMSI** (“FroM Superstring to Indexing”) *k*-mer **membership index and compressed dictionary**:

* Burrows-Wheeler Transform (BWT) of superstring *S* → *S'* + rank (and select for dictionary)

* Mask *M* transformed to suffix array coordinates. for fast queries → *M'* (+ rank and select for dict.)
  -∀*i*: *M'*[*i*] = *M*[*j*] where *j* is the starting position of the *i*-th smallest suffix of *S*

### Masked Burrows-Wheeler Transform (MBWT)

**Main idea:** attach mask symbols to superstring symbols & compute BWT of *S*
**Index construction**

0. **Read** the input *k*-mer set

$$K := \{CAG, GGT, GTA, TAG\}$$

1. **Approximate** shortest superstring

2. **Optimize** *k*-mer mask < membership: max 1's dictionary: min 1's

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

3. **Compute** Masked BWT (MBWT)

$$ (S') := \text{MBWT}(S) = \left( \begin{array}{c} \text{GTC\$AAGG} \\ \$0010111 \end{array} \right) $$

4. **Build** rank/select data structures:

< membership: rank for $S'$
dictionary: rank and select for $S'$ and $M'$

**Queries:** BWT-style backward search → SA-coordinates interval (*i*, *j*)

* **Membership:** return *i* < *j* & *M'*[*i*] = 1

* **Dictionary:** two rank queries on *M'* → yields *Minimum Perfect Hash Function* with fast evaluation, rejections, and inversion!

Simple & currently the most
**memory-efficient** data struc-
ture for single *k*-mer sets!

FMSI at GitHub:

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

### Results on query memory & time

Query memory (*disk*) requirements in bits per canonical *k*-mer; best values in bold:

<table><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.7</td><td>3.2-5.0</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>24.5-41.4</td><td>3.6-5.1</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.7-22.7</td><td>6.6-22.6</td><td>3.4-7.8</td><td>3.1-6.6</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>3.1-7.8</td><td>2.9-7.1</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>3.7-7.3</td><td>3.1-6.1</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>4.8-7.8</td><td>4.4-6.7</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>3.5-8.5</td><td>3.4-7.8</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>2.4-8.0</td><td>2.3-7.3</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>2.4-50.7</td><td>2.3-7.8</td></tr></tbody></table>

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

memory [bits / k-mer], all datasets for *k*=23

Sampled *k*-mer dictionary
* indexes:
MiniKraken DBs of
31-mers from Kraken
[Wood&Salzberg, Genome
Biol.'14]

FMSI and SSHash incl. +2B/*k*-mer
for the *k*-mers' LCA in the taxo-
nomic tree

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

FMSI compared to:

* SBWT = Spectral Burrows-Wheeler Transform
[Alanko&Puglisi&Vuohtoniemi, ACDA'23]

* SSHash on eulertigs (= optimal simplitigs) [Pibiri, Bioinformatics'22]

* CBL = Conway-Bromage-Lyndon
[Martayan&al., Bioinformatics'24]

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

Datasets at Zenodo:

* sc2-pg = SARS-CoV-2 pan-genome, from GISAID, *n* = 14M

* sp-pg = S. pneumoniae pan-genome, RASE DB, *n* = 616

* ec-pg-{*hq,all*} = E.coli pan-genome from 661k collection, with/without high-quality filtering

* mtg-ilm = metagenomic sample SRS063932 (Illumina raw reads) of human microbiome, min. freq 2

* rna-ilm = human RNA-seq Illumina raw reads, SRX348811, min. freq 2

* hg-ilm = human genome Illumina raw reads, SRX016231, min. freq 2

* hg-t2t = human genome assembly
chm13v2.0 (T2T)

## Set operations with masked superstrings

**f-MS:** Function-Assigned Masked Superstrings:

* Key idea: equip masked superstring with demasking function *f*

a) f-MS: $\mathbf{M} = \begin{array}{c} \mathbf{10110111011011011000} \\ \mathbf{\text{ACCG}} \end{array}$ query $\mathbf{\Lambda} = \begin{array}{c} \mathbf{10110111011011011000} \\ \mathbf{\text{ACCG}} \end{array}$ ($1,0,1$) $f$ invalid $\begin{array}{c} \text{if } f \text{ is or} \\ \text{if } f \text{ is xor} \\ \text{if } f \text{ is oon or aon} \end{array}$ f-MS

b) CONCAT: $\mathbf{2 \times f'-MS}$ $\mathbf{f'-MS}$ $\mathbf{f'-MS}$ $\mathbf{f'-MS}$ $\mathbf{f'-MS}$ $\mathbf{f'-MS}$ $\mathbf{f'-MS}$ $\mathbf{f'-MS}$ $\mathbf{f'-MS}$ $\mathbf{f'-MS}$ $\mathbf{f'-MS}$ $\mathbf{f'-MS}$ $\mathbf{f'-MS}$ $\mathbf{f'-MS}$ $\mathbf{f'-MS}$ $\mathbf{f'-MS}$

c) $2 \times \text{operational f-MS}$ $\mathbf{f'-RECAST}$ $\mathbf{f'-MS}$ $\mathbf{CONCAT}$ $\mathbf{f'-RECAST}$ $\mathbf{f'-RECAST}$ $\mathbf{f'-RECAST}$ $\mathbf{f'-COMPACT}$ $\mathbf{1 \times \text{operational f-MS}}$ $\mathbf{or}$