FroM Superstring to Indexing: a space-efficient index for unconstrained k -mer sets using the Masked Burrows-Wheeler Transform (MBWT)
Bioinformatics Advances · 02.01.2026 · 6 (1)
DOI: 10.1093/bioadv/vbaf290 ↗Kurz gefasst
Fachartikel in der Zeitschrift Bioinformatics Advances, online erschienen am 12.11.2025. Verfasst von Ondřej Sladký und 2 weiteren Autor:innen. Beteiligte Einrichtung: ETH Zurich, 8092 Zurich, Switzerland. Die Arbeit wurde bisher 7-mal zitiert (Crossref) und nennt 53 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: French National Research Agency, Czech Science Foundation.
Abstract (Originalsprache)
Motivation 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. Results 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. Availability and implementation FMSI is developed in C++ and released under the MIT license, with source code provided at https://github.com/OndrejSladky/fmsi and an installable package available through Bioconda. The datasets used in the experiments are deposited at Zenodo (https://doi.org/10.5281/zenodo.14722244).
Autor:innen und Institutionen
- ETH Zurich, 8092 Zurich, Switzerland.
- Computer Science Institute of Charles University, 118 00 Prague, Czechia.
- INRIA, IRISA, Univ. Rennes, 35042 Rennes, France.
ORCID-Profile: Ondřej Sladký, Pavel Veselý, Karel Břinda
Förderung
- French National Research Agency
- Czech Science Foundation
Zitieren
APA
Sladký, O., Veselý, P., & Břinda, K. (2026). FroM Superstring to Indexing: a space-efficient index for unconstrained k -mer sets using the Masked Burrows-Wheeler Transform (MBWT). Bioinformatics Advances, 6(1). https://doi.org/10.1093/bioadv/vbaf290
Vancouver
Sladký O, Veselý P, Břinda K. FroM Superstring to Indexing: a space-efficient index for unconstrained k -mer sets using the Masked Burrows-Wheeler Transform (MBWT). Bioinformatics Advances. 2026;6(1). doi:10.1093/bioadv/vbaf290
BibTeX
@article{Sladk2026,
author = {Sladký, Ondřej and Veselý, Pavel and Břinda, Karel},
title = {FroM Superstring to Indexing: a space-efficient index for unconstrained k -mer sets using the Masked Burrows-Wheeler Transform (MBWT)},
journal = {Bioinformatics Advances},
year = {2026},
volume = {6},
number = {1},
doi = {10.1093/bioadv/vbaf290}
}
EUVIMED