BMC Bioinformatics

Algorithm for DNA sequence assembly by quantum annealing

Katarzyna Nałęcz-Charkiewicz, Robert Marek Nowak

Published Apr 7, 2022• 37 citations

Abstract

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

DOI: 10.1186/s12859-022-04661-7

Related papers

Genome assembly using quantum and quantum-inspired annealing

Aleksey S. Boev, Alexander Rakitko, Sergey R. Usmanov +5 more

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.

arXiv:2004.06719Scientific ReportsJun 23, 202163 citations

Quantum-Classical Synergy: Enhancing De Novo Genome Assembly with Hybridized QUBO Optimization

Anshit Mukherjee, Biswadip Basu Mallik

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.

Jul 24, 20240 citations

QuASeR: Quantum Accelerated de novo DNA sequence reconstruction

Aritra Sarkar, Zaid Al-Ars, Koen Bertels

In this article, we present QuASeR, a reference-free DNA sequence reconstruction implementation via de novo assembly on both gate-based and quantum annealing platforms. This is the first time this important application in bioinformatics is modeled using quantum computation. Each one of the four steps of the implementation (TSP, QUBO, Hamiltonians and QAOA) is explained with a proof-of-concept example to target both the genomics research community and quantum application developers in a self-contained manner. The implementation and results on executing the algorithm from a set of DNA reads to a reconstructed sequence, on a gate-based quantum simulator, the D-Wave quantum annealing simulator and hardware are detailed. We also highlight the limitations of current classical simulation and available quantum hardware systems. The implementation is open-source and can be found on https://github.com/QE-Lab/QuASeR.

arXiv:2004.05078PLoS ONEApr 12, 202163 citations

Accelerating De Novo Genome Assembly via Quantum-Assisted Graph Optimization with Bitstring Recovery

Jaya Vasavi Pamidimukkala, Himanshu Sahu, Ashwini Kannan +3 more

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.

quant-pharXiv:2602.00156Feb 2, 20261 citation

Accelerating DNA Fragments Assembly with Quantum Computing

Kumar Dilip, Bipin Kumar Rai, G S Pradeep Ghantasala

Rapid advances in DNA sequencing have converted genomics and made large strides in our expertise in genetic records and the way it pertain to evolution, health, and illness. DNA fragment meeting is the method of reassembling the small, fragmented reads that might be produced by using DNA sequencing to rebuild the authentic genome. DNA fragment meeting is a primary computational issue, especially for huge genomes, due to the full-size extent of statistics and the intrinsic complexity of correctly assembling genomes. The want for innovative solutions is highlighted by using the truth that traditional computational techniques, such as graph-primarily based totally and heuristic approaches, are resource-intensive, have scaling problems, and can be erroneous in complex genome regions. Because of its exquisite capability to do positive computations at formerly unheard-of quotes and efficiently manipulate hard optimization issues, quantum computing has simply come to mild as a likely road for overcoming those computational barriers. In computationally annoying responsibilities like combinatorial optimization and large-scale statistics processing, quantum algorithms just like the Quantum Approximate Optimization Algorithm (QAOA) and Grover`s set of rules for search optimization have verified the capacity to carry out higher than classical approaches. DNA fragments meeting with quantum computing have the potential to boost accuracy and performance even as additionally develop new possibilities for large-scale genomic study. The essential thoughts of quantum computing, current tendencies in quantum-primarily based totally algorithms and their relevance to the meeting system are all included in this chapter, which investigates the capability of quantum computing as an innovative device for DNA fragment assembly. This chapter intends to explore on how quantum strategies would possibly enhance the precision and effectiveness of DNA assembly, starting the door for brand new tendencies inside the subject of genomics with the aid of using reading the capability and constraints of quantum computing for genomics.

CRC Press eBooksSep 30, 20250 citations

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

Jing-Kai Fang, Yuefeng Lin, Jun-Han Huang +10 more

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

PRX LifeApr 23, 20247 citations