QiBAM: Approximate Sub-String Index Search on Quantum Accelerators Applied to DNA Read Alignment

Research output: Contribution to journalArticleScientificpeer-review

1 Downloads (Pure)

Abstract

With small-scale quantum processors transitioning from experimental physics labs to industrial products, these processors in a few years are expected to scale up and be more robust for efficiently computing important algorithms in various fields. In this paper, we propose a quantum algorithm to address the challenging field of data processing for genome sequence reconstruction. This research describes an architecture-aware implementation of a quantum algorithm for sub-sequence alignment. A new algorithm named QiBAM (quantum indexed bidirectional associative memory) is proposed, which uses approximate pattern-matching based on Hamming distances. QiBAM extends the Grover’s search algorithm in two ways, allowing: (1) approximate matches needed for read errors in genomics, and (2) a distributed search for multiple solutions over the quantum encoding of DNA sequences. This approach gives a quadratic speedup over the classical algorithm. A full implementation of the algorithm is provided and verified using the OpenQL compiler and QX Simulator framework. Our implementation represents a first exploration towards a full-stack quantum accelerated genome sequencing pipeline design.
Original languageEnglish
Number of pages17
JournalElectronics (Switzerland)
DOIs
Publication statusPublished - 2021

Keywords

  • accelerator architectures
  • associative memory
  • DNA read alignment
  • genomics
  • pattern matching
  • quantum algorithms
  • quantum computing
  • quantum search

Fingerprint

Dive into the research topics of 'QiBAM: Approximate Sub-String Index Search on Quantum Accelerators Applied to DNA Read Alignment'. Together they form a unique fingerprint.

Cite this