CoChat

Genome assembly using quantum and quantum-inspired annealing

Open access

The DOI matches its Crossref record; 56 of the 56 references it cites were found in a registry or an index.

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 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 $$\phi $$ ϕ 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 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.

Overview

The claims and statistics of this paper haven’t been checked yet.

Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1038/s41598-021-88321-5

Cites

56 of 56 references verified0 citation errors · 0 not checkable

Statistics

Figures

Figure 1 Solving the de novo genome assembly problem using quantum annealers and quantum-inspired (digital) annealing algorithms: (a) raw reads; (b) raw reads are transformed to the overlap-layout-consensus (OLC) graph; (c) finding the Hamiltonian path for the OLC graph is reduced to the QUBO problem; (d) the QUBO problem should be embedded to the architecture of the quantum annealer (D-Wave): for this purpose each logical variable of the the QUBO problem is assigned with several qubits of the quantum annealer; (e) and (f) the Ising problem in QUBO form can be solved using quantum annealers (D-Wave) and quantum-inspired algorithms (SimCIM), correspondingly; (g) the output is the Hamiltonian path; (h) the genome sequence is obtained as the solution.
Figure 1 Solving the de novo genome assembly problem using quantum annealers and quantum-inspired (digital) annealing algorithms: (a) raw reads; (b) raw reads are transformed to the overlap-layout-consensus (OLC) graph; (c) finding the Hamiltonian path for the OLC graph is reduced to the QUBO problem; (d) the QUBO problem should be embedded to the architecture of the quantum annealer (D-Wave): for this purpose each logical variable of the the QUBO problem is assigned with several qubits of the quantum annealer; (e) and (f) the Ising problem in QUBO form can be solved using quantum annealers (D-Wave) and quantum-inspired algorithms (SimCIM), correspondingly; (g) the output is the Hamiltonian path; (h) the genome sequence is obtained as the solution.CC BY · PubMed Central
Figure 2 Comparison of the performance of quantum and quantum-inspired methods for de novo genome assembly based on synthetic data (10 problems were generated for every sequence length): we compare TTS for quantum device D-Wave and quantum-inspired optimization algorithm SimCIM.
Figure 2 Comparison of the performance of quantum and quantum-inspired methods for de novo genome assembly based on synthetic data (10 problems were generated for every sequence length): we compare TTS for quantum device D-Wave and quantum-inspired optimization algorithm SimCIM.CC BY · PubMed Central
Figure 3 Experimental scheme for the synthetic dataset.
Figure 3 Experimental scheme for the synthetic dataset.CC BY · PubMed Central

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

Show all 56 references

Cited by

See all 87

Metadata

Authors
Boev, A. S., Rakitko, A. S., Usmanov, S. R., Kobzeva, A. N., Popov, I. V., Ilinsky, V. V., Kiktenko, E. O., & Fedorov, A. K.
Affiliations
  • Russian Quantum Center (RU)
  • Moscow Institute of Physics and Technology (RU)
Corresponding author
Fedorov, A. K.
Venue
Scientific Reports
Published
2021-06-23
Volume
11
Issue
1
Pages
13183-13183
ISSN
2045-2322 (ISSN-L)
OpenAlex
W3016448351
Cited by
63
References
53
Citations by year
2026: 8 · 2025: 13 · 2024: 17 · 2023: 13 · 2022: 10 · 2021: 2
FWCI
3.70
Type
journal article
Language
en
Open access
Licence
Locations
  • Scientific Reports (publishedVersion, cc-by)
  • PubMed Central (publishedVersion, cc-by)
  • PubMed (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion, cc-by-sa)
  • arXiv (Cornell University)
Funders
Russian Science Foundation (19-71-10092)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Life Sciences › Biochemistry, Genetics and Molecular Biology › Molecular Biology › Genomics and Phylogenetic Studies
  • Physical Sciences › Mathematics › Theoretical Computer Science › DNA and Biological Computing
Keywords
de novo genome assembly, quantum annealing, quantum-inspired optimization, quantum annealers, combinatorial optimization, simulated quantum annealing
MeSH terms
Algorithms, Computer Simulation, DNA, Viral, Humans, Mathematics, Bacteriophage phi X 174, Quantum Theory, Genome, Viral, Sequence Analysis, DNA, Computational Biology, Genomics, Datasets as Topic

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

How to cite

Cite CoChat for the checks on this page, and the paper for its own findings.

This page
CoChat. (2026). Citation check: Genome assembly using quantum and quantum-inspired annealing. https://app.cochat.ai/papers/10.1038/s41598-021-88321-5
The paper
Boev, A. S., Rakitko, A. S., Usmanov, S. R., Kobzeva, A. N., Popov, I. V., Ilinsky, V. V., Kiktenko, E. O., & Fedorov, A. K. (2021). Genome assembly using quantum and quantum-inspired annealing. Scientific Reports. https://doi.org/10.1038/s41598-021-88321-5

Data sources

Bibliographic data: Semantic Scholar, OpenAlex, Crossref.

Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).

Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.