A foundational quantum framework for multi-pattern string matching in k-mer detection
Frontiers in Bioinformatics · 12.06.2026 · 6
DOI: 10.3389/fbinf.2026.1802517 ↗Kurz gefasst
Fachartikel in der Zeitschrift Frontiers in Bioinformatics, online erschienen am 12.06.2026. Verfasst von Christos Papalitsas und 5 weiteren Autor:innen. Beteiligte Einrichtung: Division of Pharmacology and Toxicology, College of Pharmacy, The University of Texas at Austin, Dell Paediatric Research Institute, Austin, TX, Unit…. Die Arbeit nennt 30 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: National Institute of General Medical Sciences.
Abstract (Originalsprache)
Motivation The exponential growth of publicly available genomic data has created unprecedented opportunities for sequence-based discovery. Locating specific k-mers is fundamental to diverse applications, including metagenomic classification, pathogen and cancer detection, and variant calling yet efficient identification of multiple k-mer patterns across large sequencing data and massive databases remains a significant computational challenge.
Method
We implement two quantum algorithms for DNA multi-pattern string matching for k-mer detection, leveraging Grover’s amplitude amplification under the idealized quantum random access memory (QRAM) framework. The first algorithm uses an enumerate-m oracle that sequentially checks a loaded text substring against all m patterns achieving O (√S) query complexity for S text positions but requiring O (m · L) work per oracle call. The second algorithm employs nested Grover search with an outer loop over text positions and an inner loop over pattern space, reducing oracle complexity to O(L) while performing O (√S · √m) in total. These asymptotic gains highlight the potential advantages that could be unlocked by future large-scale, low-noise QRAM architectures, positioning our results as a promising proof-of-concept foundation.
Results
This work introduces two quantum implementations of multi-pattern string matching tailored for k-mer detection. Leveraging quantum parallelism and Grover-inspired search primitives, our methods accelerate dictionary-based pattern matching, particularly in contexts involving large sequences, such as genomic data, and extensive pattern sets.
Conclusion
While implementation challenges such as QRAM overhead remain, this study demonstrates both the promise and current limitations of quantum-enhanced string matching, establishing a foundational step toward quantum readiness in bioinformatics. Availability and Implementation To maximize accessibility and practical use, we provide our methodology at: https://github.com/Georgakopoulos-Soares-lab/quantum-multi-motif-finder .
Schlagwörter
Stichwörter der Autor:innen
Autor:innen und Institutionen
- Division of Pharmacology and Toxicology, College of Pharmacy, The University of Texas at Austin, Dell Paediatric Research Institute, Austin, TX, United States.
Förderung
- National Institute of General Medical Sciences
Zitieren
APA
Papalitsas, C., Mouratidis, I., Patsakis, M., Stogiannos, E., Georgakopoulos-Soares, I., & Koulouras, G. (2026). A foundational quantum framework for multi-pattern string matching in k-mer detection. Frontiers in Bioinformatics, 6. https://doi.org/10.3389/fbinf.2026.1802517
Vancouver
Papalitsas C, Mouratidis I, Patsakis M, Stogiannos E, Georgakopoulos-Soares I, Koulouras G. A foundational quantum framework for multi-pattern string matching in k-mer detection. Frontiers in Bioinformatics. 2026;6. doi:10.3389/fbinf.2026.1802517
BibTeX
@article{Papalitsas2026,
author = {Papalitsas, Christos and Mouratidis, Ioannis and Patsakis, Michail and Stogiannos, Evangelos and Georgakopoulos-Soares, Ilias and Koulouras, Grigorios},
title = {A foundational quantum framework for multi-pattern string matching in k-mer detection},
journal = {Frontiers in Bioinformatics},
year = {2026},
volume = {6},
doi = {10.3389/fbinf.2026.1802517}
}
EUVIMED