Extracting and Updating Compact Colored k-mer Indexes
- 1University of Lille
Abstract
Colored k-mer indexes record, for every k-mer of a collection of genomes, the genomes or species that contain it, and underpin pseudoalignment and sequence search against large collections. Construction of such an index is expensive, yet the collection it represents is rarely final: genomes are retracted or found to be contaminated, users need an index of a single species or clade, and new genomes keep arriving. Rebuilding the index after every such change requires the original sequences and repeats the costly construction. We show that colored indexes based on the spectral Burrows-Wheeler transform (SBWT) can instead be updated efficiently in batches, without the original sequences, and with a result equivalent to the index built from scratch. Given an SBWT and any subset of its k-mers, we first extract the SBWT of this subset directly from the input, in one linear pass and without building a new index. Removing genomes, intersection and difference all reduce to this operation. We then carry the colors through every operation, by finding from the inputs alone where the color sets of the result change, so that removing or extracting genomes, as well as the union, intersection and difference of two colored indexes, each directly yield a complete colored index. In our experiments, editing paid off for large results: removing a genome from an index of 3,682 E. coli genomes took 54 seconds instead of 13 minutes for a rebuild, and adding one took about a minute. On AllTheBacteria, with 192 billion k-mers and 12,733 species, extracting M. tuberculosis, with 180,094 genomes, took less than four hours, and set operations then traced contamination of its color, some of which the next release of AllTheBacteria still contains. Our work turns large colored k-mer indexes from static snapshots of a collection into resources that can be maintained as the collection evolves. Our implementation is available at https://github.com/LoreDepuydt/colored-sbwt-setops.
Related
- Toward space-optimal approximate colored indexes at scale
- HIPPOCAMPAL TAU RELATED SIGNAL INDEXES HYPEREXCITABILITY AND NREM SLEEP MEMORY DYSFUNCTION IN TEMPORAL LOBE EPILEPSY
- Parent-Child Cortical Similarity Indexes Multiple Dimensions of Sensitivity in the Association Between Family Environment and Adolescent Internalizing Symptoms
- Beta bursts carry a graded signal of semantic updating during naturalistic narrative comprehension
- Movement refinement and cholinergic regulation of outcome-dependent updating during skilled reaching.
BibTeX
@misc{depuydt2026extracting,
title = {{Extracting and Updating Compact Colored k-mer Indexes}},
author = {L. Depuydt and J. N. Alanko and C. Marchet and S. J. Puglisi},
howpublished = {bioRxiv},
year = {2026},
month = nov,
doi = {10.64898/2026.11.06.764792},
url = {https://www.biorxiv.org/content/10.64898/2026.11.06.764792v1},
note = {CC BY-NC},
}
RIS
TY - UNPB
TI - Extracting and Updating Compact Colored k-mer Indexes
AU - L. Depuydt
AU - J. N. Alanko
AU - C. Marchet
AU - S. J. Puglisi
PY - 2026
DA - 2026/11/06
PB - bioRxiv
DO - 10.64898/2026.11.06.764792
UR - https://www.biorxiv.org/content/10.64898/2026.11.06.764792v1
AB - Colored k-mer indexes record, for every k-mer of a collection of genomes, the genomes or species that contain it, and underpin pseudoalignment and sequence search against large collections. Construction of such an index is expensive, yet the collection it represents is rarely final: genomes are retracted or found to be contaminated, users need an index of a single species or clade, and new genomes keep arriving. Rebuilding the index after every such change requires the original sequences and repeats the costly construction. We show that colored indexes based on the spectral Burrows-Wheeler transform (SBWT) can instead be updated efficiently in batches, without the original sequences, and with a result equivalent to the index built from scratch. Given an SBWT and any subset of its k-mers, we first extract the SBWT of this subset directly from the input, in one linear pass and without building a new index. Removing genomes, intersection and difference all reduce to this operation. We then carry the colors through every operation, by finding from the inputs alone where the color sets of the result change, so that removing or extracting genomes, as well as the union, intersection and difference of two colored indexes, each directly yield a complete colored index. In our experiments, editing paid off for large results: removing a genome from an index of 3,682 E. coli genomes took 54 seconds instead of 13 minutes for a rebuild, and adding one took about a minute. On AllTheBacteria, with 192 billion k-mers and 12,733 species, extracting M. tuberculosis, with 180,094 genomes, took less than four hours, and set operations then traced contamination of its color, some of which the next release of AllTheBacteria still contains. Our work turns large colored k-mer indexes from static snapshots of a collection into resources that can be maintained as the collection evolves. Our implementation is available at https://github.com/LoreDepuydt/colored-sbwt-setops.
ER -