Search Results

Documents authored by Groot Koerkamp, Ragnar

Artifact
Software
DOI: 10.4230/artifacts.26761
STPD-index

Authors: Ruben Becker, Davide Cenzato, Travis Gagie, Ragnar Groot Koerkamp, Sung-Hwan Kim, Giovanni Manzini, and Nicola Prezza

Abstract
Cite as

Ruben Becker, Davide Cenzato, Travis Gagie, Ragnar Groot Koerkamp, Sung-Hwan Kim, Giovanni Manzini, Nicola Prezza. STPD-index (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-26761,
   title = {{STPD-index}}, 
   author = {Becker, Ruben and Cenzato, Davide and Gagie, Travis and Groot Koerkamp, Ragnar and Kim, Sung-Hwan and Manzini, Giovanni and Prezza, Nicola},
   note = {Software, Funded by the European Union (ERC, REGINDEX, 101039208), swhId: \href{https://archive.softwareheritage.org/swh:1:dir:d4f76a2be744c622f98d403443e3f4507ae9b536;origin=https://github.com/regindex/STPD-index;visit=swh:1:snp:15232c90524e31eb789f2fce1686ae9a23d5f70f;anchor=swh:1:rev:4d8522e4fc1e7bc9781724352e4dcdefb0b8579d}{\texttt{swh:1:dir:d4f76a2be744c622f98d403443e3f4507ae9b536}} (visited on 2026-07-01)},
   url = {https://github.com/regindex/STPD-index},
   doi = {10.4230/artifacts.26761},
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.24
Compressing Suffix Trees by Path Decompositions

Authors: Ruben Becker, Davide Cenzato, Travis Gagie, Ragnar Groot Koerkamp, Sung-Hwan Kim, Giovanni Manzini, and Nicola Prezza

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract
The suffix tree is arguably the most fundamental data structure on strings: introduced by Weiner (SWAT 1973) and McCreight (JACM 1976), it allows solving a myriad of computational problems on strings in linear time. Motivated by its large space usage, subsequent research focused first on reducing its size by a constant factor via Suffix Arrays, and later on reaching space proportional to the size of the compressed string. Modern compressed indexes, such as the r-index (Gagie et al., JACM 2020), fit in space proportional to r, the number of runs in the Burrows-Wheeler transform (a strong and universal repetitiveness measure). These advances, however, came with a price: while modern compressed indexes boast optimal bounds in the RAM model, they are often orders of magnitude slower than uncompressed counterparts in practice due to catastrophic cache locality. This reality gap highlights that Big-O complexity in the RAM model has become a misleading predictor of real-world performance, leaving a critical question unanswered: can we design compressed indexes that are efficient in the I/O model of computation? We answer this in the affirmative by introducing a new Suffix Array sampling technique based on particular path decompositions of the suffix tree. We prove that sorting the suffix tree leaves by specific priority functions induces a decomposition where the number of distinct paths (each corresponding to a string suffix) is bounded by r. This allows us to solve indexed pattern matching efficiently in the I/O model using a Suffix Array sample of size at most r, strictly improving upon the (tight) 2r bound of Suffixient Arrays, another recent compressed Suffix Array sampling technique. Experiments confirm that this theoretical I/O efficiency translates to practice in pangenomic applications: our index locates pattern occurrences using less space and orders of magnitude less time than the r-index when performing pattern matching on repetitive DNA collections. Beyond this, our contributions are twofold: (i) unlike Suffixient Arrays, our technique supports most standard suffix tree operations in O(r) space on top of the text while matching the I/O complexity of uncompressed suffix trees; and (ii) we establish a general framework where any valid path decomposition induces a Suffix Array sampling whose size is a new strong repetitiveness measure; we provide a universal mechanism for locating all pattern occurrences for each such path decomposition.
Cite as

Ruben Becker, Davide Cenzato, Travis Gagie, Ragnar Groot Koerkamp, Sung-Hwan Kim, Giovanni Manzini, and Nicola Prezza. Compressing Suffix Trees by Path Decompositions. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 24:1-24:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{becker_et_al:LIPIcs.ICALP.2026.24,
  author =	{Becker, Ruben and Cenzato, Davide and Gagie, Travis and Groot Koerkamp, Ragnar and Kim, Sung-Hwan and Manzini, Giovanni and Prezza, Nicola},
  title =	{{Compressing Suffix Trees by Path Decompositions}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{24:1--24:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.24},
  URN =		{urn:nbn:de:0030-drops-264139},
  doi =		{10.4230/LIPIcs.ICALP.2026.24},
  annote =	{Keywords: Text indexing, suffix tree, I/O-efficient, Compressed Data Structures}
}
Artifact
Software
DOI: 10.4230/artifacts.25696
RagnarGrootKoerkamp/quadrank

Authors: Ragnar Groot Koerkamp

Abstract
Cite as

Ragnar Groot Koerkamp. RagnarGrootKoerkamp/quadrank (Software). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-25696,
   title = {{RagnarGrootKoerkamp/quadrank}}, 
   author = {Groot Koerkamp, Ragnar},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:83a2ce8d57ab4f246e470f1226e19ecafb51fffe}{\texttt{swh:1:dir:83a2ce8d57ab4f246e470f1226e19ecafb51fffe}} (visited on 2026-06-15)},
   url = {https://github.com/RagnarGrootKoerkamp/quadrank},
   doi = {10.4230/artifacts.25696},
}
Document
DOI: 10.4230/LIPIcs.SEA.2026.20
QuadRank: Engineering a High Throughput Rank

Authors: Ragnar Groot Koerkamp

Published in: LIPIcs, Volume 371, 24th International Symposium on Experimental Algorithms (SEA 2026)

Abstract
Motivation. Given a text, a query rank(q, c) counts the number of occurrences of character c among the first q characters of the text. Space-efficient methods to answer these rank queries form an important building block in many succinct data structures. For example, the FM-index [Ferragina and Manzini, 2000] is a widely used data structure that uses rank queries to locate all occurrences of a pattern in a text. In bioinformatics applications, the goal is usually to process large inputs as fast as possible. Thus, data structures should have high throughput when used with many threads. Contributions. We first survey existing results on rank data structures. For the σ = 2 binary alphabet, we then develop BiRank, which has 3.28% space overhead. BiRank merges the central ideas of two recent papers: (1) we interleave (inline) offsets in each cache line of the underlying bit vector [Laws et al., 2024], reducing cache misses, and (2) these offsets are to the middle of each block so that only half of each needs popcounting [Gottlieb and Reinert, 2025]. In QuadRank (14.4% overhead), we extend these techniques to the σ = 4 (DNA) alphabet. Both data structures typically require only a single cache miss per query, making them highly suitable for high-throughput and memory-bound settings. To enable efficient batch-processing, we support prefetching the cache lines required to answer upcoming queries. Results. BiRank and QuadRank are around 1.5× and 2× faster than similar-overhead methods that do not use interleaving. Prefetching gives an additional 2× speedup, at which point the dual-channel DDR4 RAM bandwidth becomes a hard limit on the total throughput. With prefetching, both methods outperform all other methods apart from SPIDER [Laws et al., 2024] by 2×. When using QuadRank with prefetching in a toy count-only FM-index, QuadFm, this results in a smaller size and up to 4× speedup over Genedex, a state-of-the-art batching FM-index implementation. Conclusion. Optimizing data structures for high throughput, by minimizing cache misses and branch-misses and adding support for prefetching, can result in significant speedups when benchmarks are adjusted accordingly.
Cite as

Ragnar Groot Koerkamp. QuadRank: Engineering a High Throughput Rank. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 20:1-20:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{grootkoerkamp:LIPIcs.SEA.2026.20,
  author =	{Groot Koerkamp, Ragnar},
  title =	{{QuadRank: Engineering a High Throughput Rank}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{20:1--20:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-422-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{371},
  editor =	{Aum\"{u}ller, Martin and Finocchi, Irene},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.20},
  URN =		{urn:nbn:de:0030-drops-260248},
  doi =		{10.4230/LIPIcs.SEA.2026.20},
  annote =	{Keywords: Rank, Succinct Data Structures, Cache Performance, Prefetching}
}
Artifact
Software
DOI: 10.4230/artifacts.23785
rust-seq/simd-minimizers

Authors: Ragnar Groot Koerkamp and Igor Martayan

Abstract
Cite as

Ragnar Groot Koerkamp, Igor Martayan. rust-seq/simd-minimizers (Software). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-23785,
   title = {{rust-seq/simd-minimizers}}, 
   author = {Groot Koerkamp, Ragnar and Martayan, Igor},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:d2fbef4c7750f02bc5cb084d0873078fef7f4e22;origin=https://github.com/rust-seq/simd-minimizers;visit=swh:1:snp:7f3e2736cab8ed6759548175a13879f7a95d5bab;anchor=swh:1:rev:078083e8e1f4dbb50ecaf5af8b56a492c72f4bd3}{\texttt{swh:1:dir:d2fbef4c7750f02bc5cb084d0873078fef7f4e22}} (visited on 2025-07-15)},
   url = {https://github.com/rust-seq/simd-minimizers},
   doi = {10.4230/artifacts.23785},
}
Artifact
Software
DOI: 10.4230/artifacts.23786
rust-seq/packed-seq

Authors: Ragnar Groot Koerkamp and Igor Martayan

Abstract
Cite as

Ragnar Groot Koerkamp, Igor Martayan. rust-seq/packed-seq (Software). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-23786,
   title = {{rust-seq/packed-seq}}, 
   author = {Groot Koerkamp, Ragnar and Martayan, Igor},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:181f8591389fdf9b941ac6f225a26d2784514787;origin=https://github.com/rust-seq/packed-seq;visit=swh:1:snp:fbb51df438475fe6020067c31d4045f9c1e4d377;anchor=swh:1:rev:e1ec76637d56e1c4bce9f4dc2e3cc32a6dd0b57a}{\texttt{swh:1:dir:181f8591389fdf9b941ac6f225a26d2784514787}} (visited on 2025-07-15)},
   url = {https://github.com/rust-seq/packed-seq},
   doi = {10.4230/artifacts.23786},
}
Artifact
Software
DOI: 10.4230/artifacts.23124
RagnarGrootKoerkamp/PtrHash

Authors: Ragnar Groot Koerkamp

Abstract
Cite as

Ragnar Groot Koerkamp. RagnarGrootKoerkamp/PtrHash (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-23124,
   title = {{RagnarGrootKoerkamp/PtrHash}}, 
   author = {Groot Koerkamp, Ragnar},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:5d61696060557f1473ab06eb35d9eaa86d682384;origin=https://github.com/RagnarGrootKoerkamp/PtrHash;visit=swh:1:snp:d758a10ef3720add298a634477960f35038684c0;anchor=swh:1:rev:20499ecf57102589ad513d8a3dafeb9c6a6ed164}{\texttt{swh:1:dir:5d61696060557f1473ab06eb35d9eaa86d682384}} (visited on 2025-07-15)},
   url = {https://github.com/RagnarGrootKoerkamp/PtrHash},
   doi = {10.4230/artifacts.23124},
}
Document
DOI: 10.4230/LIPIcs.SEA.2025.4
U-Index: A Universal Indexing Framework for Matching Long Patterns

Authors: Lorraine A. K. Ayad, Gabriele Fici, Ragnar Groot Koerkamp, Grigorios Loukides, Rob Patro, Giulio Ermanno Pibiri, and Solon P. Pissis

Published in: LIPIcs, Volume 338, 23rd International Symposium on Experimental Algorithms (SEA 2025)

Abstract
Motivation. Text indexing is a fundamental and well-studied problem. Classic solutions to this problem either replace the original text with a compressed representation, e.g., the FM-index and its variants, or keep it uncompressed but attach some redundancy - an index - to accelerate matching, e.g., the suffix array. The former solutions thus retain excellent compressed space, but are practically slow to construct and query. The latter approaches, instead, sacrifice space efficiency but are typically faster; for example, the suffix array takes much more space than the text itself for commonly used alphabets, like ASCII or DNA, but it is very fast to construct and query. Methods. In this paper, we show that efficient text indexing can be achieved using just a small extra space on top of the original text, provided that the query patterns are sufficiently long. More specifically, we develop a new indexing paradigm in which a sketch of a query pattern is first matched against a sketch of the text. Once candidate matches are retrieved, they are verified using the original text. This paradigm is thus universal in the sense that it allows us to use any solution to index the sketched text, like a suffix array, FM-index, or r-index. Results. We explore both the theory and the practice of this universal framework. With an extensive experimental analysis, we show that, surprisingly, universal indexes can be constructed much faster than their unsketched counterparts and take a fraction of the space, as a direct consequence of (i) having a lower bound on the length of patterns and (ii) working in sketch space. Furthermore, these data structures have the potential of retaining or even improving query time, because matching against the sketched text is faster and verifying candidates can be theoretically done in constant time per occurrence (or, in practice, by short and cache-friendly scans of the text). Finally, we discuss some important applications of this novel indexing paradigm to computational biology. We hypothesize that such indexes will be particularly effective when the queries are sufficiently long, and so we demonstrate applications in long-read mapping.
Cite as

Lorraine A. K. Ayad, Gabriele Fici, Ragnar Groot Koerkamp, Grigorios Loukides, Rob Patro, Giulio Ermanno Pibiri, and Solon P. Pissis. U-Index: A Universal Indexing Framework for Matching Long Patterns. In 23rd International Symposium on Experimental Algorithms (SEA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 338, pp. 4:1-4:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ayad_et_al:LIPIcs.SEA.2025.4,
  author =	{Ayad, Lorraine A. K. and Fici, Gabriele and Groot Koerkamp, Ragnar and Loukides, Grigorios and Patro, Rob and Pibiri, Giulio Ermanno and Pissis, Solon P.},
  title =	{{U-Index: A Universal Indexing Framework for Matching Long Patterns}},
  booktitle =	{23rd International Symposium on Experimental Algorithms (SEA 2025)},
  pages =	{4:1--4:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-375-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{338},
  editor =	{Mutzel, Petra and Prezza, Nicola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2025.4},
  URN =		{urn:nbn:de:0030-drops-232420},
  doi =		{10.4230/LIPIcs.SEA.2025.4},
  annote =	{Keywords: Text Indexing, Sketching, Minimizers, Hashing}
}
Document
DOI: 10.4230/LIPIcs.SEA.2025.20
SimdMinimizers: Computing Random Minimizers, fast

Authors: Ragnar Groot Koerkamp and Igor Martayan

Published in: LIPIcs, Volume 338, 23rd International Symposium on Experimental Algorithms (SEA 2025)

Abstract
Motivation. Because 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. Methods. Our 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. Results. Our library is up to 6.8× faster than a scalar implementation of the rescan method when w = 5 is small, and 3.4× faster for larger w = 19. Computing canonical minimizers is less than 50% slower than computing forward minimizers, and over 15× 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.
Cite as

Ragnar Groot Koerkamp and Igor Martayan. SimdMinimizers: Computing Random Minimizers, fast. In 23rd International Symposium on Experimental Algorithms (SEA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 338, pp. 20:1-20:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{grootkoerkamp_et_al:LIPIcs.SEA.2025.20,
  author =	{Groot Koerkamp, Ragnar and Martayan, Igor},
  title =	{{SimdMinimizers: Computing Random Minimizers, fast}},
  booktitle =	{23rd International Symposium on Experimental Algorithms (SEA 2025)},
  pages =	{20:1--20:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-375-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{338},
  editor =	{Mutzel, Petra and Prezza, Nicola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2025.20},
  URN =		{urn:nbn:de:0030-drops-232581},
  doi =		{10.4230/LIPIcs.SEA.2025.20},
  annote =	{Keywords: Minimizers, Randomized algorithms, Sketching, Hashing}
}
Document
DOI: 10.4230/LIPIcs.SEA.2025.21
PtrHash: Minimal Perfect Hashing at RAM Throughput

Authors: Ragnar Groot Koerkamp

Published in: LIPIcs, Volume 338, 23rd International Symposium on Experimental Algorithms (SEA 2025)

Abstract
Motivation. Given a set K of n keys, a minimal perfect hash function (MPHF) is a collision-free bijective map H_mphf from K to {0, … , n-1}. These functions have uses in databases, search engines, and are used in bioinformatics indexing tools such as Pufferfish (using BBHash), and Piscem (PTHash). PTHash is also used in SSHash, a data structure on k-mers that supports membership queries. PTHash only takes around 5% of the total space of SSHash, and thus, trading slightly more space for faster queries is beneficial. Thus, this work presents a (minimal) perfect hash function that first prioritizes query throughput, while also allowing efficient construction for 10⁹ or more elements using 2.4 bits of memory per key. Contributions. Both PTHash and PHOBIC first map all n keys to n/λ < n buckets. Then, each bucket stores a pilot that controls the final hash value of the keys mapping to it. PtrHash builds on this by using 1) fixed-width (uncompressed) 8-bit pilots, 2) a construction algorithm similar to Cuckoo hashing to find suitable pilot values. Further, it partitions the keys, so that keys in each part map to their own set of slots. PtrHash 3) uses the same number of buckets and slots for each part, with 4) a single remap table to map intermediate positions ≥ n to < n, 5) encoded using per-cacheline Elias-Fano coding. Lastly, 6) PtrHash supports streaming queries, where we use prefetching to answer a stream of multiple queries more efficiently than one-by-one processing. Results. With default parameters, PtrHash takes 2.4 bits per key. On 300 million string keys, PtrHash is as fast or faster to build than other MPHFs at a similar size, and at least 2.1× faster to query. When streaming multiple queries, this improves to 3.3× speedup over the fastest alternative, while also being significantly faster to construct. When using 10⁹ integer keys instead, query times are as low as 12 ns/key when iterating in a for loop, or even down to 8 ns/key when using the streaming approach, just short of the 7.4 ns inverse throughput of random memory accesses.
Cite as

Ragnar Groot Koerkamp. PtrHash: Minimal Perfect Hashing at RAM Throughput. In 23rd International Symposium on Experimental Algorithms (SEA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 338, pp. 21:1-21:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{grootkoerkamp:LIPIcs.SEA.2025.21,
  author =	{Groot Koerkamp, Ragnar},
  title =	{{PtrHash: Minimal Perfect Hashing at RAM Throughput}},
  booktitle =	{23rd International Symposium on Experimental Algorithms (SEA 2025)},
  pages =	{21:1--21:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-375-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{338},
  editor =	{Mutzel, Petra and Prezza, Nicola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2025.21},
  URN =		{urn:nbn:de:0030-drops-232597},
  doi =		{10.4230/LIPIcs.SEA.2025.21},
  annote =	{Keywords: Minimal perfect hashing, Compressed Data Structures}
}
Artifact
Software
DOI: 10.4230/artifacts.22525
OCMu64

Authors: Ragnar Groot Koerkamp and Mees de Vries

Abstract
Cite as

Ragnar Groot Koerkamp, Mees de Vries. OCMu64 (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-22525,
   title = {{OCMu64}}, 
   author = {Groot Koerkamp, Ragnar and de Vries, Mees},
   note = {Software (visited on 2024-12-05)},
   url = {https://github.com/mjdv/ocmu64},
   doi = {10.4230/artifacts.22525},
}
Document
PACE Solver Description
DOI: 10.4230/LIPIcs.IPEC.2024.35
PACE Solver Description: OCMu64, a Solver for One-Sided Crossing Minimization

Authors: Ragnar Groot Koerkamp and Mees de Vries

Published in: LIPIcs, Volume 321, 19th International Symposium on Parameterized and Exact Computation (IPEC 2024)

Abstract
Given a bipartite graph (A,B), the one-sided crossing minimization (OCM) problem is to find an ordering of the vertices of B that minimizes the number of edge crossings when drawn in the plane. We introduce the novel strongly fixed, practically fixed, and practically glued reductions that maximally generalize some existing reductions. We apply these in our exact solver OCMu64, that directly uses branch-and-bound on the ordering of the vertices of B and does not depend on ILP or SAT solvers.
Cite as

Ragnar Groot Koerkamp and Mees de Vries. PACE Solver Description: OCMu64, a Solver for One-Sided Crossing Minimization. In 19th International Symposium on Parameterized and Exact Computation (IPEC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 321, pp. 35:1-35:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{grootkoerkamp_et_al:LIPIcs.IPEC.2024.35,
  author =	{Groot Koerkamp, Ragnar and de Vries, Mees},
  title =	{{PACE Solver Description: OCMu64, a Solver for One-Sided Crossing Minimization}},
  booktitle =	{19th International Symposium on Parameterized and Exact Computation (IPEC 2024)},
  pages =	{35:1--35:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-353-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{321},
  editor =	{Bonnet, \'{E}douard and Rz\k{a}\.{z}ewski, Pawe{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2024.35},
  URN =		{urn:nbn:de:0030-drops-222616},
  doi =		{10.4230/LIPIcs.IPEC.2024.35},
  annote =	{Keywords: Graph drawing, crossing number, branch and bound}
}
Artifact
Software
DOI: 10.4230/artifacts.22510
RagnarGrootKoerkamp/astar-pairwise-aligner

Authors: Ragnar Groot Koerkamp

Abstract
Cite as

Ragnar Groot Koerkamp. RagnarGrootKoerkamp/astar-pairwise-aligner (Software). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-22510,
   title = {{RagnarGrootKoerkamp/astar-pairwise-aligner}}, 
   author = {Groot Koerkamp, Ragnar},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:0da264cc1294d18cb07ee0d76934929e5836e239;origin=https://github.com/RagnarGrootKoerkamp/astar-pairwise-aligner;visit=swh:1:snp:3158598ab43adbfc0661bcb6534fa0cf81397964;anchor=swh:1:rev:d5088352cf2a7474c35b23b046cbda3c4d94c988}{\texttt{swh:1:dir:0da264cc1294d18cb07ee0d76934929e5836e239}} (visited on 2024-11-28)},
   url = {https://github.com/RagnarGrootKoerkamp/astar-pairwise-aligner},
   doi = {10.4230/artifacts.22510},
}
Document
DOI: 10.4230/LIPIcs.WABI.2024.11
The mod-minimizer: A Simple and Efficient Sampling Algorithm for Long k-mers

Authors: Ragnar Groot Koerkamp and Giulio Ermanno Pibiri

Published in: LIPIcs, Volume 312, 24th International Workshop on Algorithms in Bioinformatics (WABI 2024)

Abstract
Motivation. Given a string S, a minimizer scheme is an algorithm defined by a triple (k,w,𝒪) that samples a subset of k-mers (k-long substrings) from a string S. Specifically, it samples the smallest k-mer according to the order 𝒪 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 𝒪 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. Methods. In 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 p of the smallest t-mer in a window. It then samples the k-mer at position pod w. The lr-minimizer uses t = k-w and the mod-minimizer uses t≡ k (mod w). Results. These 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 → ∞. 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.
Cite as

Ragnar Groot Koerkamp and Giulio Ermanno Pibiri. The mod-minimizer: A Simple and Efficient Sampling Algorithm for Long k-mers. In 24th International Workshop on Algorithms in Bioinformatics (WABI 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 312, pp. 11:1-11:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{grootkoerkamp_et_al:LIPIcs.WABI.2024.11,
  author =	{Groot Koerkamp, Ragnar and Pibiri, Giulio Ermanno},
  title =	{{The mod-minimizer: A Simple and Efficient Sampling Algorithm for Long k-mers}},
  booktitle =	{24th International Workshop on Algorithms in Bioinformatics (WABI 2024)},
  pages =	{11:1--11:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-340-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{312},
  editor =	{Pissis, Solon P. and Sung, Wing-Kin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2024.11},
  URN =		{urn:nbn:de:0030-drops-206552},
  doi =		{10.4230/LIPIcs.WABI.2024.11},
  annote =	{Keywords: Minimizers, Randomized algorithms, Sketching, Hashing}
}
Document
DOI: 10.4230/LIPIcs.WABI.2024.17
A*PA2: Up to 19× Faster Exact Global Alignment

Authors: Ragnar Groot Koerkamp

Published in: LIPIcs, Volume 312, 24th International Workshop on Algorithms in Bioinformatics (WABI 2024)

Abstract
Motivation. Pairwise alignment is at the core of computational biology. Most commonly used exact methods are either based on O(ns) band doubling or O(n+s²) diagonal transition, where n is the sequence length and s the number of errors. However, as the length of sequences has grown, these exact methods are often replaced by approximate methods based on e.g. seed-and-extend and heuristics to bound the computed region. We would like to develop an exact method that matches the performance of these approximate methods. Recently, Astarix introduced the A* shortest path algorithm with the seed heuristic for exact sequence-to-graph alignment. A*PA adapted and improved this for pairwise sequence alignment and achieves near-linear runtime when divergence (error rate) is low, at the cost of being very slow when divergence is high. Methods. We 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 Edlib, A*PA2 uses Ukkonen’s band doubling in combination with Myers' bitpacking. A*PA2 1) uses large block sizes inspired by Block Aligner, 2) extends this with SIMD (single instruction, multiple data), 3) introduces a new profile for efficient computations, 4) introduces a new optimistic technique for traceback based on diagonal transition, 5) avoids recomputation of states where possible, and 6) applies the heuristics developed in A*PA and improves them using pre-pruning. Results. With the first 4 engineering optimizations, A*PA2-simple has complexity O(ns) and is 6× to 8× faster than Edlib for sequences ≥ 10 kbp. A*PA2-full also includes the heuristic and is often near-linear in practice for sequences with small divergence. The average runtime of A*PA2 is 19× faster than the exact aligners BiWFA and Edlib on >500 kbp long ONT (Oxford Nanopore Technologies) reads of a human genome having 6% divergence on average. On shorter ONT reads of 11% average divergence the speedup is 5.6× (avg. length 11 kbp) and 0.81× (avg. length 800 bp). On all tested datasets, A*PA2 is competitive with or faster than approximate methods.
Cite as

Ragnar Groot Koerkamp. A*PA2: Up to 19× Faster Exact Global Alignment. In 24th International Workshop on Algorithms in Bioinformatics (WABI 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 312, pp. 17:1-17:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{grootkoerkamp:LIPIcs.WABI.2024.17,
  author =	{Groot Koerkamp, Ragnar},
  title =	{{A*PA2: Up to 19× Faster Exact Global Alignment}},
  booktitle =	{24th International Workshop on Algorithms in Bioinformatics (WABI 2024)},
  pages =	{17:1--17:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-340-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{312},
  editor =	{Pissis, Solon P. and Sung, Wing-Kin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2024.17},
  URN =		{urn:nbn:de:0030-drops-206610},
  doi =		{10.4230/LIPIcs.WABI.2024.17},
  annote =	{Keywords: Edit distance, Pairwise alignment, A*, Shortest path, Dynamic programming}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact