Biology subjects

Cazaux, B.

Publications and source records attributed to Cazaux, B..

7 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↗

bioRxiv2024

Conway-Bromage-Lyndon (CBL): an exact, dynamic representation of k-mer sets

In this paper, we introduce the Conway-Bromage-Lyndon (CBL) structure, a compressed, dynamic and exact method for representing k-mer sets. Originating from Conway and Bromages concept, CBL innovatively employs the smallest cyclic rotations of k-mers, akin to Lyndon words, to leverage lexicographic redundancies. In order to support dynamic operations and set operations, we propose a dynamic bit vector structure that draws a parallel with Elias-Fanos scheme. This structure is encapsulated in a Rust library, demonstrating a balanced blend of construction efficiency, cache locality, and compression. Our findings suggest that CBL outperforms existing dynamic k-mer set methods. Unique to this work, CBL stands out as the only known exact k-mer structure offering in-place set operations. Its different combined abilities position it as a flexible Swiss knife structure for k-mer set management. Availability: https://github.com/imartayan/CBL

bioinformatics↗

bioRxiv2022

dipwmsearch: a python package for searching di-PWM motifs

MotivationSeeking probabilistic motifs in a sequence is a common task to annotate putative transcription factor binding sites (TFBS). Useful motif representations include Position Weight Matrices (PWMs), dinucleotidic PWMs (di-PWMs), and Hidden Markov Models (HMMs). Dinucleotidic PWMs combine the simplicity of PWMs - a matrix form and a cumulative scoring function -, but also incoporate dependency between adjacent positions in the motif (unlike PWMs which disregard any dependency). For instance, to represent binding sites, the HOCOMOCO database provides di-PWM motifs derived from experimental data. Currently, two programs, SPRy-SARUS and MOODS, can search for di-PWMs in sequences. ResultsWe propose a Python package, dipwmsearch, which provides an original and efficient algorithm for this task (it first enumerates matching words for the di-PWM, and then search them at once in the sequence even if it contains IUPAC codes). The user benefits from an easy installation via Pypi or conda, a documented Python interface, and reusable example scripts that smooth the use of di-PWMs. Availability and Implementationdipwmsearch is available at https://pypi.org/project/dipwmsearch/ and https://gite.lirmm.fr/rivals/dipwmsearch/ under Cecill license.

bioinformatics↗

bioRxiv2022

A survey of mapping algorithms in the long-reads era

It has been ten years since the first publication of a method dedicated entirely to mapping third-generation sequencing long-reads. The unprecedented characteristics of this new type of sequencing data created a shift, and methods moved on from the seed-and-extend framework previously used for short reads to a seed-and-chain framework due to the abundance of seeds in each read. As a result, the main novelties in proposed long-read mapping algorithms are typically based on alternative seed constructs or chaining formulations. Dozens of tools now exist, whose heuristics have considerably evolved with time. The rapid progress of the field, synchronized with the frequent improvements of data, does not make the literature and implementations easy to keep up with. Therefore, in this survey article, we provide an overview of existing mapping methods for long reads with accessible insights into methods. Since mapping is also very driven by the implementations themselves, we join an original visualization tool to understand the parameter settings (http://bcazaux.polytech-lille.net/Minimap2/) for the chaining part.

bioinformatics↗

bioRxiv2021

Toward optimal fingerprint indexing for large scale genomics

MotivationTo keep up with the scale of genomic databases, several methods rely on local sensitive hashing methods to efficiently find potential matches within large genome collections. Existing solutions rely on Minhash or Hyperloglog fingerprints and require reading the whole index to perform a query. Such solutions can not be considered scalable with the growing amount of documents to index. ResultsWe present NIQKI, a novel structure with well-designed fingerprints that lead to theoretical and practical query time improvements, outperforming state-of-the-art by orders of magnitude. Our contribution is threefold. First, we generalize the concept of Hyperminhash fingerprints in (h,m)-HMH fingerprints that can be tuned to present the lowest false positive rate given the expected sub-sampling applied. Second, we provide a structure able to index any kind of fingerprints based on inverted indexes that provide optimal queries, namely linear with the size of the output. Third, we implemented these approaches in a tool dubbed NIQKI that can index and calculate pairwise distances for over one million bacterial genomes from GenBank in a few days on a small cluster. We show that our approach can be orders of magnitude faster than state-of-the-art with comparable precision. We believe this approach can lead to tremendous improvements, allowing fast queries and scaling on extensive genomic databases. Availability and implementationWe wrote the NIQKI index as an open-source C++ library under the AGPL3 license available at https://github.com/Malfoy/NIQKI. It is designed as a user-friendly tool and comes along with usage samples. 2012 ACM Subject ClassificationApplied computing [->] Bioinformatics Digital Object Identifier10.4230/LIPIcs.WABI.2022.25

bioinformatics↗