DROPS

Document

DOI: 10.4230/LIPIcs.WABI.2026.14

Quik 2.0: Efficient Large-Scale DNA Barcode Calling

Authors: Steffen Schüler, Antonia Schmidt, and Matthias Müller-Hannemann

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

Abstract

DNA barcodes are used as unique identifiers in high-throughput sequencing technologies with applications in areas such as single cell analysis, spatial transcriptomics and DNA data storage. Given a set of barcodes and a set of reads, each containing a barcode, the task of barcode calling is to assign each read to its respective barcode. This is challenging in applications involving large barcode sets and high rates of base insertion, deletion and substitution errors. Naive solutions require the calculation of pairwise distances between each barcode and read. As this is infeasible for modern applications with millions of barcodes and billions of reads, much work has been done during the previous years in accelerating this task. In 2026, Uphoff et al. introduced the barcode calling tool Quik based on k-mer filtering and pseudo-distances. They demonstrated that it is faster than state-of-the-art tools by several orders of magnitude. Here, we present Quik 2.0, which is faster than the original release by a factor of up to 56 and scales well to multiple GPUs. We discuss several algorithmic design choices that led to this speedup. In large-scale experiments with 10⁶ barcodes, we can now process approximately 300 million reads per hour on a GPU server equipped with four GPUs. In addition, we show that unfiltered barcode calling approaches can only slightly improve the accuracy at the cost of a vastly increased running time. Finally, we introduce more fine-grained assignment rejection criteria to achieve a better trade-off between precision and acceptance rate. To help users select suitable rejection parameters for real-world experiments, we propose an automatic calibration procedure that optimizes parameters for specific barcode and read sets.

Cite as

Steffen Schüler, Antonia Schmidt, and Matthias Müller-Hannemann. Quik 2.0: Efficient Large-Scale DNA Barcode Calling. In 26th International Conference on Algorithms for Bioinformatics (WABI 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 390, pp. 14:1-14:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{schuler_et_al:LIPIcs.WABI.2026.14,
  author =	{Sch\"{u}ler, Steffen and Schmidt, Antonia and M\"{u}ller-Hannemann, Matthias},
  title =	{{Quik 2.0: Efficient Large-Scale DNA Barcode Calling}},
  booktitle =	{26th International Conference on Algorithms for Bioinformatics (WABI 2026)},
  pages =	{14:1--14:19},
  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.14},
  URN =		{urn:nbn:de:0030-drops-275185},
  doi =		{10.4230/LIPIcs.WABI.2026.14},
  annote =	{Keywords: DNA barcode calling, k-mer filtering, GPU computing, algorithm engineering, spatial transcriptomics}
}

Document

DOI: 10.4230/LIPIcs.SEA.2024.17

Barcode Selection and Layout Optimization in Spatial Transcriptomics

Authors: Frederik L. Jatzkowski, Antonia Schmidt, Robert Mank, Steffen Schüler, and Matthias Müller-Hannemann

Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)

Abstract

An important special case of the quadratic assignment problem arises in the synthesis of DNA microarrays for high-resolution spatial transcriptomics. The task is to select a suitable subset from a set of barcodes, i. e. short DNA strings that serve as unique identifiers, and to assign the selected barcodes to positions on a two-dimensional array in such a way that a position-dependent cost function is minimized. A typical microarray with dimensions of 768×1024 requires 786,432 many barcodes to be placed, leading to very challenging large-scale combinatorial optimization problems. The general quadratic assignment problem is well-known for its hardness, both in theory and in practice. It turns out that this also holds for the special case of the barcode layout problem. We show that the problem is even hard to approximate: It is MaxSNP-hard. An ILP formulation theoretically allows the computation of optimal results, but it is only applicable for tiny instances. Therefore, we have developed layout constructing and improving heuristics with the aim of computing near-optimal solutions for instances of realistic size. These include a sorting-based algorithm, a greedy algorithm, 2-OPT-based local search and a genetic algorithm. To assess the quality of the results, we compare the generated solutions with the expected cost of a random layout and with lower bounds. A combination of the greedy algorithm and 2-OPT local search produces the most promising results in terms of both quality and runtime. Solutions to large-scale instances with arrays of dimension 768×1024 show a 37% reduction in cost over a random solution and can be computed in about 3 minutes. Since the universe of suitable barcodes is much larger than the number of barcodes needed, this can be exploited. Experiments with different surpluses of barcodes show that a significant improvement in layout quality can be achieved at the cost of a reasonable increase in runtime. Another interesting finding is that the restriction of the barcode design space by biochemical constraints is actually beneficial for the overall layout cost.

Cite as

Frederik L. Jatzkowski, Antonia Schmidt, Robert Mank, Steffen Schüler, and Matthias Müller-Hannemann. Barcode Selection and Layout Optimization in Spatial Transcriptomics. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 17:1-17:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{jatzkowski_et_al:LIPIcs.SEA.2024.17,
  author =	{Jatzkowski, Frederik L. and Schmidt, Antonia and Mank, Robert and Sch\"{u}ler, Steffen and M\"{u}ller-Hannemann, Matthias},
  title =	{{Barcode Selection and Layout Optimization in Spatial Transcriptomics}},
  booktitle =	{22nd International Symposium on Experimental Algorithms (SEA 2024)},
  pages =	{17:1--17:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-325-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{301},
  editor =	{Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.17},
  URN =		{urn:nbn:de:0030-drops-203821},
  doi =		{10.4230/LIPIcs.SEA.2024.17},
  annote =	{Keywords: Spatial Transcriptomics, Array Layout, Optimization, Computational Complexity, GPU Computing, Integer Linear Programming, Metaheuristics}
}

Search Results

Documents authored by Schüler, Steffen

Quik 2.0: Efficient Large-Scale DNA Barcode Calling

Abstract

Cite as

Barcode Selection and Layout Optimization in Spatial Transcriptomics

Abstract

Cite as

Thanks for your feedback!

Could not send message