Divide-and-conquer quantum algorithm for hybrid <i>de novo</i> genome assembly of short and long reads

Abstract Computational biology holds immense promise as a domain that can leverage quantum advantages due to its involvement in a wide range of challenging computational tasks. Researchers have recently explored the applications of quantum computing in genome assembly implementation. However, the issue of repetitive sequences remains unresolved. In this paper, we propose a hybrid assembly quantum algorithm using high-accuracy short reads and error-prone long reads to deal with sequencing errors and repetitive sequences. The proposed algorithm builds upon the variational quantum eigensolver and utilizes divide-and-conquer strategies to approximate the ground state of larger Hamiltonian while conserving quantum resources. Using simulations of 10-qubit quantum computers, we address problems as large as 140 qubits, yielding optimal assembly results. The convergence speed is significantly improved via the problem-inspired ansatz based on the known information about the assembly problem. Besides, entanglement within quantum circuits is qualitatively verified to notably accelerate the assembly path optimization.