Search Results

Documents authored by Marchet, Camille

Artifact
Software
DOI: 10.4230/artifacts.27674
LoreDepuydt/sbwt-set-operations

Authors: Jarno N. Alanko, Lore Depuydt, Camille Marchet, and Simon J. Puglisi

Abstract
Cite as

Jarno N. Alanko, Lore Depuydt, Camille Marchet, Simon J. Puglisi. LoreDepuydt/sbwt-set-operations (Software). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-27674,
   title = {{LoreDepuydt/sbwt-set-operations}}, 
   author = {Alanko, Jarno N. and Depuydt, Lore and Marchet, Camille and Puglisi, Simon J.},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:de3c949dbd910f97f6af25f8be4838be2fbe4dfb;origin=https://github.com/LoreDepuydt/sbwt-set-operations;visit=swh:1:snp:eceff5e98e31e77ceeede627ef8a88598b05a4fd;anchor=swh:1:rev:0a3c2d30767c7cf91900393445e9bc658194f696}{\texttt{swh:1:dir:de3c949dbd910f97f6af25f8be4838be2fbe4dfb}} (visited on 2026-08-27)},
   url = {https://github.com/LoreDepuydt/sbwt-set-operations},
   doi = {10.4230/artifacts.27674},
}
Document
DOI: 10.4230/LIPIcs.WABI.2026.18
Fast Set Operations for Compact k-mer Sets

Authors: Jarno N. Alanko, Lore Depuydt, Camille Marchet, and Simon J. Puglisi

Published in: LIPIcs, Volume 390, 26th International Conference on Algorithms for Bioinformatics (WABI 2026)

Abstract
The k-mer spectrum of a set of sequences is the set of k-length substrings the sequences contain. This lossy representation of sequence content pervades modern genomics. Recently, the spectral Burrows-Wheeler transform (SBWT) has emerged as a space-efficient representation of k-spectra that also supports efficient k-mer lookup queries and, more generally, easy navigation of the de Bruijn graph of the k-spectrum. In this paper, we examine primitive set operations, such as intersection, union, and set difference, on SBWT-encoded k-spectra and show that these operations can be supported efficiently. Moreover, efficient merging leads directly to a new memory-efficient algorithm for SBWT construction, which was able to build the SBWT for the 661K bacterial dataset containing 88 billion distinct k-mers in 50 hours using 186 GiB of RAM and 112 GiB of disk space. Given the pervasiveness of k-mer sets in genomics and the continued rapid growth of genomic databases, our work opens the door to a wide array of future applications that manipulate and reason about genomic data by dealing directly with simultaneously compact and searchable k-mer set representations offered by the SBWT.
Cite as

Jarno N. Alanko, Lore Depuydt, Camille Marchet, and Simon J. Puglisi. Fast Set Operations for Compact k-mer Sets. In 26th International Conference on Algorithms for Bioinformatics (WABI 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 390, pp. 18:1-18:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{alanko_et_al:LIPIcs.WABI.2026.18,
  author =	{Alanko, Jarno N. and Depuydt, Lore and Marchet, Camille and Puglisi, Simon J.},
  title =	{{Fast Set Operations for Compact k-mer Sets}},
  booktitle =	{26th International Conference on Algorithms for Bioinformatics (WABI 2026)},
  pages =	{18:1--18:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-446-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{390},
  editor =	{El-Mabrouk, Nadia and Vandin, Fabio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2026.18},
  URN =		{urn:nbn:de:0030-drops-275220},
  doi =		{10.4230/LIPIcs.WABI.2026.18},
  annote =	{Keywords: Data Structures, efficient Algorithms}
}
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}
}

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