Quantum gate algorithm for reference-guided DNA sequence alignment
Reference-guided DNA sequencing and alignment is an important process in
computational molecular biology. The amount of DNA data grows very fast, and
many new genomes are waiting to be sequenced while millions of private genomes
need to be re-sequenced. Each human genome has 3.2 B base pairs, and each one
could be stored with 2 bits of information, so one human genome would take 6.4
B bits or about 760 MB of storage (National Institute of General Medical
Sciences). Today most powerful tensor processing units cannot handle the volume
of DNA data necessitating a major leap in computing power. It is, therefore,
important to investigate the usefulness of quantum computers in genomic data
analysis, especially in DNA sequence alignment. Quantum computers are expected
to be involved in DNA sequencing, initially as parts of classical systems,
acting as quantum accelerators. The number of available qubits is increasing
annually, and future quantum computers could conduct DNA sequencing, taking the
place of classical computing systems. We present a novel quantum algorithm for
reference-guided DNA sequence alignment modeled with gate-based quantum
computing. The algorithm is scalable, can be integrated into existing classical
DNA sequencing systems and is intentionally structured to limit computational
errors. The quantum algorithm has been tested using the quantum processing
units and simulators provided by IBM Quantum, and its correctness has been
confirmed.
G. D. Varsamis I. G. Karafyllidis K. M. Gilkes U. Arranz R. Martin-Cuevas G. Calleja P. Dimitrakis P. Kolovos R. Sandaltzopoulos H. C. Jessen J. Wong