Divide-and-Conquer Quantum Algorithm for Hybrid de novo Genome Assembly of Short and Long Reads

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 ten-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 based on the known information about the assembly problem. In addition, we qualitatively verify that entanglement within quantum circuits may accelerate the assembly path optimization. Published by the American Physical Society 2024