State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing, China.
School of Cyberspace Science and Technology, Beijing Institute of Technology, Beijing, China.
BMC Bioinformatics. 2023 Jan 31;24(1):34. doi: 10.1186/s12859-023-05157-8.
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.
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.
The proposed outsourcing framework, PP-DDP, is secure and effective for solving the DDP problem.
作为生物信息学的基本问题之一，双酶切问题（DDP）专注于重新排列适当序列中的遗传片段。尽管在过去几十年中提出了许多处理 DDP 问题的算法，但由于 DDP 的强 NP 完全性，解决 DDP 仍然是非常耗时的工作。然而，这些算法都没有考虑到 DDP 数据的隐私问题，这些数据包含关键的商业利益，并且是通过数天甚至数月的凝胶电泳实验收集的。因此，DDP 数据所有者不愿意将解决 DDP 的任务部署在云端。
我们在本文中的主要动机是设计一个安全的外包计算框架来解决 DDP 问题。我们首先提出了一个使用云服务器处理 DDP 问题的隐私保护外包框架；然后，为了使云服务器能够在密文上解决 DDP 实例，我们从 2012 年在 CCS 上发布的一个有序加密方案中定制了一个有序同态索引方案（OPHI）；最后，我们将之前解决 DDP 问题的工作，即量子启发遗传算法（QIGA），合并到我们的外包框架中，同时支持我们提出的 OPHI 方案。此外，在云服务器端执行 QIGA 之后，最优解，即两个映射序列，将公开传输给数据所有者。安全分析表明，从这些序列中，任何人都无法学习到任何关于原始 DDP 数据的信息。性能分析表明，客户端和服务器端的通信成本和计算工作量都是合理的。特别是，我们的实验表明，PP-DDP 可以针对典型的测试 DDP 实例和随机 DDP 实例找到可选的解决方案，并且具有较高的成功率，同时保持原始 DDP 数据的隐私性。
所提出的外包框架 PP-DDP 是安全有效的，可用于解决 DDP 问题。
