EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

A foundational quantum framework for multi-pattern string matching in k-mer detection

Christos Papalitsas, Ioannis Mouratidis, Michail Patsakis, Evangelos Stogiannos, Ilias Georgakopoulos-Soares, Grigorios Koulouras

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.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

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

QRAMgrover algorithmk-mer algorithmquantum bioinformaticsquantum string matching

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}
}
Kostenlos starten →