Quantum Inspired Genetic Algorithm for Double Digest Problem

IEEE Access

Yun Pan¹  Xiaoya Hu²  Lize Gu²  Sijia Yang²  Jingwen Suo² 

[1] School of Computer Sciences and Technology, Communication University of China, Beijing, China;State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing, China;

关键词: Double digest problem;    quantum inspired genetic algorithm;    DNA mapping;   

DOI  :  10.1109/ACCESS.2020.2988117

来源: DOAJ

【 摘 要 】

The double digest problem (DDP) is a fundamental problem in bioinformatics, and it has been proven to be an NP-hard problem. As a type of promising combinational optimization method inspired by evolutionary theory, genetic algorithms have attracted much attention during the past four decades, and some genetic algorithms have been successfully applied to solve the DDP. To further enhance the ability to solve the DDP, it is of interest to couple the insights from classical genetic algorithms with the parallel capability of quantum computation. Thus, in this paper, we propose a quantum inspired genetic algorithm (QIGA) for the DDP. In our QIGA, the binary Q-bit representation is converted to mapping sequences, and on this basis, DNA fragments are reordered. The solution of the DDP is a permutation, selected by the QIGA, of all the DNA fragments. The effectiveness and efficiency of our proposal can be inferred from the simulation results for the QIGA on a classical computer. As far as we know, this is the first attempt to address the DDP using a QIGA. Compared with classical genetic algorithms for the DDP, our QIGA slightly accelerates the time require to solve the problem, and we believe that it will achieve superior performance when a quantum computer with the required scale is available.

【 授权许可】

Unknown