Biology subjects

Depuydt, L.

Publications and source records attributed to Depuydt, L..

5 recordsLinked to original sources

bioRxiv2026

Extracting and Updating Compact Colored k-mer Indexes

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.

bioinformatics↗

bioRxiv2026

Fast Set Operations for Compact k-mer Sets

The k-mer spectrum of a set of sequences is the set of k-length substrings the sequences contain. This lossy representation of sequence content pervades modern genomics. Recently, the spectral Burrows-Wheeler transform (SBWT) has emerged as a space-efficient representation of k-spectra that also supports efficient k-mer lookup queries and, more generally, easy navigation of the de Bruijn graph of the k-spectrum. In this paper, we examine primitive set operations, such as intersection, union, and set difference, on SBWT-encoded k-spectra and show that these operations can be supported efficiently. Moreover, efficient merging leads directly to a new memory-efficient algorithm for SBWT construction, which was able to build the SBWT for the 661K bacterial dataset containing 88 billion distinct k-mers in 50 hours using 186 GiB of RAM and 112 GiB of disk space. Given the pervasiveness of k-mer sets in genomics and the continued rapid growth of genomic databases, our work opens the door to a wide array of future applications that manipulate and reason about genomic data by dealing directly with simultaneously compact and searchable k-mer set representations offered by the SBWT. 2012 ACM Subject ClassificationTheory of computation [->] Design and analysis of algorithms Digital Object Identifier10.4230/LIPIcs.WABI.2026. Supplementary MaterialSoftware (Source Code): https://github.com/LoreDepuydt/sbwt-set-operations FundingThis work has benefited from funding from the French State under the France 2030 program, reference ANR-21-IDES-0006. The European Metropolis of Lille and the University of Lille are also acknowledged for their funding and support of the project WILL-CHAIRES-25-001-BOSSA.

bioinformatics↗

bioRxiv2025

Columba: Fast Approximate Pattern Matching withOptimized Search Schemes

Aligning sequencing reads to reference genomes is a fundamental task in bioinformatics. Aligners can be classified as lossy or lossless: lossy aligners prioritize speed by reporting only one or a few high-scoring alignments, whereas lossless aligners output all optimal alignments, ensuring completeness and sensitivity. This paper introduces Columba, a high-performance lossless aligner tailored for Illumina sequencing data. Columba processes single or paired-end reads in FASTQ format and outputs alignments in SAM format. By utilizing advanced search schemes and bit-parallel alignment techniques, Columba achieves exceptional speed. Columba is available in two variants. The first is based on the bidirectional FM-index. The second, Columba RLC, employs run-length compression using a bidirectional move structure, significantly reducing memory usage for large, repetitive datasets like pan-genomes. Through extensive benchmarking, Columba outperforms existing lossless aligners in speed, particularly at higher error rates. Tests on the human genome and bacterial and human pan-genome datasets demonstrate Columbas robustness and efficiency. We integrated Columba into the OptiType HLA genotyping pipeline, where it substantially reduced computational time while maintaining accuracy. These results position Columba as a versatile, state-of-the-art tool for high-sensitivity genomic analyses.

bioinformatics↗

bioRxiv2025

Run-length compressed metagenomic read classification with SMEM-finding and tagging

Metagenomic read classification is a fundamental task in computational biology, yet it remains challenging due to the scale, diversity, and complexity of sequencing datasets. We propose a novel, run-length compressed index based on the move structure that enables efficient multi-class metagenomic classification in O(r) space, where r is the number of character runs in the BWT of the reference text. Our method identifies all super-maximal exact matches (SMEMs) of length at least L between a read and the reference dataset and associates each SMEM with one class identifier using a sampled tag array. A consensus algorithm then compacts these SMEMs with their class identifier into a single classification per read. We are the first to perform run-length compressed read classification based on full SMEMs instead of semi-SMEMs. We evaluate our approach on both long and short reads in two conceptually distinct datasets: a large bacterial pan-genome with few metagenomic classes and a smaller 16S rRNA gene database spanning thousands of genera or classes. Our method consistently outperforms SPUMONI 2 in accuracy and runtime while maintaining the same asymptotic memory complexity of O(r). Compared to Cliffy, we demonstrate better memory efficiency while achieving superior accuracy on the simpler dataset and comparable performance on the more complex one. Overall, our implementation carefully balances accuracy, runtime, and memory usage, offering a versatile solution for metagenomic classification across diverse datasets. The open-source C++11 implementation is available at https://github.com/biointec/tagger under the AGPL-3.0 license.

bioinformatics↗

bioRxiv2024

b-move: faster bidirectional character extensions in a run-length compressed index

Due to the increasing availability of high-quality genome sequences, pan-genomes are gradually replacing single consensus reference genomes in many bioinformatics pipelines to better capture genetic diversity. Traditional bioinformatics tools using the FM-index face memory limitations with such large genome collections. Recent advancements in run-length compressed indices like Gagie et al.s r-index and Nishimoto and Tabeis move structure, alleviate memory constraints but focus primarily on backward search for MEM-finding. Arakawa et al.s br-index initiates complete approximate pattern matching using bidirectional search in run-length compressed space, but with significant computational overhead due to complex memory access patterns. We introduce b-move, a novel bidirectional extension of the move structure, enabling fast, cache-efficient bidirectional character extensions in run-length compressed space. It achieves bidirectional character extensions up to 8 times faster than the br-index, closing the performance gap with FM-index-based alternatives, while maintaining the br-indexs favorable memory characteristics. For example, all available complete E. coli genomes on NCBIs RefSeq collection can be compiled into a b-move index that fits into the RAM of a typical laptop. Thus, b-move proves practical and scalable for pan-genome indexing and querying. We provide a C++ implementation of b-move, supporting efficient lossless approximate pattern matching including locate functionality, available at https://github.com/biointec/b-move under the AGPL-3.0 license. FundingLore Depuydt: PhD Fellowship FR (1117322N), Research Foundation - Flanders (FWO) Luca Renders: PhD Fellowship SB (1SE7822N), Research Foundation - Flanders (FWO) Travis Gagie: NSERC Discovery Grant RGPIN-07185-2020 to Travis Gagie and NIH grant R01HG011392 to Ben Langmead

bioinformatics↗