PP-QIGA: A Privacy-Preserving Quantum Inspired Genetic Algorithm for the Double Digest Problem

Abstract Background: The double digest problem (DDP), a fundamental problem for reordering genetic fragments in a proper sequence, is one of the NP-hard problems in bioinformatics. During the past decades, many algorithms for dealing with the DDP problem were proposed. Among them, quantum inspired genetic algorithms (QIGA) have shown outstanding performance. However, none of the existing algorithms consider solving DDP under the well-known framework of outsourcing computation. In addition, none of them consider the issue of privacy-preserving of the DDP instances. Results: In this paper, we propose a privacy-preserving outsourcing computation framework, PP-QIGA, for solving the DDP problem by resorting to the idea of cloud computation, and meantime keep the privacy of the input DDP instances. Our main technical contribution is an order-preserving homomorphic index scheme (OPHI) that is tailored from an order-preserving homomorphic encryption scheme since for solving DDP, the decryption process is unnecessary. Under the PP-QIGA framework, the OPHI scheme is used to encrypt the input DDP instances. After the execution of QIGA, the optimal solution, i.e. two mapping sequences, would be output. From these sequences, none, even the cloud server for running QIGA, can learn any information about the original DDP data. Our experiments show that PP-QIGA can find optional solutions with a high success rate towards typical test DDP instances and random DDP instances. In addition, PP-QIGA takes less running time than DDmap, SK05 and GM12 while protecting data privacy, and a little bit more than that of QIGA, which is within an acceptable range. The success rate of PP-QIGA is almost the same as that of QIGA. Conclusion: Therefore, PP-QIGA is a more effective way to solve the DDP problem.