  In this study, we explore how quantum pathfinding algorithm called Gaussian
Amplitude Amplification (GAA) can be used to solve the DNA sequencing problem.
To do this, sequencing by hybridization was assumed wherein short fragments of
the nucleic acids called oligonucleotides of length l were gathered and were
then assembled. The process of reassembling the sequence was then abstracted
into a graph problem of finding the Hamiltonian path with the least cost. The
constructed directed graph was then converted into sequential bipartite graphs
in order to use GAA. The results of our simulation revealed that for the case
where l = 2 and spectrum size of |S| = 4, the probability of finding the
optimal solution (with the least cost) is approximately 70.92% - a significant
improvement compared to 4.17% when the path is chosen randomly. While this
study only focused on the ideal scenario where there are no errors in the
spectrum, the outcomes presented here demonstrate the plausibility of using GAA
as a genome sequencing method.
