Quantum implementation of multi-pattern string matching for 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 computational challenge.

Purpose of the Study:

• To develop and present quantum algorithms for DNA multi-pattern string matching for k-mer detection.
• To accelerate dictionary-based pattern matching in large genomic sequences.

Main Methods:

• Implementation of two quantum algorithms based on Grover's amplitude amplification and quantum random access memory (QRAM).
• Algorithm 1: Enumerate-m oracle achieving O(√S) query complexity.
• Algorithm 2: Nested Grover search achieving O(√S · √m) total complexity.

Main Results:

• Demonstration of two quantum implementations for multi-pattern string matching tailored for k-mer detection.
• Acceleration of pattern matching using quantum parallelism and Grover-inspired search primitives.
• Identification of promise and limitations of quantum-enhanced string matching.

Conclusions:

• Quantum algorithms show promise for accelerating k-mer detection in bioinformatics.
• Implementation challenges like QRAM overhead need further research.
• This work is a foundational step towards quantum readiness in bioinformatics.