Biology subjects

Martayan, I.

Publications and source records attributed to Martayan, I..

7 recordsLinked to original sources

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↗

bioRxiv2025

SimdMinimizers: Computing random minimizers, fast

MotivationBecause of the rapidly-growing amount of sequencing data, computing sketches of large textual datasets has become an essential preprocessing task. These sketches are typically much smaller than the input sequences, but preserve sufficient information for downstream analysis. Minimizers are an especially popular sketching technique and used in a wide variety of applications. They sample at least one out of every w consecutive k-mers. As DNA sequencers are getting more accurate, some applications can afford to use a larger w and hence sparser and smaller sketches. And as sketches get smaller, their analysis becomes faster, so the time spent sketching the full-sized input becomes more of a bottleneck. MethodsOur library simd-minimizers implements a random minimizer algorithm using SIMD instructions. It supports both AVX2 and NEON architectures. Its main novelty is two-fold. First, it splits the input into 8 chunks that are streamed over in parallel through all steps of the algorithm. This is enabled by using the completely deterministic two-stacks sliding window minimum algorithm, which seems not to have been used before for finding minimizers. ResultsOur library is up to 6.8x faster than a scalar implementation of the rescan method when w = 5 is small, and 3.4x faster for larger w = 19. Computing canonical minimizers is less than 50% slower than computing forward minimizers, and over 15x faster than the existing implementation in the minimizer-iter crate. Our library finds all (canonical) minimizers of a 3.2 Gbp human genome in 5.2 (resp. 6.7) seconds.

bioinformatics↗

bioRxiv2024

Brisk: Exact resource-efficient dictionary for k-mers

The rapid advancements in DNA sequencing technology have led to an unprecedented increase in the generation of genomic datasets, with modern sequencers now capable of producing up to ten terabases per run. However, the effective indexing and analysis of this vast amount of data pose significant challenges to the scientific community. K-mer indexing has proven crucial in managing extensive datasets across a wide range of applications, including alignment, compression, dataset comparison, error correction, assembly, and quantification. As a result, developing efficient and scalable k-mer indexing methods has become an increasingly important area of research. Despite the progress made, current state-of-the-art indexing structures are predominantly static, necessitating resource-intensive index reconstruction when integrating new data. Recently, the need for dynamic indexing structures has been recognized. However, many proposed solutions are only pseudo-dynamic, requiring substantial updates to justify the costs of adding new datasets. In practice, applications often rely on standard hash tables to associate data with their k-mers, leading to high k-mer encoding rates exceeding 64 bits per k-mer. In this work, we introduce Brisk, a drop-in replacement for most k-mer dictionary applications. This novel hashmap-like data structure provides high throughput while significantly reducing memory usage compared to existing dynamic associative indexes, particularly for large k-mer sizes. Brisk achieves this by leveraging hierarchical minimizer indexing and memory-efficient super-k-mer representation. We also introduce novel techniques for efficiently probing k-mers within a set of super-k-mers and managing duplicated minimizers. We believe that the methodologies developed in this work represent a significant advancement in the creation of efficient and scalable k-mer dictionaries, greatly facilitating their routine use in genomic data analysis.

bioinformatics↗

bioRxiv2024

Hyper-k-mers: efficient streaming k-mers representation

K-mers have become ubiquitous in modern bioinformatics pipelines. A key factor in their success is the ability to filter out erroneous k-mers by removing those with low abundances. However, large numbers of distinct k-mers make counting a memory-intensive step. Early tools addressed this issue by storing k-mers on disk. More recent solutions mitigate the excessive redundancy of overlapping k-mers by partially reassembling them into super-k-mers. Nevertheless, consecutive super-k-mers still overlap by k - 1 bases, leading to some degree of inefficiency. Here we present hyper-k-mers as an alternative, less redundant, representation of super-k-mers. Our contributions are three-fold. First, we propose hyper-k-mers, a new k-mer representation that asymptotically decreases duplication compared to super-k-mers. Second, we present a theoretical analysis comparing the space efficiency of super-k-mers, syncmers, and hyper-k-mers. Our approach offers significant advantages compared to super-k-mers, by reducing the asymptotic lower bound from 6 to 4 bits per nucleotide. Third, we present KFC, a k-mer counting algorithm leveraging hyper-k-mers. KFC offers significant practical advantages, including an order of magnitude improvement in memory usage compared to state-of-the-art tools. Notably, our experiments show that KFC is the only tool whose memory usage scales sub-linearly with k-mer size k, and is the fastest option when k is large. AvailabilityKFC is available at https://github.com/lrobidou/KFC with tests available at https://github.com/imartayan/KFC_experiments.

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↗

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↗

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↗