Academic Journal
Barcode Selection and Layout Optimization in Spatial Transcriptomics
| العنوان: | Barcode Selection and Layout Optimization in Spatial Transcriptomics |
|---|---|
| المؤلفون: | Jatzkowski, Frederik L., Schmidt, Antonia, Mank, Robert, Schüler, Steffen, Müller-Hannemann, Matthias |
| المساهمون: | Frederik L. Jatzkowski and Antonia Schmidt and Robert Mank and Steffen Schüler and Matthias Müller-Hannemann |
| بيانات النشر: | Schloss Dagstuhl – Leibniz-Zentrum für Informatik |
| سنة النشر: | 2024 |
| المجموعة: | DROPS - Dagstuhl Research Online Publication Server (Schloss Dagstuhl - Leibniz Center for Informatics ) |
| مصطلحات موضوعية: | Spatial Transcriptomics, Array Layout, Optimization, Computational Complexity, GPU Computing, Integer Linear Programming, Metaheuristics |
| الوصف: | 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 ... |
| نوع الوثيقة: | article in journal/newspaper conference object |
| وصف الملف: | application/pdf |
| اللغة: | English |
| Relation: | Is Part Of LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024); https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.17 |
| DOI: | 10.4230/LIPIcs.SEA.2024.17 |
| الاتاحة: | https://doi.org/10.4230/LIPIcs.SEA.2024.17 https://nbn-resolving.org/urn:nbn:de:0030-drops-203821 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.17 |
| Rights: | https://creativecommons.org/licenses/by/4.0/legalcode |
| رقم الانضمام: | edsbas.3D33E301 |
| قاعدة البيانات: | BASE |
| DOI: | 10.4230/LIPIcs.SEA.2024.17 |
|---|