Quantum implementation of multi-pattern string matching for k-mer detection

Abstract

MotivationThe 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. MethodWe implement two quantum algorithms for DNA multi pattern string matching for k-mer detection based on Grovers amplitude amplification with quantum random access memory (QRAM). The first algorithm uses an enumerate-m oracle that sequentially checks a loaded text substring against all m patterns achieving O({surd}S) query complexity for S text positions but requiring O(m{middle dot}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({surd}S {middle dot} {surd}m) in total. ResultsWe present 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. ConclusionsWhile 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 implementationTo maximize accessibility and practical use, we provide our methodology at: https://github.com/Georgakopoulos-Soares-lab/quantum-multi-motif-finder