Biology subjects

Vandamme, L.

Publications and source records attributed to Vandamme, L..

3 recordsLinked to original sources

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

Accelerating k-mer-based sequence filtering

MotivationThe exponential growth of global sequencing data repositories presents both analytical challenges and opportunities. While k-mer-based indexing has improved scalability over traditional alignment for identifying relevant documents, pinpointing the exact sequences matching numerous queries remains a hurdle. In particular, searching for numerous k-mers with a single large query or multiple distinct queries strains existing exact matching tools, whose performance scales poorly with an increasing number of patterns. At the same time, indexing entire vast datasets for infrequent or ad-hoc searches is often resource-prohibitive. Designing fast methods for matching a large number of k-mers without exhaustive pre-indexing is therefore critical. ContributionsWe propose an efficient solution to the problem of k-mer-based sequence filtering: given a set of k-mers of interests and a threshold, quickly evaluate whether an arbitrary sequence has a number of k-mer matches above or below the threshold. Our approach demonstrates how minimizer-based based sketching, alongside SIMD acceleration, can enhance the performance of streaming searches, and is implemented as a Rust tool named K2Rmini. On a consumer laptop, K2Rmini is able to filter long reads at 2 Gbp/s. Availabilityhttps://github.com/Malfoy/K2Rmini.

bioinformatics↗

bioRxiv2024

Tinted de Bruijn Graphs for efficient read extraction from sequencing datasets

The analysis of biological sequences often depends on reference genomes; however, achieving accurate assemblies remains a significant challenge. As a result, de novo analysis directly from raw sequencing reads, without pre-processing, is frequently a more practical approach. A common need across various applications is the ability to identify reads containing a specific k-mer within a dataset. This k-mer-to-read association is critical in multiple contexts, such as genotyping, bacterial strain resolution, profiling, data compression, error correction, and assembly. While this challenge appears similar to the extensively researched colored de Bruijn graph problem, resolving it at the read level is prohibitively resource-intensive for practical applications. In this work, we demonstrate its tractable resolution by leveraging reasonnable assumptions for genome sequencing dataset indexing. To tackle this challenge, we introduce the Tinted de Bruijn Graph concept, an altered version of the colored de Bruijn graph where each read in a sequencing dataset acts as a distinct source. We developed K2R, a highly scalable index that implements this framework efficiently. K2Rs performance, in terms of index size, memory footprint, throughput, and construction time, is benchmarked against leading methods, including hashing techniques (e.g., Short Read Connector and Fulgor), full-text indexing (e.g., Movi and Themisto) across various datasets. To demonstrate K2Rs scalability, we indexed two human datasets from the T2T consortium. The 126X coverage ONT dataset was indexed in 9 hours using 61GB of RAM, resulting in a 30GB index. Similarly, the 56X coverage HiFi dataset was indexed in less than 5 hours using 39GB of RAM, producing a 20.5GB index. Developed in C++, the K2R index is open-source and available on GitHub at http://github.com/LeaVandamme/K2R.

bioinformatics↗