QiBAM: Approximate Sub-String Index Search on Quantum Accelerators Applied to DNA Read Alignment
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 addr...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-10-01
|
| Series: | Electronics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2079-9292/10/19/2433 |
| _version_ | 1797516662750052352 |
|---|---|
| author | Aritra Sarkar Zaid Al-Ars Carmen G. Almudever Koen L. M. Bertels |
| author_facet | Aritra Sarkar Zaid Al-Ars Carmen G. Almudever Koen L. M. Bertels |
| author_sort | Aritra Sarkar |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-10T07:04:01Z |
| format | Article |
| id | doaj.art-9ee4172d04de4579af0a54e164cfe85a |
| institution | Directory Open Access Journal |
| issn | 2079-9292 |
| language | English |
| last_indexed | 2024-03-10T07:04:01Z |
| publishDate | 2021-10-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Electronics |
| spelling | doaj.art-9ee4172d04de4579af0a54e164cfe85a2023-11-22T15:57:39ZengMDPI AGElectronics2079-92922021-10-011019243310.3390/electronics10192433QiBAM: Approximate Sub-String Index Search on Quantum Accelerators Applied to DNA Read AlignmentAritra Sarkar0Zaid Al-Ars1Carmen G. Almudever2Koen L. M. Bertels3Department of Quantum & Computer Engineering, Faculty of Electrical Engineering, Mathematics and Computer Science, Delft University of Technology, 2628 CD Delft, The NetherlandsDepartment of Quantum & Computer Engineering, Faculty of Electrical Engineering, Mathematics and Computer Science, Delft University of Technology, 2628 CD Delft, The NetherlandsDepartment of Quantum & Computer Engineering, Faculty of Electrical Engineering, Mathematics and Computer Science, Delft University of Technology, 2628 CD Delft, The NetherlandsQBeeX, B-3001 Leuven, BelgiumWith 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.https://www.mdpi.com/2079-9292/10/19/2433accelerator architecturesassociative memoryDNA read alignmentgenomicspattern matchingquantum algorithms |
| spellingShingle | Aritra Sarkar Zaid Al-Ars Carmen G. Almudever Koen L. M. Bertels QiBAM: Approximate Sub-String Index Search on Quantum Accelerators Applied to DNA Read Alignment Electronics accelerator architectures associative memory DNA read alignment genomics pattern matching quantum algorithms |
| title | QiBAM: Approximate Sub-String Index Search on Quantum Accelerators Applied to DNA Read Alignment |
| title_full | QiBAM: Approximate Sub-String Index Search on Quantum Accelerators Applied to DNA Read Alignment |
| title_fullStr | QiBAM: Approximate Sub-String Index Search on Quantum Accelerators Applied to DNA Read Alignment |
| title_full_unstemmed | QiBAM: Approximate Sub-String Index Search on Quantum Accelerators Applied to DNA Read Alignment |
| title_short | QiBAM: Approximate Sub-String Index Search on Quantum Accelerators Applied to DNA Read Alignment |
| title_sort | qibam approximate sub string index search on quantum accelerators applied to dna read alignment |
| topic | accelerator architectures associative memory DNA read alignment genomics pattern matching quantum algorithms |
| url | https://www.mdpi.com/2079-9292/10/19/2433 |
| work_keys_str_mv | AT aritrasarkar qibamapproximatesubstringindexsearchonquantumacceleratorsappliedtodnareadalignment AT zaidalars qibamapproximatesubstringindexsearchonquantumacceleratorsappliedtodnareadalignment AT carmengalmudever qibamapproximatesubstringindexsearchonquantumacceleratorsappliedtodnareadalignment AT koenlmbertels qibamapproximatesubstringindexsearchonquantumacceleratorsappliedtodnareadalignment |