Search Results

Documents authored by Martayan, Igor

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},
}
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.WABI.2023.15
Fractional Hitting Sets for Efficient and Lightweight Genomic Data Sketching

Authors: Timothé Rouzé, Igor Martayan, Camille Marchet, and Antoine Limasset

Published in: LIPIcs, Volume 273, 23rd International Workshop on Algorithms in Bioinformatics (WABI 2023)

Abstract
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 resource-efficient, 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.
Cite as

Timothé Rouzé, Igor Martayan, Camille Marchet, and Antoine Limasset. Fractional Hitting Sets for Efficient and Lightweight Genomic Data Sketching. In 23rd International Workshop on Algorithms in Bioinformatics (WABI 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 273, pp. 15:1-15:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{rouze_et_al:LIPIcs.WABI.2023.15,
  author =	{Rouz\'{e}, Timoth\'{e} and Martayan, Igor and Marchet, Camille and Limasset, Antoine},
  title =	{{Fractional Hitting Sets for Efficient and Lightweight Genomic Data Sketching}},
  booktitle =	{23rd International Workshop on Algorithms in Bioinformatics (WABI 2023)},
  pages =	{15:1--15:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-294-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{273},
  editor =	{Belazzougui, Djamal and Ouangraoua, A\"{i}da},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2023.15},
  URN =		{urn:nbn:de:0030-drops-186414},
  doi =		{10.4230/LIPIcs.WABI.2023.15},
  annote =	{Keywords: k-mer, subsampling, sketching, Jaccard, containment, metagenomics}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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