  De novo DNA sequence assembly is based on finding paths in overlap graphs,
which is a NP-hard problem. We developed a quantum algorithm for de novo
assembly based on quantum walks in graphs. The overlap graph is partitioned
repeatedly to smaller graphs that form a hierarchical structure. We use quantum
walks to find paths in low rank graphs and a quantum algorithm that finds
Hamiltonian paths in high hierarchical rank. We tested the partitioning quantum
algorithm, as well as the quantum algorithm that finds Hamiltonian paths in
high hierarchical rank and confirmed its correct operation using Qiskit. We
developed a custom simulation for quantum walks to search for paths in low rank
graphs. The approach described in this paper may serve as a basis for the
development of efficient quantum algorithms that solve the de novo DNA assembly
problem.
