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

Area of Science:

• Bioinformatics
• Quantum Computing
• Computational Biology

Background:

• Genomic data is growing exponentially, creating opportunities for sequence-based discovery.
• Efficiently identifying multiple k-mer patterns in large datasets is a significant computational challenge.

Purpose of the Study:

• To introduce two quantum algorithms for DNA multi-pattern string matching for k-mer detection.
• To leverage quantum parallelism and Grover-inspired search primitives to accelerate pattern matching.

Main Methods:

• Implementation of two quantum algorithms using Grover's amplitude amplification and an idealized quantum random access memory (QRAM).
• Algorithm 1: Enumerate-m oracle with O(√S) query complexity and O(m·L) work per call.
• Algorithm 2: Nested Grover search with O(√S · √m) total complexity and O(L) oracle complexity.

Main Results:

• Demonstrated acceleration of dictionary-based pattern matching for k-mer detection.
• Achieved asymptotic gains in query complexity compared to classical methods.
• Provided a proof-of-concept for quantum-enhanced string matching in bioinformatics.

Conclusions:

• The study highlights the potential advantages of large-scale, low-noise QRAM architectures.
• Acknowledges implementation challenges like QRAM overhead.
• Establishes a foundational step toward quantum readiness in bioinformatics.