Related Experiment Video
Updated: Jul 16, 2025

Hybrid De Novo Genome Assembly for the Generation of Complete Genomes of Urinary Bacteria using Short- and Long-read Sequencing Technologies
Published on: August 20, 2021
Quantum algorithm for de novo DNA sequence assembly based on quantum walks on graphs
G D Varsamis1, I G Karafyllidis2, K M Gilkes3
1Department of Electrical and Computer Engineering, Democritus University of Thrace, Xanthi, 67100, Greece.
None:
De novo DNA sequence assembly is based on finding paths in overlap graphs, which is a NP-hard problem. We developed a quantum algorithm for de novo assembly based on quantum walks in graphs. The overlap graph is partitioned repeatedly to smaller graphs that form a hierarchical structure. We use quantum walks to find paths in low rank graphs and a quantum algorithm that finds Hamiltonian paths in high hierarchical rank. We tested the partitioning quantum algorithm, as well as the quantum algorithm that finds Hamiltonian paths in high hierarchical rank and confirmed its correct operation using Qiskit. We developed a custom simulation for quantum walks to search for paths in low rank graphs. The approach described in this paper may serve as a basis for the development of efficient quantum algorithms that solve the de novo DNA assembly problem.
Related Concept Videos
Maxam-Gilbert Sequencing
Challenges of the Maxam-Gilbert Method
The...
Genome Annotation and Assembly
Sanger Sequencing
Next-generation Sequencing
Next-Generation Sequencing Methods
Although all next-generation methods use different technologies, they all share a set of standard features....
RNA-seq
Before the discovery of RNA-seq, microarray-based methods and Sanger sequencing were used for transcriptome analysis. However, while...

