Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2308.03532 · Biosystems

Quantum algorithm for de novo DNA sequence assembly based on quantum walks on graphs

Georgios D. Varsamis, Ioannis G. Karafyllidis, K.M. Gilkes, U. Arranz, R. Martin-Cuevas, G. Calleja, J. Wong, H. C. Jessen, Panagiotis Dimitrakis, Petros Kolovos, Raphael Sandaltzopoulos

Published Sep 19, 2023• 6 citations
arXivHTMLPDF
DOI
10.1016/j.biosystems.2023.105037

Related papers

Multi-Quantum Agent System for DNA Self-Assembly

Vasile Vancea

Communications in computer and information science•Jan 1, 2026•0 citations

Algorithm for DNA sequence assembly by quantum annealing

Katarzyna Nałęcz-Charkiewicz, Robert Marek Nowak

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

BMC Bioinformatics•Apr 7, 2022•37 citations

Quantum gate algorithm for reference-guided DNA sequence alignment

Georgios D. Varsamis, Ioannis G. Karafyllidis, K.M. Gilkes +8 more

arXiv:2308.04525•Computational Biology and Chemistry•Sep 13, 2023•27 citations

Quantum-driven Path Exploration Algorithm: QAOA for de novo Genome Assembly

Jui-Ting Lu, Jean-Paul Adogbo, Peguy Kem-Meka Tiotsop Kadzue +2 more

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.

•Apr 24, 2026•0 citations

Quantum algorithms for genomic analysis in systems biology

Don Roosan, Hasiba Mahshed Khan, Rubayat Islam Khan

Elsevier eBooks•Jan 1, 2026•0 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.05078•PLoS ONE•Apr 12, 2021•63 citations
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).
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.
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.