Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

ETRI Journal

Quantum‐based exact pattern matching algorithms for biological sequences

Kapil Kumar Soni, Akhtar Rasool

Published May 11, 2021• 13 citations
Publisher

Abstract

In computational biology, desired patterns are searched in large text databases, and an exact match is preferable. Classical benchmark algorithms obtain competent solutions for pattern matching in time, whereas quantum algorithm design is based on Grover's method, which completes the search in time. This paper briefly explains existing quantum algorithms and defines their processing limitations. Our initial work overcomes existing algorithmic constraints by proposing the quantum-based combined exact (QBCE) algorithm for the pattern-matching problem to process exact patterns. Next, quantum random access memory (QRAM) processing is discussed, and based on it, we propose the QRAM processing-based exact (QPBE) pattern-matching algorithm. We show that to find all occurrences of a pattern, the best case time complexities of the QBCE and QPBE algorithms are , and the exceptional worst case is bounded by . Thus, the proposed quantum algorithms achieve computational speedup. Our work is proved mathematically and validated with simulation, and complexity analysis demonstrates that our quantum algorithms are better than existing pattern-matching methods.

DOI
10.4218/etrij.2019-0589

Related papers

Quantum-effective exact multiple patterns matching algorithms for biological sequences

Kapil Kumar Soni, Akhtar Rasool

This article presents efficient quantum solutions for exact multiple pattern matching to process the biological sequences. The classical solution takes Ο ( mN ) time for matching m patterns over N sized text database. The quantum search mechanism is a core for pattern matching, as this reduces time complexity and achieves computational speedup. Few quantum methods are available for multiple pattern matching, which executes search oracle for each pattern in successive iterations. Such solutions are likely acceptable because of classical equivalent quantum designs. However, these methods are constrained with the inclusion of multiplicative factor m in their complexities. An optimal quantum design is to execute multiple search oracle in parallel on the quantum processing unit with a single-core that completely removes the multiplicative factor m , however, this method is impractical to design. We have no effective quantum solutions to process multiple patterns at present. Therefore, we propose quantum algorithms using quantum processing unit with C quantum cores working on shared quantum memory. This quantum parallel design would be effective for searching all t exact occurrences of each pattern. To our knowledge, no attempts have been made to design multiple pattern matching algorithms on quantum multicore processor. Thus, some quantum remarkable exact single pattern matching algorithms are enhanced here with their equivalent versions, namely enhanced quantum memory processing based exact algorithm and enhanced quantum-based combined exact algorithm for multiple pattern matching. Our quantum solutions find all t exact occurrences of each pattern inside the biological sequence in $O((m/C)\sqrt{N})$ and $O((m/C)\sqrt{t})$ time complexities. This article shows the hybrid simulation of quantum algorithms to validate quantum solutions. Our theoretical–experimental results justify the significant improvements that these algorithms outperform over the existing classical solutions and are proven effective in quantum counterparts.

PeerJ Computer Science•May 12, 2022•7 citations

Pattern Matching: A Quantum Oriented Approach

Kapil Kumar Soni, Akhtar Rasool

This article influences the quantum based solutions for traditional pattern matching problem, as the quantum machines can accelerate the computation speed by inherently supporting the parallel executions. The problem identifies solution by suggesting effective algorithms, and as per the classical machines several algorithms are qualified and become criterion for other, importantly noted as Knuth Morris Pratt and Boyer Moore which solves such problem in O(M + N) time. A quantum identical pattern matching algorithms are based upon the principle of high speed Grover's quantum search method which searches an element over unstructured database of "N" elements in O(√N) time. The standard quantum algorithm was proposed by Ramesh and Vinay that could obtain computational speed and provides solution in O(√M + √N) time. We review two already existing quantum based exact and approximate pattern matching algorithms and then by combining the logic of both, a new exact pattern matching algorithm is being proposed which overcomes the algorithmic constraints and substantially proves to be equivalently better than the existing classical and quantum benchmark algorithms. So, this article includes existing and proposed quantum pattern matching algorithms, their flowcharts and examples, mathematical justification over complexity analysis. At last we discuss suitable application domains and further possible variations over the proposed work.

Procedia Computer Science•Jan 1, 2020•16 citations

Classical Equivalent Quantum Based Pattern Matching Algorithms

Kapil Kumar Soni, Akhtar Rasool

The pattern matching problem is imperative in diversified field of computer science, and it finds occurrences of the pattern string(s) of any arbitrary length “M” in the large text string of length “N”. Since past decades the solutions to a problem have been suggesting through efficient algorithms. Classical benchmark algorithms such as Knuth Morris Pratt and Boyer Moore locates such solution in O(N) time, equivalent quantum algorithms can utilize quantum computations which are inherently parallel and obtains computational speedup by providing the solution in O(√N) time. The quantum pattern matching algorithm uses Grover's search logic that finds an element existence in the large unstructured text data of “N” items in O(√N) time, instead classically it takes O(N) time. The article comprises of introductory pattern matching tactics, quantum basics, Grover's search method, quantum based pattern matching algorithms, their illustration followed by complexity analysis, and finally concludes with the possible algorithmic variations and relevant applications.

International Conference on Computing, Communication and Networking Technologies (ICCCNT)•Jul 1, 2019•0 citations

Fast quantum search algorithms in protein sequence comparisons: Quantum bioinformatics

Lloyd C. L. Hollenberg

Quantum search algorithms are considered in the context of protein sequence comparison in bioinformatics. Given a sample protein sequence of length m (i.e., m residues), the problem considered is to find an optimal match in a large database containing N residues. Initially, Grover's quantum search algorithm is applied to a simple illustrative case-namely, where the database forms a complete set of states over the 2(m) basis states of a m qubit register, and thus is known to contain the exact sequence of interest. This example demonstrates explicitly the typical O(square root of [N]) speedup on the classical O(N) requirements. An algorithm is then presented for the (more realistic) case where the database may contain repeat sequences, and may not necessarily contain an exact match to the sample sequence. In terms of minimizing the Hamming distance between the sample sequence and the database subsequences the algorithm finds an optimal alignment, in O(square root of [N]) steps, by employing an extension of Grover's algorithm, due to Boyer et al. for the case when the number of matches is not a priori known.

arXiv:quant-ph/0002076•Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics•Nov 1, 2000•36 citations

Quantum Algorithm for Position Weight Matrix Matching

Koichi Miyamoto, Naoki Yamamoto, Yasubumi Sakakibara

We propose two quantum algorithms for a problem in bioinformatics, position weight matrix (PWM) matching, which aims to find segments (sequence motifs) in a biological sequence such as DNA and protein that have high scores defined by the PWM and are thus of informational importance related to biological function. The two proposed algorithms, the naive iteration method and the Monte-Carlo-based method, output matched segments, given the oracular accesses to the entries in the biological sequence and the PWM. The former uses quantum amplitude amplification (QAA) for sequence motif search, resulting in the query complexity scaling on the sequence lengthn, the sequence motif lengthmand the number of the PWMsKas$O(m\sqrt{Kn})$, which means speedup over existing classical algorithms with respect tonandK. The latter also uses QAA, and further, quantum Monte Carlo integration for segment score calculation, instead of iteratively operating quantum circuits for arithmetic in the naive iteration method; then it provides the additional speedup with respect tomin some situation. As a drawback, these algorithms use quantum random access memories and their initialization takesO(n) time. Nevertheless, our algorithms keep the advantage especially when we search matches in a sequence for many PWMs in parallel.

arXiv:2303.03569•IEEE Transactions on Quantum Engineering•Jan 1, 2023•3 citations

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

Rohit De

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.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 1, 2022•5 citations
In computational biology, desired patterns are searched in large text databases, and an exact match is preferable. Classical benchmark algorithms obtain competent solutions for pattern matching in time, whereas quantum algorithm design is based on Grover's method, which completes the search in time. This paper briefly explains existing quantum algorithms and defines their processing limitations. Our initial work overcomes existing algorithmic constraints by proposing the quantum-based combined exact (QBCE) algorithm for the pattern-matching problem to process exact patterns. Next, quantum random access memory (QRAM) processing is discussed, and based on it, we propose the QRAM processing-based exact (QPBE) pattern-matching algorithm. We show that to find all occurrences of a pattern, the best case time complexities of the QBCE and QPBE algorithms are , and the exceptional worst case is bounded by . Thus, the proposed quantum algorithms achieve computational speedup. Our work is proved mathematically and validated with simulation, and complexity analysis demonstrates that our quantum algorithms are better than existing pattern-matching methods.
This article presents efficient quantum solutions for exact multiple pattern matching to process the biological sequences. The classical solution takes Ο ( mN ) time for matching m patterns over N sized text database. The quantum search mechanism is a core for pattern matching, as this reduces time complexity and achieves computational speedup. Few quantum methods are available for multiple pattern matching, which executes search oracle for each pattern in successive iterations. Such solutions are likely acceptable because of classical equivalent quantum designs. However, these methods are constrained with the inclusion of multiplicative factor m in their complexities. An optimal quantum design is to execute multiple search oracle in parallel on the quantum processing unit with a single-core that completely removes the multiplicative factor m , however, this method is impractical to design. We have no effective quantum solutions to process multiple patterns at present. Therefore, we propose quantum algorithms using quantum processing unit with C quantum cores working on shared quantum memory. This quantum parallel design would be effective for searching all t exact occurrences of each pattern. To our knowledge, no attempts have been made to design multiple pattern matching algorithms on quantum multicore processor. Thus, some quantum remarkable exact single pattern matching algorithms are enhanced here with their equivalent versions, namely enhanced quantum memory processing based exact algorithm and enhanced quantum-based combined exact algorithm for multiple pattern matching. Our quantum solutions find all t exact occurrences of each pattern inside the biological sequence in O((m/C)N)O((m/C)\sqrt{N})O((m/C)N​) and O((m/C)t)O((m/C)\sqrt{t})O((m/C)t​) time complexities. This article shows the hybrid simulation of quantum algorithms to validate quantum solutions. Our theoretical–experimental results justify the significant improvements that these algorithms outperform over the existing classical solutions and are proven effective in quantum counterparts.
This article influences the quantum based solutions for traditional pattern matching problem, as the quantum machines can accelerate the computation speed by inherently supporting the parallel executions. The problem identifies solution by suggesting effective algorithms, and as per the classical machines several algorithms are qualified and become criterion for other, importantly noted as Knuth Morris Pratt and Boyer Moore which solves such problem in O(M + N) time. A quantum identical pattern matching algorithms are based upon the principle of high speed Grover's quantum search method which searches an element over unstructured database of "N" elements in O(√N) time. The standard quantum algorithm was proposed by Ramesh and Vinay that could obtain computational speed and provides solution in O(√M + √N) time. We review two already existing quantum based exact and approximate pattern matching algorithms and then by combining the logic of both, a new exact pattern matching algorithm is being proposed which overcomes the algorithmic constraints and substantially proves to be equivalently better than the existing classical and quantum benchmark algorithms. So, this article includes existing and proposed quantum pattern matching algorithms, their flowcharts and examples, mathematical justification over complexity analysis. At last we discuss suitable application domains and further possible variations over the proposed work.
The pattern matching problem is imperative in diversified field of computer science, and it finds occurrences of the pattern string(s) of any arbitrary length “M” in the large text string of length “N”. Since past decades the solutions to a problem have been suggesting through efficient algorithms. Classical benchmark algorithms such as Knuth Morris Pratt and Boyer Moore locates such solution in O(N) time, equivalent quantum algorithms can utilize quantum computations which are inherently parallel and obtains computational speedup by providing the solution in O(√N) time. The quantum pattern matching algorithm uses Grover's search logic that finds an element existence in the large unstructured text data of “N” items in O(√N) time, instead classically it takes O(N) time. The article comprises of introductory pattern matching tactics, quantum basics, Grover's search method, quantum based pattern matching algorithms, their illustration followed by complexity analysis, and finally concludes with the possible algorithmic variations and relevant applications.
Quantum search algorithms are considered in the context of protein sequence comparison in bioinformatics. Given a sample protein sequence of length m (i.e., m residues), the problem considered is to find an optimal match in a large database containing N residues. Initially, Grover's quantum search algorithm is applied to a simple illustrative case-namely, where the database forms a complete set of states over the 2(m) basis states of a m qubit register, and thus is known to contain the exact sequence of interest. This example demonstrates explicitly the typical O(square root of [N]) speedup on the classical O(N) requirements. An algorithm is then presented for the (more realistic) case where the database may contain repeat sequences, and may not necessarily contain an exact match to the sample sequence. In terms of minimizing the Hamming distance between the sample sequence and the database subsequences the algorithm finds an optimal alignment, in O(square root of [N]) steps, by employing an extension of Grover's algorithm, due to Boyer et al. for the case when the number of matches is not a priori known.
We propose two quantum algorithms for a problem in bioinformatics, position weight matrix (PWM) matching, which aims to find segments (sequence motifs) in a biological sequence such as DNA and protein that have high scores defined by the PWM and are thus of informational importance related to biological function. The two proposed algorithms, the naive iteration method and the Monte-Carlo-based method, output matched segments, given the oracular accesses to the entries in the biological sequence and the PWM. The former uses quantum amplitude amplification (QAA) for sequence motif search, resulting in the query complexity scaling on the sequence lengthn, the sequence motif lengthmand the number of the PWMsKasO(mKn)O(m\sqrt{Kn})O(mKn​), which means speedup over existing classical algorithms with respect tonandK. The latter also uses QAA, and further, quantum Monte Carlo integration for segment score calculation, instead of iteratively operating quantum circuits for arithmetic in the naive iteration method; then it provides the additional speedup with respect tomin some situation. As a drawback, these algorithms use quantum random access memories and their initialization takesO(n) time. Nevertheless, our algorithms keep the advantage especially when we search matches in a sequence for many PWMs in parallel.
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.