Biology subjects

Rouze, T.

Publications and source records attributed to Rouze, T..

3 recordsLinked to original sources

bioRxiv2026

Super Bloom: Fast and precise filter for streaming k-mer queries

Approximate membership query structures are used throughout sequence bioinformatics, from read screening and metagenomic classification to assembly, indexing, and error correction. Among them, Bloom filters remain the default choice. They are not the most efficient structures in either time or memory, but they provide an effective compromise between compactness, speed, simplicity, and dynamic insertions, which explains their widespread adoption in practice. Their main drawback is poor cache locality, since each query typically requires several random memory accesses. Blocked Bloom filters alleviate this issue by restricting accesses for any given element to a single memory block, but this usually comes with a loss in accuracy at fixed memory. In this work, we introduce the Super Bloom Filter, a Bloom filter variant designed for streaming k-mer queries on biological sequences. Super Bloom uses minimizers to group adjacent k-mers into super-k-mers and assigns all k-mers of a group to the same memory block, thereby amortizing random accesses over consecutive k-mer queries and improving cache efficiency. We further combine this layout with the findere scheme, which reduces false positives by requiring consistent evidence across overlapping subwords. We provide a theoretical analysis of the construction of Super Bloom filters, showing how minimizer density controls the expected reduction in memory transfers, and derive a practical parameterization strategy linking memory budget, block size, collision overhead, and the number of hash functions to robust false-positive control. Across a broad range of memory budgets and numbers of hash functions, Super Bloom consistently outperforms existing Bloom filter implementations, with several-fold time improvements. As a practical validation, we integrated it into a Rust reimplementation of BioBloom Tools, a sequence screening tool that builds filters from reference genomes and classifies reads through k-mer membership queries for applications such as host removal and contamination filtering. This replacement yields substantially faster indexing and querying than both the original C++ implementation and Rust variants based on Bloom filters and blocked Bloom filters. The findere scheme also reduces false positives by several orders of magnitude, with some configurations yielding no observed false positives among 109 random queried k-mers. Code is available at https://github.com/EtienneC-K/SuperBloom and https://github.com/Malfoy/SBB.

bioinformatics↗

bioRxiv2025

Inverted colored de Bruijn Graph for practical kmer sets storage

Petabases of sequencing data in the Sequence Read Archive (SRA) present a significant challenge for holistic reanalysis due to their sheer volume. Recent efforts have assembled this data into terabytes of unitigs, an efficient k-mer set representation that can reduce data size by an order of magnitude. However, these unitigs were compressed on a per-accession basis, leaving substantial cross-sample redundancy unexploited. While co-compression of related samples offers high space-saving potential, existing tools lack targeted decompression: the ability to retrieve specific documents at a cost proportional to their individual sizes rather than that of the entire collection. This paper introduces the "inverted de Bruijn graph" property, formalizing the concept of efficient targeted decompression, and presents kloe, its first implementation. kloe is a compression method for large, highly similar k-mer multi-sets, such as collections of unitigs from related samples. Unlike existing approaches that map k-mers to colors (samples), kloe takes a complementary route by performing color-to-k-mer mapping, associating samples with their respective k-mer sets. This enables targeted decompression of any chosen samples k-mer content. At its core, kloe utilizes a new sequence construct called "monochromatigs," drawing on concepts from simplitigs and monotigs to achieve both significant space savings and efficient retrieval. Finally, a central aim of this work is to highlight this novel problem area, which we argue is critically understudied compared to colored de Bruijn graphs. The associated tool is available as an open source project at github.com/TimRouze/KLOE

bioinformatics↗

bioRxiv2023

Fractional Hitting Sets for Efficient and Lightweight Genomic Data Sketching

The exponential increase in publicly available sequencing data and genomic resources necessitates the development of highly efficient methods for data processing and analysis. Locality-sensitive hashing techniques have successfully transformed large datasets into smaller, more manageable sketches while maintaining comparability using metrics such as Jaccard and containment indices. However, fixed-size sketches encounter difficulties when applied to divergent datasets. Scalable sketching methods, such as Sourmash, provide valuable solutions but still lack resourceefficient, tailored indexing. Our objective is to create lighter sketches with comparable results while enhancing efficiency. We introduce the concept of Fractional Hitting Sets, a generalization of Universal Hitting Sets, which uniformly cover a specified fraction of the k-mer space. In theory and practice, we demonstrate the feasibility of achieving such coverage with simple but highly efficient schemes. By encoding the covered k-mers as super-k-mers, we provide a space-efficient exact representation that also enables optimized comparisons. Our novel tool, SuperSampler, implements this scheme, and experimental results with real bacterial collections closely match our theoretical findings. In comparison to Sourmash, SuperSampler achieves similar outcomes while utilizing an order of magnitude less space and memory and operating several times faster. This highlights the potential of our approach in addressing the challenges presented by the ever-expanding landscape of genomic data. SuperSampler is an open-source software and can be accessed at github.com/TimRouze/supersampler. The data required to reproduce the results presented in this manuscript is available at github.com/TimRouze/Expe_SPSP.

bioinformatics↗