  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.
