Biology subjects

Groot Koerkamp, R.

Publications and source records attributed to Groot Koerkamp, R..

9 recordsLinked to original sources

bioRxiv2026

Sassy2: Batch Searching of Short DNA Patterns

MotivationSearching short DNA patterns such as barcodes, primers, or CRISPR spacers within sequencing reads or genomes is a fundamental task in bioinformatics. These problems are instances of multiple approximate string matching (MASM) [Baeza-Yates and Navarro, 1997], which requires locating all occurrences with up to k errors of multiple patterns of length m in a text of length n. Classical approaches based on seeding with exact matches become inefficient for short patterns (m [≤] 64 bp) as k increases, producing either many spurious hits or missing true matches. Our previous work, Sassy1, showed that careful hardware optimization drastically accelerates single-pattern searches in long texts by distributing chunks of the text across SIMD lanes. MethodsSassy2 distributes multiple patterns across SIMD lanes to maximize parallelism when searching batches of short patterns. When k is small, often only a short substring of the pattern of length O(k) is needed to reject a possible match. Thus, Sassy2 first examines short suffixes of the patterns (e.g., the last 16 bp of 32 bp patterns), allowing more (but smaller) parallel SIMD lanes. Only positions passing this suffix filter undergo full pattern verification. ResultsOn synthetic data, Sassy2 achieves 10-50x speedups over Sassy1 for short texts (n [≤] 200 bp) and 2-4x for large texts (n [≥] 1 Mbp). On real-world tasks with 16 threads, Sassy2 reaches over 100 Gbp/s text throughput per guide when searching 312 gRNAs across the human genome and 116 Gbp/s throughput when demultiplexing Nanopore reads with 96 barcodes. In both cases, Sassy2 outperforms Sassy1 by 2-5x and Edlib by 20-45x. AvailabilitySassy2 is implemented in Rust and available at github.com/RagnarGrootKoerkamp/sassy.

bioinformatics↗

bioRxiv2025

mim: A lightweight auxiliary index to enable fast, parallel, gzipped FASTQ parsing

The FASTQ file format is the lingua franca of primary data distribution and processing across most of bioinformatics. Over time, the compression, storage, transmission, and decompression of gzip compressed fastq.gz files has become a substantial scalability bottleneck in the modern world of fast and massively parallel genomics tools and algorithms. In this work, we introduce mim: a lightweight, auxiliary index that enables fast, parallel, and highly-scalable parsing of compressed fastq.gz files. The creation of the mim index for a file is a one-time operation that can be performed in time comparable to that of simply decompressing and parsing the file (index creation induces [~] 20% overhead) and with minimal working memory. The mim index itself is very small, usually about [Formula]th of the size of the original compressed file, and can be easily stored along side the file or fetched from a remote location when it is needed. Further, the mim index is purely additive -- it does not modify the original gzipped FASTQ file in any way, nor require that the file be recompressed or rewritten -- and thus it does not require converting the massive back catalog of existing raw sequencing data. To demonstrate the feasibility and utility of the mim index, we benchmark construction of the mim index on a variety of existing gzipped FASTQ data, and also measure thread-scaling of mim index-assisted parallel FASTQ parsing on a simple parsing/ decompression-related task. We find that, for the one-time cost of index creation, and a small fraction of extra storage space, the mim index can massively accelerate the ingestion and parsing of gzipped FASTQ data, exhibiting near linear thread scaling in our experiments. mim is written in C++17, and is available as open source software under a BSD 3-clause license at https://github.com/COMBINE-lab/mim.

bioinformatics↗

bioRxiv2025

Barbell Resolves Demultiplexing and Trimming Issues in Nanopore Data

BackgroundOxford Nanopore sequencing enables long-read sequencing across diverse applications, yet the experimental artifacts introduced by Nanopore barcoding are not well characterized. These artifacts can affect demultiplexing accuracy and downstream analyses. ResultsWe performed a rapid barcoding experiment on 66 diagnostic samples and found that 83% of reads carried the expected single-barcode pattern, while 17% contained multiple barcodes or other artifacts. Current demultiplexers, including the widely used Dorado, fail to correctly handle these complex cases, leaving approximately 7% of reads partially trimmed and contaminated with adapter fragments. Additional issues include the presence of two barcodes at the same read end--either identical, originating from the same sample, or different, introduced after pooling. The latter can lead to barcode bleeding when the outer barcode is incorrectly selected. To address these challenges, we developed Barbell, a pattern-aware demultiplexer that detects all barcode configurations. Barbell reduces trimming errors by three orders of magnitude, minimizes barcode bleeding, and supports custom experimental setups such as shorter barcodes, dual-end barcodes, and custom flank sequences. ConclusionsOur results highlight the impact of complex barcode attachments in Nanopore sequencing and demonstrate that Barbell drastically reduces their effects on downstream analyses. Barbell is open source and available at https://github.com/rickbeeloo/barbell.

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

The open-closed mod-minimizer algorithm

Sampling algorithms that deterministically select a subset of k-mers are an important building block in bioinformatics applications. For example, they are used to index large textual collections, like DNA, and to compare sequences quickly. In such applications, a sampling algorithm is required to select one k-mer out of every window of w consecutive k-mers. The folklore and most used scheme is the random minimizer that selects the smallest k-mer in the window according to some random order. This scheme is remarkably simple and versatile, and has a density (expected fraction of selected k-mers) of 2/(w + 1). In practice, lower density leads to faster methods and smaller indexes, and it turns out that the random minimizer is not the best one can do. Indeed, some schemes are known to approach optimal density 1/w when k [->] {infty}, like the recently introduced mod-minimizer (Groot Koerkamp and Pibiri, WABI 2024). In this work, we study methods that achieve low density when k [≤] w. In this small-k regime, a practical method with provably better density than the random minimizer is the miniception (Zheng et al., Bioinformatics 2021). This method can be elegantly described as sampling the smallest closed sycnmer (Edgar, PeerJ 2021) in the window according to some random order. We show that extending the miniception to prefer sampling open syncmers yields much better density. This new method - the open-closed minimizer - offers improved density for small k [≤] w while being as fast to compute as the random minimizer. Compared to methods based on decycling sets, that achieve very low density in the small-k regime, our method has comparable density while being computationally simpler and intuitive. Furthermore, we extend the mod-minimizer to improve density of any scheme that works well for small k to also work well when k > w is large. We hence obtain the open-closed mod-minimizer, a practical method that improves over the mod-minimizer for all k.

bioinformatics↗

bioRxiv2024

A near-tight lower bound on the density of forward sampling schemes

MotivationSampling k-mers is a ubiquitous task in sequence analysis algorithms. Sampling schemes such as the often-used random minimizer scheme are particularly appealing as they guarantee at least one k-mer is selected out of every w consecutive k-mers. Sampling fewer k-mers often leads to an increase in efficiency of downstream methods. Thus, developing schemes that have low density, i.e., have a small proportion of sampled k-mers, is an active area of research. After over a decade of consistent efforts in both decreasing the density of practical schemes and increasing the lower bound on the best possible density, there is still a large gap between the two. ResultsWe prove a near-tight lower bound on the density of forward sampling schemes, a class of schemes that generalizes minimizer schemes. For small w and k, we observe that our bound is tight when k {equiv} 1 (mod w). For large w and k, the bound can be approximated by [Formula]. Importantly, our lower bound implies that existing schemes are much closer to achieving optimal density than previously known. For example, with the current default minimap2 HiFi settings w = 19 and k = 19, we show that the best known scheme for these parameters, the double decycling-set-based minimizer of Pellow et al., is at most 3% denser than optimal, compared to the previous gap of at most 50%. Furthermore, when k {equiv} 1 (mod w) and the alphabet size{sigma} goes to {infty}, we show that mod-minimizers introduced by Groot Koerkamp and Pibiri achieve optimal density matching our lower bound. Availability and implementationMinimizer implementations: github.com/RagnarGrootKoerkamp/minimizers ILP and analysis: github.com/treangenlab/sampling-scheme-analysis

bioinformatics↗

bioRxiv2024

The mod-minimizer: a simple and efficient sampling algorithm for long k-mers

MotivationGiven a string S, a minimizer scheme is an algorithm defined by a triple (k, w, [O]) that samples a subset of k-mers (k-long substrings) from a string S. Specifically, it samples the minimal k-mer according to the order [O] from each window of w consecutive k-mers in S. Because consecutive windows can sample the same k-mer, the set of the sampled k-mers is typically much smaller than S. More generally, we consider substring sampling algorithms that respect a window guarantee: at least one k-mer must be sampled from every window of w consecutive k-mers. As a sampled k-mer is uniquely identified by its absolute position in S, we can define the density of a sampling algorithm as the fraction of distinct sampled positions. Good methods have low density which, by respecting the window guarantee, is lower bounded by 1/w. It is however difficult to design a sequence-agnostic algorithm with provably optimal density. In practice, the order [O] is usually implemented using a pseudo-random hash function to obtain the so-called random minimizer. This scheme is simple to implement, very fast to compute even in streaming fashion, and easy to analyze. However, its density is almost a factor of 2 away from the lower bound for large windows. MethodsIn this work we introduce mod-sampling, a two-step sampling algorithm to obtain new minimizer schemes. Given a (small) parameter t, the mod-sampling algorithm finds the position i of the minimal t-mer in a window. It then samples the k-mer at position i mod w. The lr-minimizer uses t = k - w and the mod-minimizer uses t {equiv} k (mod w). ResultsThese new schemes have provably lower density than random minimizers and other schemes when k is large compared to w, while being as fast to compute. Importantly, the mod-minimizer achieves optimal density when k [->] {infty}. Although the mod-minimizer is not the first method to achieve optimal density for large k, its proof of optimality is simpler than previous work. We provide pseudocode for a number of other methods and compare to them. In practice, the mod-minimizer has considerably lower density than the random minimizer and other state-of-the-art methods, like closed syncmers and miniception, when k > w. We plugged the mod-minimizer into SSHash, a k-mer dictionary based on minimizers. For default parameters (w, k) = (11, 21), space usage decreases by 15% when indexing the whole human genome (GRCh38), while maintaining its fast query time.

bioinformatics↗

bioRxiv2024

A*PA2: up to 20 times faster exact global alignment

MethodsWe introduce A*PA2, an exact global pairwise aligner with respect to edit distance. The goal of A*PA2 is to unify the near-linear runtime of A*PA on similar sequences with the efficiency of dynamic programming (DP) based methods. Like EO_SCPLOWDLIBC_SCPLOW, A*PA2 uses Ukkonens band doubling in combination with Myers bitpacking. A*PA2 1) extends this with SIMD (single instruction, multiple data), 2) uses large block sizes inspired by BO_SCPLOWLOCKC_SCPLOW AO_SCPLOWLIGNERC_SCPLOW, 3) avoids recomputation of states where possible as suggested before by Fickett, 4) introduces a new optimistic technique for traceback based on diagonal transition, and 5) applies the heuristics developed in A*PA and improves them using pre-pruning. ResultsThe average runtime of A*PA2 is 19x faster than the exact aligners BO_SCPLOWIC_SCPLOWWFA and EO_SCPLOWDLIBC_SCPLOW on >500 kbp long ONT reads of a human genome having 6% divergence on average. On shorter ONT reads of 11% average divergence the speedup is 5.6x (avg. length 11 kbp) and 0.81x (avg. length 800 bp). On all tested datasets, A*PA2 is competitive with or faster than approximate methods. Availabilitygithub.com/RagnarGrootKoerkamp/astar-pairwise-aligner Contactragnar.grootkoerkamp@inf.ethz.ch

bioinformatics↗

bioRxiv2022

Exact global alignment using A* with seed heuristic and match pruning

MotivationSequence alignment has been at the core of computational biology for half a century. Still, it is an open problem to design a practical algorithm for exact alignment of a pair of related sequences in linear-like time (Medvedev, 2022b). MethodsWe solve exact global pairwise alignment with respect to edit distance by using the A* shortest path algorithm. In order to efficiently align long sequences with high divergence, we extend the recently proposed seed heuristic (Ivanov et al., 2022) with match chaining, gap costs, and inexact matches. We additionally integrate the novel match pruning technique and diagonal transition (Ukkonen, 1985) to improve the A* search. We prove the correctness of our algorithm, implement it in the A*PA aligner, and justify our extensions intuitively and empirically. ResultsOn random sequences of divergence d=4% and length n, the empirical runtime of A*PA scales near-linearly with length (best fit n1.06, n[≤]107 bp). A similar scaling remains up to d=12% (best fit n1.24, n[≤]107 bp). For n=107 bp and d=4%, A*PA reaches >500x speedup compared to the leading exact aligners EDLIB and BIWFA. The performance of A*PA is highly influenced by long gaps. On long (n>500 kbp) ONT reads of a human sample it efficiently aligns sequences with d<10%, leading to 3x median speedup compared to EDLIB and BIWFA. When the sequences come from different human samples, A*PA performs 1.7x faster than EDLIB and BIWFA. Availabilitygithub.com/RagnarGrootKoerkamp/astar-pairwise-aligner Contactragnar.grootkoerkamp@inf.ethz.ch, pesho@inf.ethz.ch

bioinformatics↗