Abstract
Interferon-related research has important implications for understanding how biological immune systems function. With the development of DNA sequencing in recent years, interferon has been found in an increasing number of species, and many genome sequences remain to be annotated. Since BLAST is a commonly used sequence comparison method and conventional methods have difficulty to optimize the time complexity of the BLAST algorithm, quantum computing sheds light on accelerating BLAST for sequence annotation after DNA sequencing. Moreover, owing to the limitations of quantum devices, related quantum circuit optimization methods are needed to optimize the circuits of quantum algorithms to reduce the qubits required and complexity of the circuits. This work presents a quantum computing model for sequence annotation after DNA sequencing. First, we propose a quantum gene sequence alignment algorithm that optimizes the time complexity of the second step of BLAST from linear to semilinear by combining Grover's quantum search algorithm and the quantum 01 string alignment algorithm. Second, we propose a quantum circuit optimization method based on a truth table that successfully reduces the number of quantum resources needed to implement the quantum algorithm. Third, we propose a visualization and analysis website that provides online circuit generation and simple experiment running. The experimental results show that our proposed methods can be successfully performed both on virtual and real quantum computer, verifying the usability of the algorithm. Website: http://www.combio-lezhang.online/QGSA.