Abstract The difficult computational task of de novo genome assembly is to piece together the original DNA sequence from a collection of overlapping pieces. The issue can be expressed as an NP-hard quadratic unconstrained binary optimization (QUBO) problem. To solve QUBO problems more effectively than conventional techniques, quantum computing presents a viable alternative. This is because quantum annealers and gate-based quantum algorithms may take advantage of quantum effects like superposition and entanglement. But there are drawbacks to quantum computing as well, such scalability, noise, and decoherence. In this work, we present a hybrid quantum-classical optimization algorithm that solves the QUBO problem of de novo genome assembly by utilizing the advantages of both paradigms. To find near-optimal solutions in the presence of defects and noise, our technique combines a classical local search heuristic with a quantum approximate optimization algorithm (QAOA). We assess our algorithm's performance against current quantum and conventional approaches using both artificial and actual data sets. We demonstrate that our algorithm can outperform the state-of-the-art methods in terms of accuracy and computing cost, and it has the potential to solve intricate and large-scale genome assembly challenges.
Abstract The difficult computational task of de novo genome assembly is to piece together the original DNA sequence from a collection of overlapping pieces. The issue can be expressed as an NP-hard quadratic unconstrained binary optimization (QUBO) problem. To solve QUBO problems more effectively than conventional techniques, quantum computing presents a viable alternative. This is because quantum annealers and gate-based quantum algorithms may take advantage of quantum effects like superposition and entanglement. But there are drawbacks to quantum computing as well, such scalability, noise, and decoherence. In this work, we present a hybrid quantum-classical optimization algorithm that solves the QUBO problem of de novo genome assembly by utilizing the advantages of both paradigms. To find near-optimal solutions in the presence of defects and noise, our technique combines a classical local search heuristic with a quantum approximate optimization algorithm (QAOA). We assess our algorithm's performance against current quantum and conventional approaches using both artificial and actual data sets. We demonstrate that our algorithm can outperform the state-of-the-art methods in terms of accuracy and computing cost, and it has the potential to solve intricate and large-scale genome assembly challenges.
Genome sequencing is essential to decode genetic information, identify organisms, understand diseases and advance personalized medicine. A critical step in any genome sequencing technique is genome assembly. However, de novo genome assembly, which involves constructing an entire genome sequence from scratch without a reference genome, presents significant challenges due to its high computational complexity, affecting both time and accuracy. In this study, we propose a hybrid approach utilizing a quantum computing-based optimization algorithm integrated with classical pre-processing to expedite the genome assembly process. Specifically, we present a method to solve the Hamiltonian and Eulerian paths within the genome assembly graph using gate-based quantum computing through a Higher-Order Binary Optimization (HOBO) formulation with the Variational Quantum Eigensolver algorithm (VQE), in addition to a novel bitstring recovery mechanism to improve optimizer traversal of the solution space. A comparative analysis with classical optimization techniques was performed to assess the effectiveness of our quantum-based approach in genome assembly. The results indicate that, as quantum hardware continues to evolve and noise levels diminish, our formulation holds a significant potential to accelerate genome sequencing by offering faster and more accurate solutions to the complex challenges in genomic research.
Recent advances in DNA sequencing open prospects to make whole-genome analysis rapid and reliable, which is promising for various applications including personalized medicine. However, existing techniques for de novo genome assembly, which is used for the analysis of genomic rearrangements, chromosome phasing, and reconstructing genomes without a reference, require solving tasks of high computational complexity. Here we demonstrate a method for solving genome assembly tasks with the use of quantum and quantum-inspired optimization techniques. Within this method, we present experimental results on genome assembly using quantum annealers both for simulated data and the [Formula: see text]X 174 bacteriophage. Our results pave a way for a significant increase in the efficiency of solving bioinformatics problems with the use of quantum computing technologies and, in particular, quantum annealing might be an effective method. We expect that the new generation of quantum annealing devices would outperform existing techniques for de novo genome assembly. To the best of our knowledge, this is the first experimental study of de novo genome assembly problems both for real and synthetic data on quantum annealing devices and quantum-inspired techniques.
BACKGROUND: The assembly task is an indispensable step in sequencing genomes of new organisms and studying structural genomic changes. In recent years, the dynamic development of next-generation sequencing (NGS) methods raises hopes for making whole-genome sequencing a fast and reliable tool used, for example, in medical diagnostics. However, this is hampered by the slowness and computational requirements of the current processing algorithms, which raises the need to develop more efficient algorithms. One possible approach, still little explored, is the use of quantum computing. RESULTS: We present a proof of concept of de novo assembly algorithm, using the Genomic Signal Processing approach, detecting overlaps between DNA reads by calculating the Pearson correlation coefficient and formulating the assembly problem as an optimization task (Traveling Salesman Problem). Computations performed on a classic computer were compared with the results achieved by a hybrid method combining CPU and QPU calculations. For this purpose quantum annealer by D-Wave was used. The experiments were performed with artificially generated data and DNA reads coming from a simulator, with actual organism genomes used as input sequences. To our knowledge, this work is one of the few where actual sequences of organisms were used to study the de novo assembly task on quantum annealer. CONCLUSIONS: Proof of concept carried out by us showed that the use of quantum annealer (QA) for the de novo assembly task might be a promising alternative to the computations performed in the classical model. The current computing power of the available devices requires a hybrid approach (combining CPU and QPU computations). The next step may be developing a hybrid algorithm strictly dedicated to the de novo assembly task, using its specificity (e.g. the sparsity and bounded degree of the overlap-layout-consensus graph).
Reconstructing DNA sequences without a reference, known as de novo assembly, is a complex computational task involving the alignment of overlapping fragments. To address this problem, a usual strategy is to map the assembly to a Quadratic Unconstrained Binary Optimization (QUBO) formulation, which can be solved by different quantum algorithms. In this work, we focus on three versions of the Feedback-based Algorithm, a protocol that eliminates classical optimization loops via measurement feedback. We analyze long-read DNA fragments from SARS-CoV-2 and human mitochondrial DNA using standard FALQON, second-order FALQON (SO-FALQON), and time-rescaled FALQON (TR-FALQON). Numerical results show that both variants improve convergence to the ground state and increase success probabilities at reduced circuit depths. These findings indicate that enhanced feedback-driven dynamics are effective for solving combinatorial problems on near-term quantum hardware.
Metagenomic analysis of the 'microbial dark matter'-the vast majority of microorganisms lacking reference genomes-depends critically on de novo assembly methods. These approaches enable genome reconstruction directly from sequencing data without prior genomic knowledge, revealing previously unknown microbial diversity. Here, we introduce a graph transformation algorithm that converts bidirected compressed De Bruijn genomic graphs into directed graphs, then formulate the de novo assembly challenge as a Quadratic Unconstrained Binary Optimization (QUBO) problem addressable through the Quantum Approximate Optimization Algorithm (QAOA). Computational exploration was conducted on the Eviden Qaptiva 800 emulator using real-world viral data. Our analysis reveals that while QAOA successfully identifies valid assembly paths in small-scale instances, qubit requirements scale linearly with graph edge counts, presenting a bottleneck for larger bacterial genomes. To address this scalability issue, we propose a graph decomposition strategy to break down large assembly graphs into manageable subgraphs. This study establishes a proof-of-concept for quantum-enhanced de novo assembly, exploring the capabilities of QAOA against classical solvers and highlighting a path toward quantum-driven de novo assembly.
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.