Quantum-effective exact multiple patterns matching algorithms for biological sequences

Kapil Kumar Soni

doi:10.7717/peerj-cs.957

2022-05-12

Kapil Kumar Soni *

Akhtar Rasool

DOI：10.7717/peerj-cs.957

原文链接

查看原文

摘要

En 中文

This article presents efficient quantum solutions for exact multiple pattern matching to process the biological sequences. The classical solution takes O(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)root N) and O((m/C)root 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.

Keyword:

Quantum algorithms

Biological sequences

Grover's quantum search

Quantum memory

Quantum exact multiple pattern matching