Quantum Inspired Genetic Algorithm for Double Digest Problem
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 so...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2020-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/9068928/ |
| _version_ | 1818664571374665728 |
|---|---|
| author | Jingwen Suo Lize Gu Yun Pan Sijia Yang Xiaoya Hu |
| author_facet | Jingwen Suo Lize Gu Yun Pan Sijia Yang Xiaoya Hu |
| author_sort | Jingwen Suo |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-17T05:34:51Z |
| format | Article |
| id | doaj.art-c161a956084c4ae6b567be8eb7c3dc15 |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-12-17T05:34:51Z |
| publishDate | 2020-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-c161a956084c4ae6b567be8eb7c3dc152022-12-21T22:01:39ZengIEEEIEEE Access2169-35362020-01-018729107291610.1109/ACCESS.2020.29881179068928Quantum Inspired Genetic Algorithm for Double Digest ProblemJingwen Suo0https://orcid.org/0000-0001-5744-9296Lize Gu1Yun Pan2Sijia Yang3Xiaoya Hu4State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing, ChinaState Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing, ChinaSchool of Computer Sciences and Technology, Communication University of China, Beijing, ChinaState Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing, ChinaState Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing, ChinaThe 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.https://ieeexplore.ieee.org/document/9068928/Double digest problemquantum inspired genetic algorithmDNA mapping |
| spellingShingle | Jingwen Suo Lize Gu Yun Pan Sijia Yang Xiaoya Hu Quantum Inspired Genetic Algorithm for Double Digest Problem IEEE Access Double digest problem quantum inspired genetic algorithm DNA mapping |
| title | Quantum Inspired Genetic Algorithm for Double Digest Problem |
| title_full | Quantum Inspired Genetic Algorithm for Double Digest Problem |
| title_fullStr | Quantum Inspired Genetic Algorithm for Double Digest Problem |
| title_full_unstemmed | Quantum Inspired Genetic Algorithm for Double Digest Problem |
| title_short | Quantum Inspired Genetic Algorithm for Double Digest Problem |
| title_sort | quantum inspired genetic algorithm for double digest problem |
| topic | Double digest problem quantum inspired genetic algorithm DNA mapping |
| url | https://ieeexplore.ieee.org/document/9068928/ |
| work_keys_str_mv | AT jingwensuo quantuminspiredgeneticalgorithmfordoubledigestproblem AT lizegu quantuminspiredgeneticalgorithmfordoubledigestproblem AT yunpan quantuminspiredgeneticalgorithmfordoubledigestproblem AT sijiayang quantuminspiredgeneticalgorithmfordoubledigestproblem AT xiaoyahu quantuminspiredgeneticalgorithmfordoubledigestproblem |