Biology subjects

Ingels, F.

Publications and source records attributed to Ingels, F..

4 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

Compressed inverted indexes for scalable sequence similarity

Modern sequencing continues to drive explosive growth of nucleotide sequence archives, pushing MinHash sketching methods to their scalability limits. Tools such as Mash, Dashing2, and Bindash2 provide compact sketches and accurate similarity estimates, but they typically use forward indexes that materialize each sketch as an explicit fingerprint vector. This architecture makes large-scale similarity search and collection-versus-collection comparison costly in both time and memory, especially at the scale of millions of sequences. We revisit sketch index architectures and develop a framework based on inverted indexes over sketch fingerprints. We introduce a cost model for sketch comparison and prove that, with suitably compressed posting lists, inverted indexes can match the asymptotic space complexity of forward indexes. Using this model, we design all-vs-all comparison algorithms between two inverted indexes whose running time is proportional to the total number of matching sketch positions, yielding outputsensitive optimality and enabling efficient large collection comparisons at scale. Because many applications impose similarity thresholds, we add two early-pruning schemes for Jaccard similarity. The first is exact and eliminates pairs guaranteed not to reach a target threshold. The second is probabilistic and exploits partial match statistics to discard pairs unlikely to exceed the threshold, with explicit control of the false-rejection probability. These schemes reduce time and memory while preserving rigorous guarantees on retained high-similarity pairs. We implement these ideas in Onika, an open-source Rust system built on compressed inverted posting lists at github.com/Malfoy/Onika. Onika also applies similarity-aware document reordering to shrink index size and improve locality, especially for redundant collections. Experiments on bacterial genome repositories and long-read HiFi datasets show that Onika matches or improves sketch sizes of leading tools while accelerating large-scale search and collection-versus-collection comparison by up to several orders of magnitude in low-redundancy regimes, without compromising sensitivity at practically relevant similarity thresholds.

bioinformatics↗

bioRxiv2025

Minimizer Density revisited: Models and Multiminimizers

High-throughput sequence analysis commonly relies on k-mers (words of fixed length k) to remain tractable at modern scales. These k-mer-based pipelines can employ a sampling step, which in turn allows grouping consecutive k-mers into larger strings to improve data locality. Although other sampling strategies exist, local schemes have become standard: such schemes map each k-mer to the position of one of its characters. A key performance measure of these schemes is their density, defined as the expected fraction of selected positions. The most widely used local scheme is the minimizer scheme: given an integer m [≤] k, a minimizer scheme associates each k-mer to the starting position of one of its m-mers, called its minimizer. Being a local scheme, the minimizer scheme guarantees covering all k-mers of a sequence, with a maximal distance between selected positions of w = k - m + 1. Recent works have established near-tight lower bounds on achievable density under standard assumptions for local schemes, and state-of-the-art schemes now operate close to these limits, suggesting that further improvements under the classical notion of density will face diminishing returns. Hence, in this work, we aim to revisit the notion of density and broaden its scope. As a first contribution, we draw a link between density and the distance between consecutive selected positions. We propose a probabilistic model allowing us to establish that the density of a local scheme is exactly the inverse of the expected distance between the positions it selects, under the minimal and only assumption that said distances are somehow equally distributed. We emphasize here that our model makes no assumptions about how positions are selected, unlike the classical models in the literature. Our result introduces a novel method for computing the density of a local scheme, extending beyond classical settings. Based on this analysis, we introduce a novel technique, named multiminimizers, by associating each k-mer with a bounded set of candidate minimizers rather than a single one. The candidate furthest away (in a precise sense defined in the article) is selected. Since the decision is made by taking advantage of a context beyond a single k-mer, this technique is not a local scheme -- and belong to a novel category of meta schemes. Using the multiminimizer trick on a local scheme reduces its density at the expense of a controlled increase in computation time. We show that this method, when applied to random (hash-based) minimizers and to open-closed mod-minimizers, approaches a density of [Formula], representing, to our knowledge, the first construction converging to this limit. Our third contribution is the introduction of the deduplicated density, which measures the fraction of distinct minimizers used to cover all k-mers of a set of sequences. While this problem has gained traction in applications such as assembly, filtering, and pattern matching, standard minimizer schemes are often used as a proxy, blurring the distinction between the two objectives (minimizing the number of selected positions or the number of selected minimizers). Although related to the classical notion of density, deduplicated density differs in both definition and suitable constructions, and must be analyzed in its own right, together with its precise connections to standard density. We show that multiminimizers can also improve this metric, but that globally minimizing deduplicated density in this setting is NP-complete, and we instead propose a local heuristic with strong empirical behavior. Finally, we show that multiminimizers can be computed efficiently, and provide a SIMD-accelerated Rust implementation together with proofs of concept demonstrating reduced memory footprints on core sequence-analysis tasks. We conclude with open theoretical and practical questions that remain to be addressed in the area of density.

bioinformatics↗

bioRxiv2024

Constrained enumeration of k-mers from a collection of references with metadata

While recent developments in k-mers indexing methods have opened up many new possibilities, they still have limitations in handling certain types of queries, such as identifying k-mers present in one dataset but absent in another. In this article, we present a framework for efficiently enumerating all k-mers within a collection of references that satisfy constraints related to their metadata tags. Our method involves simplifying the query beforehand to reduce computation delays; the construction of the solution itself is carried out using CBL, a recent data structure specifically dedicated to the optimised computation of set operations on k-mer sets. We provide an implementation to our solution and we demonstrate its capabilities using real genomic data (microbial and RNA-seq), and show examples of use cases to identify k-mers of biological interest. FundingThis work is funded by a grant from the French ANR: Full-RNA ANR-22-CE45-0007. Igor Martayan is supported by a doctoral grant from ENS Rennes.

bioinformatics↗