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

{"sci_version": "1.2", "schema": "https://corpus.bntrg.co.uk/sci/1.0/sci.schema.json", "id": "pmid:41542367", "kind": "science-record", "revision": 1, "content_hash": "sha256:5e4a88b538e4fc71ccba1a8373dbb5f6bf5dd5c914c98118412dcafcec19f29e", "created_at": "2026-11-01T20:31:30Z", "updated_at": "2026-11-01T20:31:30Z", "generator": {"name": "corpus-assay-engine", "run_id": "reading-sci-2026-11-01"}, "paper": {"state": "complete", "title": "FroM Superstring to Indexing: a space-efficient index for unconstrained k-mer sets using the Masked Burrows-Wheeler Transform (MBWT).", "doi": "10.1093/bioadv/vbaf290", "pmid": "41542367", "authors": ["Ondřej Sladký", "Pavel Veselý", "Karel Břinda"], "journal": "Bioinformatics advances", "year": 2026, "abstract": "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.\nResults: 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.\nAvailability 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).", "claims": [{"id": "claim-data-access", "statement": "The datasets used in the experiments are deposited at Zenodo (https://doi.org/10.5281/zenodo.14722244).", "kind": "methodological", "target": null, "evidence": [{"asset": "source:pmid:41542367", "locator": "sections[0] \"Abstract\" paragraph 3", "quote": "The datasets used in the experiments are deposited at Zenodo (https://doi.org/10.5281/zenodo.14722244)."}], "state": "complete"}, {"id": "claim-target-result", "statement": "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.", "kind": "qualitative", "target": null, "evidence": [{"asset": "source:pmid:41542367", "locator": "sections[0] \"Abstract\" paragraph 2", "quote": "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."}], "state": "complete"}], "gaps": []}, "experiment": {"state": "partial", "objective": "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.", "steps": [{"id": "read_published_estimate", "order": 1, "name": "Read the published estimate from the source", "kind": "other", "state": "complete", "blocked_on": null, "description": "The claim, method and evidence span published with the source article.", "duration_hours": null, "parameters": {}, "inputs": ["source:pmid:41542367"], "outputs": ["the published estimate and its evidence"], "instruments": [], "reagents": []}, {"id": "obtain_source_data", "order": 2, "name": "Obtain the source data from the named repository", "kind": "data-preparation", "state": "blocked", "blocked_on": "data:accession_absent", "description": "The GEO series accession resolves and its sample accessions are listed. This lane did not download the dataset or read its licence.", "duration_hours": null, "parameters": {}, "inputs": [], "outputs": ["the source data with its repository provenance"], "instruments": [], "reagents": []}, {"id": "run_analysis", "order": 3, "name": "Run the published analysis", "kind": "analysis", "state": "complete", "blocked_on": null, "description": "Apply the paper's statistical method to the resolved series and compare the result with the published target.", "duration_hours": null, "parameters": {}, "inputs": [], "outputs": ["the replicated result and its comparison"], "instruments": [], "reagents": []}], "materials": [], "instruments": [], "reagents": [], "conditions": {}, "gaps": ["step:obtain_source_data blocked on data:accession_absent"]}, "data": {"state": "partial", "assets": [{"id": "source:pmid:41542367", "role": "manuscript", "format": "xml", "media_type": "application/xml", "uri": "https://doi.org/10.1093/bioadv/vbaf290", "sha256": "sha256:e519e7c4a6baf75e0ecaf2a0e459185896105313d526959a0051076bbeeb2b5c", "bytes": 41262, "access": "open", "state": "resolved", "reader": null, "reader_status": "reader_required", "identifier": "10.1093/bioadv/vbaf290", "version": null, "note": "Full article fetched from PMC; the checksum covers the rendered section body, not the original XML bytes.", "structure": {"pmcid": "PMC12800775", "source": "europe_pmc_fulltext", "coverage": "whole_body_without_references", "text_hash_scope": "rendered_section_body"}}], "gaps": []}, "analysis": {"state": "absent", "methods": [], "targets": [], "gaps": ["method", "operations"]}, "capability": {"state": "complete", "requirements": [{"capability_id": "capability:computational_analysis", "label": "Computational analysis platform", "assay_families": ["meta_analysis", "machine_learning", "survival_analysis", "statistical_regression", "pca", "molecular_docking", "network_analysis", "differential_expression", "gwas"], "availability_state": "owned", "tier_unlocked": "R1", "candidate": "Automated Assays Laravel application and simulated adapters"}], "gaps": []}, "readiness": {"state": "blocked", "tier": "R4", "blocking_axis": "data", "blocked_on": "data:accession_absent", "axes": {"method": {"tier": "R4", "expressible": false, "required_operations": [], "missing_operations": [], "basis": "The reader quoted the method the paper names (not named), but the corpus's method extractor could not map it onto a DSL operation, so the method is published but not expressible."}, "capability": {"tier": "R1", "capability_id": "capability:computational_analysis", "availability_state": "owned", "basis": "The computational analysis is owned. The physical bench the paper used is not, so a physical validation cannot be run here."}, "data": {"tier": "R4", "reachable": false, "accessions": [], "resolved_accessions": [], "statements": ["The datasets used in the experiments are deposited at Zenodo (https://doi.org/10.5281/zenodo.14722244)."], "basis": "The paper names no accession to its source data, so the data has to come from the authors."}}, "can_run": {"dsl_operations": [], "assets": ["source:pmid:41542367"], "steps": ["run_analysis"]}, "must_build": {"dsl_operations": [], "converters": [], "readers": [], "capabilities": [], "data_gaps": ["data:geo:None"]}, "gaps": ["data:accession_absent"]}, "review": {"state": "partial", "machine_critique": {"kind": "extraction_review", "reader": {"model": "MiniMax-M3.1-Flash", "provider": "minimax", "provider_family": "minimax", "read_at": "2026-11-01T20:10:19Z", "independence": "single_reader"}, "evidence_check": {"method": null, "availability": "verbatim"}, "calls": 5, "usage": {"prompt_tokens": 11772, "completion_tokens": 1479, "cached_tokens": 128}}, "human_critique": null, "stages": [{"id": "extraction", "state": "complete", "reader": "MiniMax-M3.1-Flash", "provider": "minimax"}], "gaps": ["review.independent_reader", "review.machine_critique", "review.human_critique"]}, "execution": {"state": "absent", "status": "not_run", "mode": null, "runs": [], "gaps": ["execution.not_run"]}, "provenance": {"entities": [{"id": "pmid:41542367", "type": "paper", "label": "pmid:41542367"}, {"id": "source:pmid:41542367", "type": "manuscript", "label": "PMID 41542367 full text"}, {"id": "data:geo:None", "type": "dataset", "label": "GEO None"}], "activities": [{"id": "activity-reading-sci-2026-11-01", "type": "classification", "used": [{"id": "pmid:41542367", "type": "paper", "label": "pmid:41542367"}, {"id": "source:pmid:41542367", "type": "manuscript", "label": "PMID 41542367 full text"}, {"id": "data:geo:None", "type": "dataset", "label": "GEO None"}], "agent": "agent:corpus-assay-engine"}, {"id": "activity-read-41542367", "type": "extraction", "used": ["source:pmid:41542367"], "agent": "agent:minimax-reader"}, {"id": "activity-resolve-None", "type": "accession_resolution", "used": ["data:geo:None"], "agent": "agent:corpus-assay-engine"}], "agents": [{"id": "agent:corpus-assay-engine", "type": "software", "label": "Corpus assay engine"}, {"id": "agent:minimax-reader", "type": "software", "label": "MiniMax literature reader"}], "source_run_id": "reading-sci-2026-11-01", "dsl_catalogue_fingerprint": "343fb30756ba6ec3", "capability_table_fingerprint": "2cb3e42f047d2ecf", "snapshot_id": "ba34b49490d9bfaf"}, "lineage": {"parent_id": null, "parent_hash": null, "fork_of": null, "generation": 0}, "gaps": ["execution.not_run", "method", "operations", "review.human_critique", "review.independent_reader", "review.machine_critique", "step:obtain_source_data blocked on data:accession_absent"], "assays": [{"role": "data_generation", "definition_id": "rna_seq", "definition_version": "99e1195c7d6f", "definition_digest": null, "required_operations": [], "support_state": "partial", "source_hashes": {"assay_lexicon": "99e1195c7d6f"}, "confidence": 0.93, "evidence": ["uman tongue microbiome (mtg-ilm; SRX023459), RNA-seq Illumina reads (rna-ilm; SRX348811), human T"], "order_basis": "paper_text_order:3152", "id": "assay:1"}]}