PP-DDP: a privacy-preserving outsourcing framework for solving the double digest problem
Abstract Background As one of the fundamental problems in bioinformatics, the double digest problem (DDP) focuses on reordering genetic fragments in a proper sequence. Although many algorithms for dealing with the DDP problem were proposed during the past decades, it is believed that solving DDP is...
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
BMC
2023-01-01
|
| Series: | BMC Bioinformatics |
| Subjects: | |
| Online Access: | https://doi.org/10.1186/s12859-023-05157-8 |
| _version_ | 1811171507045400576 |
|---|---|
| author | Jingwen Suo Lize Gu Xingyu Yan Sijia Yang Xiaoya Hu Licheng Wang |
| author_facet | Jingwen Suo Lize Gu Xingyu Yan Sijia Yang Xiaoya Hu Licheng Wang |
| author_sort | Jingwen Suo |
| collection | DOAJ |
| description | Abstract Background As one of the fundamental problems in bioinformatics, the double digest problem (DDP) focuses on reordering genetic fragments in a proper sequence. Although many algorithms for dealing with the DDP problem were proposed during the past decades, it is believed that solving DDP is still very time-consuming work due to the strongly NP-completeness of DDP. However, none of these algorithms consider the privacy issue of the DDP data that contains critical business interests and is collected with days or even months of gel-electrophoresis experiments. Thus, the DDP data owners are reluctant to deploy the task of solving DDP over cloud. Results Our main motivation in this paper is to design a secure outsourcing computation framework for solving the DDP problem. We at first propose a privacy-preserving outsourcing framework for handling the DDP problem by using a cloud server; Then, to enable the cloud server to solve the DDP instances over ciphertexts, an order-preserving homomorphic index scheme (OPHI) is tailored from an order-preserving encryption scheme published at CCS 2012; And finally, our previous work on solving DDP problem, a quantum inspired genetic algorithm (QIGA), is merged into our outsourcing framework, with the supporting of the proposed OPHI scheme. Moreover, after the execution of QIGA at the cloud server side, the optimal solution, i.e. two mapping sequences, would be transferred publicly to the data owner. Security analysis shows that from these sequences, none can learn any information about the original DDP data. Performance analysis shows that the communication cost and the computational workload for both the client side and the server side are reasonable. In particular, our experiments show that PP-DDP can find optional solutions with a high success rate towards typical test DDP instances and random DDP instances, and PP-DDP takes less running time than DDmap, SK05 and GM12, while keeping the privacy of the original DDP data. Conclusion The proposed outsourcing framework, PP-DDP, is secure and effective for solving the DDP problem. |
| first_indexed | 2024-04-10T17:16:10Z |
| format | Article |
| id | doaj.art-6be7d9b5baac431b98316dcb08878131 |
| institution | Directory Open Access Journal |
| issn | 1471-2105 |
| language | English |
| last_indexed | 2024-04-10T17:16:10Z |
| publishDate | 2023-01-01 |
| publisher | BMC |
| record_format | Article |
| series | BMC Bioinformatics |
| spelling | doaj.art-6be7d9b5baac431b98316dcb088781312023-02-05T12:25:35ZengBMCBMC Bioinformatics1471-21052023-01-0124112110.1186/s12859-023-05157-8PP-DDP: a privacy-preserving outsourcing framework for solving the double digest problemJingwen Suo0Lize Gu1Xingyu Yan2Sijia Yang3Xiaoya Hu4Licheng Wang5State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and TelecommunicationsState Key Laboratory of Networking and Switching Technology, Beijing University of Posts and TelecommunicationsState Key Laboratory of Networking and Switching Technology, Beijing University of Posts and TelecommunicationsState Key Laboratory of Networking and Switching Technology, Beijing University of Posts and TelecommunicationsState Key Laboratory of Networking and Switching Technology, Beijing University of Posts and TelecommunicationsState Key Laboratory of Networking and Switching Technology, Beijing University of Posts and TelecommunicationsAbstract Background As one of the fundamental problems in bioinformatics, the double digest problem (DDP) focuses on reordering genetic fragments in a proper sequence. Although many algorithms for dealing with the DDP problem were proposed during the past decades, it is believed that solving DDP is still very time-consuming work due to the strongly NP-completeness of DDP. However, none of these algorithms consider the privacy issue of the DDP data that contains critical business interests and is collected with days or even months of gel-electrophoresis experiments. Thus, the DDP data owners are reluctant to deploy the task of solving DDP over cloud. Results Our main motivation in this paper is to design a secure outsourcing computation framework for solving the DDP problem. We at first propose a privacy-preserving outsourcing framework for handling the DDP problem by using a cloud server; Then, to enable the cloud server to solve the DDP instances over ciphertexts, an order-preserving homomorphic index scheme (OPHI) is tailored from an order-preserving encryption scheme published at CCS 2012; And finally, our previous work on solving DDP problem, a quantum inspired genetic algorithm (QIGA), is merged into our outsourcing framework, with the supporting of the proposed OPHI scheme. Moreover, after the execution of QIGA at the cloud server side, the optimal solution, i.e. two mapping sequences, would be transferred publicly to the data owner. Security analysis shows that from these sequences, none can learn any information about the original DDP data. Performance analysis shows that the communication cost and the computational workload for both the client side and the server side are reasonable. In particular, our experiments show that PP-DDP can find optional solutions with a high success rate towards typical test DDP instances and random DDP instances, and PP-DDP takes less running time than DDmap, SK05 and GM12, while keeping the privacy of the original DDP data. Conclusion The proposed outsourcing framework, PP-DDP, is secure and effective for solving the DDP problem.https://doi.org/10.1186/s12859-023-05157-8Double digest problemPrivacy-preservingOutsourcing computationOrder-preserving homomorphic index schemeQuantum inspired genetic algorithm |
| spellingShingle | Jingwen Suo Lize Gu Xingyu Yan Sijia Yang Xiaoya Hu Licheng Wang PP-DDP: a privacy-preserving outsourcing framework for solving the double digest problem BMC Bioinformatics Double digest problem Privacy-preserving Outsourcing computation Order-preserving homomorphic index scheme Quantum inspired genetic algorithm |
| title | PP-DDP: a privacy-preserving outsourcing framework for solving the double digest problem |
| title_full | PP-DDP: a privacy-preserving outsourcing framework for solving the double digest problem |
| title_fullStr | PP-DDP: a privacy-preserving outsourcing framework for solving the double digest problem |
| title_full_unstemmed | PP-DDP: a privacy-preserving outsourcing framework for solving the double digest problem |
| title_short | PP-DDP: a privacy-preserving outsourcing framework for solving the double digest problem |
| title_sort | pp ddp a privacy preserving outsourcing framework for solving the double digest problem |
| topic | Double digest problem Privacy-preserving Outsourcing computation Order-preserving homomorphic index scheme Quantum inspired genetic algorithm |
| url | https://doi.org/10.1186/s12859-023-05157-8 |
| work_keys_str_mv | AT jingwensuo ppddpaprivacypreservingoutsourcingframeworkforsolvingthedoubledigestproblem AT lizegu ppddpaprivacypreservingoutsourcingframeworkforsolvingthedoubledigestproblem AT xingyuyan ppddpaprivacypreservingoutsourcingframeworkforsolvingthedoubledigestproblem AT sijiayang ppddpaprivacypreservingoutsourcingframeworkforsolvingthedoubledigestproblem AT xiaoyahu ppddpaprivacypreservingoutsourcingframeworkforsolvingthedoubledigestproblem AT lichengwang ppddpaprivacypreservingoutsourcingframeworkforsolvingthedoubledigestproblem |