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 Ansatz 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.

Figure 1

Schematic overview of the quantum algorithm for hybrid de novo genome assembly. The short reads are used to construct the de Bruijn graphs, while the long reads are used to provide long-range linking between nodes. Here the nodes represent $k$-mers and the red ones mean low-frequency $k$-mers from sequencing errors. Connections between nodes are based on the common $k-1$ suffix and prefix. Inevitable path conflicts are caused by sequencing errors or repetitive sequences. The short-read and long-read data are encoded together into a optimization model solvable on a quantum device. The results are then decoded to obtain the assembly sequences.

Figure 2

Schematic diagram of the toy model. Both short-read and long-read sequencing data are used, where the red characters represent sequencing errors. To optimize qubit utilization and streamline the model, a strategy is implemented where three consecutive $k$-mers are consolidated into a single node. The nodes in the red dotted circle are low-frequency $k$-mers from sequencing errors. The connection of the nodes is established based on the shared $k-1$ suffix and prefix. The nodes $n_2$ and $n_3$ represent repeat regions and the node $n_5$ represents sequencing errors. The toy model is input into a quantum computer for simulation, resulting in the generation of the final quantum state of the binary string $|\mathrm{\Psi }\rangle$. The optimal assembly sequence is then obtained through the process of decoding the binary string.

Figure 3

Variational Ansätze for the VQE algorithm. (a) HEA1 implemented by $R_y, R_z$, and cz gates. (b) HEA2 implemented by $R_y$ and $R_z$ gates. The quantum circuits in the dashed boxes repeat $D_e$ times. (c) Problem-inspired Ansatz based on the assembly problem (Sec. 4).

Figure 4

Simulation results of HEA. Convergence of (a) HEA1 and (b) HEA2 is shown with 100 sets of random initial parameters. (c) Comparison of the average convergence between HEA1 and HEA2.

Figure 5

Simulation results of the problem-inspired Ansatz. (a) Evaluation value for 100 groups of random initial parameters with the problem-inspired Ansatz. (b) Comparison of the average convergence of HEA1, HEA2, and the problem-inspired Ansatz.

Figure 6

The de Bruijn graphs for five different sizes of assembly problems, from six nodes to ten nodes, calculated by the problem-inspired Ansatz.

Figure 7

Simulation results of the problem-inspired Ansatz for five different problem sizes. (a) Average convergence of different problem sizes. (b) Iteration number for convergence and the number of experiments required to find the optimal assembly results with a probability of $99\%$, called $R_{99}$.

Figure 8

Scheme of the VQE method. The VQE is a hybrid quantum-classical algorithm, where quantum processing units are used to prepare the trial wave function by parametrized quantum circuits and measure the corresponding expectation value of the Hamiltonian and classical processing units are used to update the parameters.

Figure 9

Schematic diagram of the toy model with four nodes.

Figure 10

Schematic of the problem-inspired Ansatz for preparing the $n$-qubit wave function $|{\psi }^{\left(p\right)}\left(\vec{\theta }\right)\rangle$. (a) Problem-inspired Ansatz implemented by $R_x\left({\theta }_0\right), U_{cq,tq}\left({\theta }_j\right)$, and cnot gates. (b) Implementation of the $U_{cq,tq}\left({\theta }_j\right)$ gate using $R_y\left({\theta }_j\right)$, cz, and $R_y({\theta }_j+\pi )$ gates. (c) Quantum circuit for the three-qubit wave function.