An algorithm for DNA read alignment on quantum accelerators
arXiv:1909.05563
Abstract
With small-scale quantum processors transitioning from experimental physics labs to industrial products, these processors allow us to efficiently compute important algorithms in various fields. In this paper, we propose a quantum algorithm to address the challenging field of big 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, that uses approximate pattern-matching based on Hamming distances. QiBAM extends the Grover's search algorithm in two ways to allow for: (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. This represents a first exploration towards a full-stack quantum accelerated genome sequencing pipeline design. The open-source implementation can be found on https://github.com/prince-ph0en1x/QAGS.
arXiv commentKeywords: quantum algorithms, quantum search, DNA read alignment, genomics, associative memory, accelerators, in-memory computing
References in corpus (11)
- Quantum Mechanics helps in searching for a needle in a haystack
- Many-body quantum state tomography with neural networks
- Synthesis of Quantum Logic Circuits
- Grover's quantum searching algorithm is optimal
- Grover's Quantum Search Algorithm for an Arbitrary Initial Amplitude Distribution
- An Experimental Microarchitecture for a Superconducting Quantum Processor
- Quantum Computer Architecture: Towards Full-Stack Quantum Accelerators
- Fast Quantum Search Algorithms in Protein Sequence Comparison - Quantum Biocomputing
- Quantum associative memory with improved distributed queries
- Quantum Pattern Matching
- Sampling with quantum mechanics
Cited by in corpus (8)
- Biology and medicine in the landscape of quantum advantages
- QuASeR -- Quantum Accelerated De Novo DNA Sequence Reconstruction
- Efficient decomposition of unitary matrices in quantum circuit compilers
- Quantum Computer Architecture: Towards Full-Stack Quantum Accelerators
- Quantum Accelerator Stack: A Research Roadmap
- QPack: Quantum Approximate Optimization Algorithms as universal benchmark for quantum computers
- ACSS-q: Algorithmic complexity for short strings via quantum accelerated approach
- String Comparison on a Quantum Computer Using Hamming Distance