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

Hellenic Conference on Artificial Intelligence

Improving the Sequence Alignment Method by Quantum Multi-Pattern Recognition

Konstantinos P. Prousalis, Nikos Konofaos

Published Jul 6, 2018• 14 citations
Publisher

Abstract

A dot matrix approach for sequence alignment is combined with a known quantum multi-pattern recognition method in order to improve the problem of sequence alignment. This dot matrix technique allows the application of some quantum computing principles on the pattern recognition problems like those used in the Grover's algorithm. When the recognized patterns exceed the limit of the 1/3 of the overall patterns, the multi-pattern recognition is accomplished simultaneously with the probability of 100%. The contribution concerns the way that the adopted quantum pattern recognition algorithm is applied speeding up the sequence alignment process. An example application demonstrates the effectiveness of the proposed method. String alignments isn't an essential task only in bioinformatics, but also in calculating the edit distance cost between strings in a natural language or in financial data.

DOI
10.1145/3200947.3201041

Related papers

Α Quantum Pattern Recognition Method for Improving Pairwise Sequence Alignment

Konstantinos P. Prousalis, Nikos Konofaos

Quantum pattern recognition techniques have recently raised attention as potential candidates in analyzing vast amount of data. The necessity to obtain faster ways to process data is imperative where data generation is rapid. The ever-growing size of sequence databases caused by the development of high throughput sequencing is unprecedented. Current alignment methods have blossomed overnight but there is still the need for more efficient methods that preserve accuracy in high levels. In this work, a complex method is proposed to treat the alignment problem better than its classical counterparts by means of quantum computation. The basic principal of the standard dot-plot method is combined with a quantum algorithm, giving insight into the effect of quantum pattern recognition on pairwise alignment. The central feature of quantum algorithmic -quantum parallelism- and the diffraction patterns of x-rays are synthesized to provide a clever array indexing structure on the growing sequence databases. A completely different approach is considered in contrast to contemporary conventional aligners and a variety of competitive classical counterparts are classified and organized in order to compare with the quantum setting. The proposed method seems to exhibit high alignment quality and prevail among the others in terms of time and space complexity.

Scientific Reports•May 10, 2019•33 citations

Quantum Pattern Recognition for Local Sequence Alignment

Konstantinos P. Prousalis, Nikos Konofaos

Over the last two decades, there have been some challenging proposals on the field of pattern recognition by means of quantum technology. The application of them is considered for a popular branch of bioinformatics which analyzes massive amounts of sequence data for genes and proteins. More specific, the Smith-Waterman algorithm is studied under the more general term of local sequence alignment. The steps of this algorithm are totally reformed and powered by the quantum mechanics computing theory. The proposed method is based on R. Schützhold's pattern recognition quantum algorithm. A binary and unstructured data set is formed after the comparison of the sequences under alignment which is used by R. Schützhold's algorithm to identify and locate potential patterns. It is achieved with the aid of a spatial light modulator. The adopted quantum algorithm exhibits an exponential speed-up in comparison with its classical counterparts.

IEEE Globecom Workshops (GC Wkshps)•Dec 1, 2017•2 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

Pattern Recognition of Quantum Information Based on pattern-distance

Daoyi Dong, Daoyi, Chen +3 more

Looking upon every encoding state of quantum information systems as a quantum information pattern, A kind of pattern-distance between different patterns as a measurement of comparability of quantum information patterns is defined, and two kinds of recognition algorithms based on pattern-distance for quantum information are proposed. They can respectively recognize quantum information with known objective pattern and unknown objective pattern. In the two algorithms, the phases and occurrence probabilities of different eigenpatterns of quantum information are sufficiently considered. Two examples demonstrate the feasibility and effectiveness of the two recognition methods. These algorithms point out a new and important path for applications of quantum information and pattern recognition.

Journal of Systems Engineering and Electronics•Jan 1, 2005•2 citations

Derivation of optimal sequence alignment using quantum annealing

Tatsuya AKAMATSU, Hironori Makino

Gene sequence-alignment is an important technique in the research field of bioinformatics, providing a fundamental approach to elucidating the structure and function of organisms and their evolutionary relationships.This method enables the correct assessment of the similarity of gene sequences between organisms.On the other hand, information processing to obtain optimal alignment results is NP-complete problem and requires huge computational resources when processing large sequence data.Quantum computation has the potential to provide an innovative approach to this type of problem.In this paper, we propose an alignment method using quantum annealing, an effective computational technique of quantum computing for combinatorial optimization problems, and report the results of validating its effectiveness on computer simulations.

Journal of Advanced Science•Jan 1, 2025•0 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 Trends•Aug 31, 2024•0 citations
A dot matrix approach for sequence alignment is combined with a known quantum multi-pattern recognition method in order to improve the problem of sequence alignment. This dot matrix technique allows the application of some quantum computing principles on the pattern recognition problems like those used in the Grover's algorithm. When the recognized patterns exceed the limit of the 1/3 of the overall patterns, the multi-pattern recognition is accomplished simultaneously with the probability of 100%. The contribution concerns the way that the adopted quantum pattern recognition algorithm is applied speeding up the sequence alignment process. An example application demonstrates the effectiveness of the proposed method. String alignments isn't an essential task only in bioinformatics, but also in calculating the edit distance cost between strings in a natural language or in financial data.
Quantum pattern recognition techniques have recently raised attention as potential candidates in analyzing vast amount of data. The necessity to obtain faster ways to process data is imperative where data generation is rapid. The ever-growing size of sequence databases caused by the development of high throughput sequencing is unprecedented. Current alignment methods have blossomed overnight but there is still the need for more efficient methods that preserve accuracy in high levels. In this work, a complex method is proposed to treat the alignment problem better than its classical counterparts by means of quantum computation. The basic principal of the standard dot-plot method is combined with a quantum algorithm, giving insight into the effect of quantum pattern recognition on pairwise alignment. The central feature of quantum algorithmic -quantum parallelism- and the diffraction patterns of x-rays are synthesized to provide a clever array indexing structure on the growing sequence databases. A completely different approach is considered in contrast to contemporary conventional aligners and a variety of competitive classical counterparts are classified and organized in order to compare with the quantum setting. The proposed method seems to exhibit high alignment quality and prevail among the others in terms of time and space complexity.
Over the last two decades, there have been some challenging proposals on the field of pattern recognition by means of quantum technology. The application of them is considered for a popular branch of bioinformatics which analyzes massive amounts of sequence data for genes and proteins. More specific, the Smith-Waterman algorithm is studied under the more general term of local sequence alignment. The steps of this algorithm are totally reformed and powered by the quantum mechanics computing theory. The proposed method is based on R. Schützhold's pattern recognition quantum algorithm. A binary and unstructured data set is formed after the comparison of the sequences under alignment which is used by R. Schützhold's algorithm to identify and locate potential patterns. It is achieved with the aid of a spatial light modulator. The adopted quantum algorithm exhibits an exponential speed-up in comparison with its classical counterparts.
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.
Looking upon every encoding state of quantum information systems as a quantum information pattern, A kind of pattern-distance between different patterns as a measurement of comparability of quantum information patterns is defined, and two kinds of recognition algorithms based on pattern-distance for quantum information are proposed. They can respectively recognize quantum information with known objective pattern and unknown objective pattern. In the two algorithms, the phases and occurrence probabilities of different eigenpatterns of quantum information are sufficiently considered. Two examples demonstrate the feasibility and effectiveness of the two recognition methods. These algorithms point out a new and important path for applications of quantum information and pattern recognition.
Gene sequence-alignment is an important technique in the research field of bioinformatics, providing a fundamental approach to elucidating the structure and function of organisms and their evolutionary relationships.This method enables the correct assessment of the similarity of gene sequences between organisms.On the other hand, information processing to obtain optimal alignment results is NP-complete problem and requires huge computational resources when processing large sequence data.Quantum computation has the potential to provide an innovative approach to this type of problem.In this paper, we propose an alignment method using quantum annealing, an effective computational technique of quantum computing for combinatorial optimization problems, and report the results of validating its effectiveness on computer simulations.
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.