Genome assembly using quantum and quantum-inspired annealing
arXiv:2004.06719 · doi:10.1038/s41598-021-88321-5
Abstract
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 {\it 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 X 174 bacteriophage. Our results pave a way for an increase in the efficiency of solving bioinformatics problems with the use of quantum computing and, in particular, quantum annealing. We expect that the new generation of quantum annealing devices would outperform existing techniques for {\it 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 comment9 pages, 4 figures
References in corpus (22)
- Minimap2: pairwise alignment for nucleotide sequences
- Quantum Machine Learning
- Quantum Computing
- Probing many-body dynamics on a 51-atom quantum simulator
- Ising formulations of many NP problems
- Minimap and miniasm: fast mapping and de novo assembly for noisy long sequences
- Observation of a Many-Body Dynamical Phase Transition with a 53-Qubit Quantum Simulator
- Quantum Computational Supremacy
- Quantum annealing with more than one hundred qubits
- Defining and detecting quantum speedup
- Quantum computing with neutral atoms
- Observation of Entangled States of a Fully Controlled 20-Qubit System
- Experimental signature of programmable quantum annealing
- Quantum Optimization of Fully-Connected Spin Glasses
- Quantum Supremacy through the Quantum Approximate Optimization Algorithm
- Probing for quantum speedup in spin glass problems with planted solutions
- Quantum annealing versus classical machine learning applied to a simplified computational biology problem
- Searching for quantum speedup in quasistatic quantum annealers
- Glassy Chimeras could be blind to quantum speedup: Designing better benchmarks for quantum annealing machines
- Quantum-inspired algorithms in practice
- Annealing by simulating the coherent Ising machine
- QuASeR -- Quantum Accelerated De Novo DNA Sequence Reconstruction
Cited by in corpus (7)
- Quantum Computing for Molecular Biology
- Biology and medicine in the landscape of quantum advantages
- QuASeR -- Quantum Accelerated De Novo DNA Sequence Reconstruction
- Quantum-inspired Complex Convolutional Neural Networks
- A biological sequence comparison algorithm using quantum computers
- Quantum-inspired optimization for wavelength assignment
- Quantum computing for genomics: conceptual challenges and practical perspectives