IEEE International Conference on Quantum Computing and Engineering (QCE)

Quantum Accelerated Pattern Matching for Genome Sequencing in Complex RNA Secondary Structures

Rohit De

Published Sep 1, 2022• 5 citations

Abstract

Sequence matching in genomics can be approached by quantum computing through Grover’s algorithm offering a quadratic speed-up versus the fastest classical algorithms. Previous research using quantum computing focused on long DNA sequences, but application to complex RNA secondary structures with hairpin, bulge, ring, and stem forms has not been possible. This paper developed new formulations for RNA structures using quantum pattern recognition and quantum Hamming distance on Grover’s framework by extracting linear regions from the complex forms. To best leverage the quantum speedup, methods are developed to create long sequences by concatenating different linearized parts of the complex RNA structures. The mechanism is simulated on IBM’s Qiskit quantum simulator using RNA examples from GenBank and mirBase. Comparisons of the iteration complexity indeed shows the potential for quadratic speedups from quantum computing versus classical. Simulation results also show that search accuracy is very good when using the quantum pattern recognition method.

DOI: 10.1109/qce53715.2022.00139

Related papers

An algorithm for DNA read alignment on quantum accelerators

Aritra Sarkar, Zaid Al-Ars, Carmen G. Almudéver +1 more

With small-scale quantum processors transitioning from experimental physics labs to industrial products, these processors allow us to efficiently compute important algorithms in various fields. In this paper, we propose a quantum algorithm to address the challenging field of big data processing for genome sequence reconstruction. This research describes an architecture-aware implementation of a quantum algorithm for sub-sequence alignment. A new algorithm named QiBAM (quantum indexed bidirectional associative memory) is proposed, that uses approximate pattern-matching based on Hamming distances. QiBAM extends the Grover's search algorithm in two ways to allow for: (1) approximate matches needed for read errors in genomics, and (2) a distributed search for multiple solutions over the quantum encoding of DNA sequences. This approach gives a quadratic speedup over the classical algorithm. A full implementation of the algorithm is provided and verified using the OpenQL compiler and QX simulator framework. This represents a first exploration towards a full-stack quantum accelerated genome sequencing pipeline design. The open-source implementation can be found on https://github.com/prince-ph0en1x/QAGS.

arXiv:1909.05563Sep 12, 201915 citations

Convergence of Bioinformatics and Quantum Computing: A Novel Framework for Genome Sequencing Acceleration

Jun‐Han Huang, Fabrizio Falchi, Eneko Osaba

The exponential growth of genomic data presents significant computational challenges in the field of bioinformatics, particularly in genome sequencing. Traditional methods struggle to meet the increasing demand for speed, accuracy, and efficiency. This paper introduces a novel framework that leverages quantum computing to accelerate genome sequencing processes. The proposed framework integrates quantum algorithms, such as Grover's search and quantum Fourier transform, with classical bioinformatics techniques to optimize key tasks, including sequence alignment, variant detection, and large-scale data analysis. By exploiting the inherent parallelism and computational power of quantum systems, the framework achieves substantial reductions in processing time while maintaining high accuracy. A case study on large-scale genomic datasets demonstrates the framework's ability to outperform state-of-the-art classical approaches, particularly in handling complex and large-scale sequencing tasks. Furthermore, this research highlights the potential of quantum computing in advancing bioinformatics, paving the way for more efficient and scalable solutions to address the computational bottlenecks of modern genomics. The implications of this interdisciplinary approach extend beyond genomics, offering transformative possibilities in data-driven life sciences.

International Journal of Computer Engineering in Research TrendsAug 31, 20240 citations

RNA folding using quantum computers

Dillion M. Fox, Christopher M. MacDermaid, Andrea M. A. Schreij +2 more

The 3-dimensional fold of an RNA molecule is largely determined by patterns of intramolecular hydrogen bonds between bases. Predicting the base pairing network from the sequence, also referred to as RNA secondary structure prediction or RNA folding, is a nondeterministic polynomial-time (NP)-complete computational problem. The structure of the molecule is strongly predictive of its functions and biochemical properties, and therefore the ability to accurately predict the structure is a crucial tool for biochemists. Many methods have been proposed to efficiently sample possible secondary structure patterns. Classic approaches employ dynamic programming, and recent studies have explored approaches inspired by evolutionary and machine learning algorithms. This work demonstrates leveraging quantum computing hardware to predict the secondary structure of RNA. A Hamiltonian written in the form of a Binary Quadratic Model (BQM) is derived to drive the system toward maximizing the number of consecutive base pairs while jointly maximizing the average length of the stems. A Quantum Annealer (QA) is compared to a Replica Exchange Monte Carlo (REMC) algorithm programmed with the same objective function, with the QA being shown to be highly competitive at rapidly identifying low energy solutions. The method proposed in this study was compared to three algorithms from literature and, despite its simplicity, was found to be competitive on a test set containing known structures with pseudoknots.

PLoS Computational BiologyApr 11, 202233 citations

Quantum Algorithms: for pattern-matching in genomic sequences

Aritra Sarkar

Fast sequencing and analysis of (microorganism, plant or human) genomes will open up new vistas in fields like personalised medication, food yield and epigenetic research. Current state-of-the-art DNA pattern matching techniques use heuristic algorithms on computing clusters of CPUs, GPUs and FPGAs. With genomic data set to eclipse social and astronomical big data streams within a decade, the alternate computing paradigm of quantum computation is explored to accelerate genome-sequence reconstruction. The inherent parallelism of quantum superposition of states is harnessed to design a quantum kernel for accelerating the search process. The project explores the merger of these two domains and identifies ways to fit these together to design a genome-sequence analysis pipeline with quantum algorithmic speedup. The design of a genome-sequence analysis pipeline with a quantum kernel is tested with a proof-of-concept demonstration using a quantum simulator.

Jan 1, 20189 citations

A novel quantum algorithm for Biological Sequence Alignment using Quantum Accelerated Mapping in Seed-and-Extend Technique.

Konstantinos P. Prousalis, Dimitris Ntalaperas, Konstantinos Georgiou +6 more

Abstract A novel quantum algorithm for use in Biological Sequence Alignment is presented and analyzed. The large amounts of data extracted from genome sequencing, de novo assembly sequencing, resequencing, and transcriptome sequencing at the DNA or RNA level, foreshadow the need for higher computing power as well as more sophisticated alignment methods. Modern and faster sequencing techniques in genomics have led to the reconsideration of current methods of designing or implementing alignment protocols. Novel quantum computing accelerators may provide drastic solutions in this field reaching the desired levels of gate operation maturity. This paper proposes a computer vision-based approach, using the unprecedented power of entanglement in a dot-matrix, to address the high demand for fast harnessing of biological data. A quantum accelerated protocol is demonstrated and tested using the Qiskit software framework of IBM. Runtime tests verify the expectations to obtain a potentially advantageous sequence alignment algorithmic process in terms of accuracy, completeness and computing complexity. The performance has been tested under various conditions and promises a clear and viable advantage.

May 3, 20240 citations

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

Christos Papalitsas, Ioannis Mouratidis, Michail Patsakis +3 more

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 based on Grover's 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(√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. Results: We 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. Conclusions: 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.

Dec 23, 20250 citations