QiBAM

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

Sarkar, A. (TU Delft Computer Engineering; QBee.eu)
Al-Ars, Z. (TU Delft Computer Engineering)
Almudever, Carmen G. (TU Delft QCD/Sebastiano Lab)
Bertels, K.L.M. (Katholieke Universiteit Leuven; QBee.eu)

2021

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.

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

http://resolver.tudelft.nl/uuid:bc2cb339-76f3-400a-8216-5b00af3b8aa1

10.3390/ electronics10192433

Electronics (Switzerland), 10 (19), 1-17

Institutional Repository

journal article

© 2021 A. Sarkar, Z. Al-Ars, Carmen G. Almudever, K.L.M. Bertels