{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,27]],"date-time":"2026-02-27T04:11:06Z","timestamp":1772165466419,"version":"3.50.1"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,1,31]],"date-time":"2023-01-31T00:00:00Z","timestamp":1675123200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,1,31]],"date-time":"2023-01-31T00:00:00Z","timestamp":1675123200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Background<\/jats:title>\n                    <jats:p>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.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>\n                      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\n                      <jats:italic>publicly<\/jats:italic>\n                      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.\n                    <\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Conclusion<\/jats:title>\n                    <jats:p>The proposed outsourcing framework, PP-DDP, is secure and effective for solving the DDP problem.<\/jats:p>\n                  <\/jats:sec>","DOI":"10.1186\/s12859-023-05157-8","type":"journal-article","created":{"date-parts":[[2023,1,31]],"date-time":"2023-01-31T09:05:51Z","timestamp":1675155951000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["PP-DDP: a privacy-preserving outsourcing framework for solving the double digest problem"],"prefix":"10.1186","volume":"24","author":[{"given":"Jingwen","family":"Suo","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lize","family":"Gu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xingyu","family":"Yan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sijia","family":"Yang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaoya","family":"Hu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Licheng","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,1,31]]},"reference":[{"key":"5157_CR1","unstructured":"Chen Y, Peng B, Wang X, Tang H. Large-scale privacy-preserving mapping of human genomic sequences on hybrid clouds. In: 19th annual network and distributed system security symposium. San Diego, California, USA; 2012."},{"issue":"3","key":"5157_CR2","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/j.tig.2007.12.007","volume":"24","author":"ER Mardis","year":"2008","unstructured":"Mardis ER. The impact of next-generation sequencing technology on genetics. Trends Genet. 2008;24(3):133\u201341.","journal-title":"Trends Genet"},{"issue":"2","key":"5157_CR3","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1016\/0022-2836(70)90149-X","volume":"51","author":"HO Smith","year":"1970","unstructured":"Smith HO, Wilcox KW. A restriction enzyme from Hemophilus influenzae. I. Purification and general properties. J Mol Biol. 1970;51(2):379\u201391.","journal-title":"J Mol Biol"},{"key":"5157_CR4","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1146\/annurev.bi.44.070175.001421","volume":"44","author":"D Nathans","year":"1975","unstructured":"Nathans D, Smith HO. Restriction endonuleases in the analysis and restructuring of DNA molecules. Ann Rev Biochem. 1975;44:273\u201393.","journal-title":"Ann Rev Biochem"},{"issue":"4","key":"5157_CR5","doi-asserted-by":"publisher","first-page":"412","DOI":"10.1016\/0196-8858(91)90028-H","volume":"12","author":"W Schmitt","year":"1991","unstructured":"Schmitt W, Waterman MS. Multiple solutions of DNA restriction mapping problems. Adv Appl Math. 1991;12(4):412\u201327.","journal-title":"Adv Appl Math"},{"issue":"1","key":"5157_CR6","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/BF01188582","volume":"13","author":"PA Pevzner","year":"1995","unstructured":"Pevzner PA. DNA physical mapping and alternating Eulerian cycles in colored graphs. Algorithmica. 1995;13(1):77\u2013105.","journal-title":"Algorithmica"},{"issue":"4","key":"5157_CR7","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1504\/IJBRA.2008.021173","volume":"4","author":"Z Wu","year":"2008","unstructured":"Wu Z, Zhang Y. Solving large double digestion problems for DNA restriction mapping by using branchand-bound integer linear programming. Int J Bioinform Res Appl. 2008;4(4):351\u201362.","journal-title":"Int J Bioinform Res Appl"},{"key":"5157_CR8","unstructured":"Susmita SK, Satyajit B, Mukhopadhyaya S, Murthy CA. Genetic algorithm for double digest problem. In: International conference on pattern recognition and machine intelligence. Berlin, Heidelberg: Springer; 2005."},{"issue":"10","key":"5157_CR9","doi-asserted-by":"publisher","first-page":"453","DOI":"10.6026\/97320630008453","volume":"8","author":"M Ganjtabesh","year":"2012","unstructured":"Ganjtabesh M, Ahrabian H, Nowzari-Dalini A, Moghadam ZRK. Genetic algorithm solution for double digest problem. Bioinformation. 2012;8(10):453\u20136.","journal-title":"Bioinformation"},{"issue":"1","key":"5157_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s12859-019-2862-x","volume":"20","author":"L Wang","year":"2019","unstructured":"Wang L, Suo J, Pan Y, Li L. DDmap: a matlab package for the double digest problem using multiple genetic operators. BMC Bioinform. 2019;20(1):1\u201312.","journal-title":"BMC Bioinform"},{"key":"5157_CR11","doi-asserted-by":"publisher","first-page":"72910","DOI":"10.1109\/ACCESS.2020.2988117","volume":"8","author":"J Suo","year":"2020","unstructured":"Suo J, Gu L, Pan Y, Yang S, Hu X. Quantum inspired genetic algorithm for double digest problem. IEEE Access. 2020;8:72910\u20136.","journal-title":"IEEE Access"},{"issue":"6","key":"5157_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1093\/bib\/bbab151","volume":"22","author":"D Lu","year":"2021","unstructured":"Lu D, Zhang Y, Zhang L, Wang H, Weng W, Li L, Cai H. Methods of privacy-preserving genomic sequencing data alignments. Brief Bioinform. 2021;22(6):1\u201315.","journal-title":"Brief Bioinform"},{"issue":"2","key":"5157_CR13","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1093\/bioinformatics\/btv563","volume":"32","author":"S Wang","year":"2016","unstructured":"Wang S, Zhang Y, Dai W, Lauter K, Kim M, Tang Y, Jiang X. HEALER: homomorphic computation of ExAct Logistic rEgRession for secure rare disease variants analysis in GWAS. Bioinformatics. 2016;32(2):211\u20138.","journal-title":"Bioinformatics"},{"issue":"5","key":"5157_CR14","doi-asserted-by":"publisher","first-page":"1466","DOI":"10.1109\/JBHI.2016.2625299","volume":"21","author":"R Ghasemi","year":"2016","unstructured":"Ghasemi R, Aziz M, Mohammed N, Dehkordi M, Jiang X. Private and efficient query processing on outsourced genomic databases. IEEE J Biomed Health Inform. 2016;21(5):1466\u201372.","journal-title":"IEEE J Biomed Health Inform"},{"issue":"1","key":"5157_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s42400-020-00057-3","volume":"3","author":"X Liu","year":"2020","unstructured":"Liu X, Deng R, Wu P, Yang Y. Lightning-fast and privacy-preserving outsourced computation in the cloud. Cybersecurity. 2020;3(1):1\u201321.","journal-title":"Cybersecurity"},{"issue":"11","key":"5157_CR16","doi-asserted-by":"publisher","first-page":"1108","DOI":"10.1016\/j.cels.2021.07.010","volume":"12","author":"M Kim","year":"2021","unstructured":"Kim M, Harmanci A, Bossuat J, Carpov S, Cheon J, Chillotti I, Jiang X. Ultrafast homomorphic encryption models enable secure outsourcing of genotype imputation. Cell Syst. 2021;12(11):1108\u201320.","journal-title":"Cell Syst"},{"key":"5157_CR17","doi-asserted-by":"crossref","unstructured":"Gentry C. Fully homomorphic encryption using ideal lattices. In: Proceedings of the 41st annual ACM symposium on theory of computing. MD, USA: Bethesda; 2009. p. 169\u2013178.","DOI":"10.1145\/1536414.1536440"},{"issue":"9","key":"5157_CR18","doi-asserted-by":"publisher","first-page":"1918","DOI":"10.1109\/TIFS.2015.2435697","volume":"10","author":"K Li","year":"2015","unstructured":"Li K, Zhang W, Yang C, Yu N. Security analysis on one-to-many order preserving encryption-based cloud data search. IEEE Trans Inf Forensics Secur. 2015;10(9):1918\u201326.","journal-title":"IEEE Trans Inf Forensics Secur"},{"issue":"1","key":"5157_CR19","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1109\/TDSC.2016.2536601","volume":"15","author":"X Liu","year":"2018","unstructured":"Liu X, Choo R, Deng R, Lu R, Weng J. Efficient and privacy-preserving outsourced calculation of rational numbers. IEEE Trans Dependable Secure Comput. 2018;15(1):27\u201339.","journal-title":"IEEE Trans Dependable Secure Comput"},{"key":"5157_CR20","doi-asserted-by":"crossref","unstructured":"Liu D, Wang S. DEMO: Query encrypted databases practically. In: Proceedings of the 2012 ACM conference on computer and communications security. 2012. p. 1049\u20131051.","DOI":"10.1145\/2382196.2382321"},{"issue":"13","key":"5157_CR21","doi-asserted-by":"publisher","first-page":"1967","DOI":"10.1002\/cpe.2992","volume":"25","author":"D Liu","year":"2013","unstructured":"Liu D, Wang S. Nonlinear order preserving index for encrypted database query in service cloud environments. Concurr Comput Pract Exp. 2013;25(13):1967\u201384.","journal-title":"Concurr Comput Pract Exp"},{"key":"5157_CR22","doi-asserted-by":"crossref","unstructured":"Liu D, Bertino E, Yi X. Privacy of outsourced k-means clustering. In: 9th ACM symposium on information, computer and communications security. Kyoto, Japan; 2014. p. 123\u2013134.","DOI":"10.1145\/2590296.2590332"},{"key":"5157_CR23","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1016\/j.jnca.2014.07.001","volume":"59","author":"Z Liu","year":"2016","unstructured":"Liu Z, Chen X, Yang J, Jia C, You I. New order preserving encryption model for outsourced databases in cloud environments. J Netw Comput Appl. 2016;59:198\u2013207.","journal-title":"J Netw Comput Appl"},{"issue":"2","key":"5157_CR24","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1145\/359340.359342","volume":"21","author":"R Rivest","year":"1978","unstructured":"Rivest R, Shamir A, Adleman L. A method for obtaining digital signatures and public-key cryptosystems. Commun ACM. 1978;21(2):120\u20136.","journal-title":"Commun ACM"},{"issue":"4","key":"5157_CR25","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1109\/TIT.1985.1057074","volume":"31","author":"T ElGamal","year":"1985","unstructured":"ElGamal T. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans Inf Theory. 1985;31(4):469\u201372.","journal-title":"IEEE Trans Inf Theory"},{"key":"5157_CR26","doi-asserted-by":"crossref","unstructured":"Paillier P. Public-key cryptosystems based on composite degree residuosity classes. In: International conference on the theory and aapplications of cryptographic techniques. Berlin, Heidelberg: Springer; 1999. p. 223\u2013238.","DOI":"10.1007\/3-540-48910-X_16"},{"issue":"3","key":"5157_CR27","first-page":"552","volume":"105","author":"N Dowlin","year":"2017","unstructured":"Dowlin N, Gilad-Bachrach R, Laine K, Lauter K, Naehrig M, Wernsing J. Manual for using homomorphic encryption for bioinformatics. Proc IEEE. 2017;105(3):552\u201367.","journal-title":"Proc IEEE"},{"issue":"8","key":"5157_CR28","doi-asserted-by":"publisher","first-page":"3590","DOI":"10.1109\/TII.2017.2780885","volume":"14","author":"K Gai","year":"2017","unstructured":"Gai K, Qiu M. Blend arithmetic operations on tensor-based fully homomorphic encryption over real numbers. IEEE Trans Ind Inf. 2017;14(8):3590\u20138.","journal-title":"IEEE Trans Ind Inf"},{"key":"5157_CR29","doi-asserted-by":"crossref","unstructured":"Stehl\u00e9 D, Steinfeld R. Faster fully homomorphic encryption. In: International conference on the theory and application of cryptology and information security. Berlin, Heidelberg: Springer; 2010. p. 377\u2013394.","DOI":"10.1007\/978-3-642-17373-8_22"},{"issue":"3","key":"5157_CR30","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2633600","volume":"6","author":"Z Brakerski","year":"2014","unstructured":"Brakerski Z, Gentry C, Vaikuntanathan V. (Leveled) fully homomorphic encryption without bootstrapping. ACM Trans Comput Theory. 2014;6(3):1\u201336.","journal-title":"ACM Trans Comput Theory"},{"key":"5157_CR31","doi-asserted-by":"crossref","unstructured":"Brakerski Z, Vaikuntanathan V. Fully homomorphic encryption from ring-lwe and security for key dependent messages. In: 31st annual cryptology conference. Berlin, Heidelberg: Springer; 2011. p. 505\u2013524.","DOI":"10.1007\/978-3-642-22792-9_29"},{"key":"5157_CR32","doi-asserted-by":"crossref","unstructured":"Agrawal R, Kiernan J, Srikant R, Xu Y. Order preserving encryption for numeric data. In: Proceedings of the ACM SIGMOD international conference on management of data. Paris, France; 2004. p. 563\u2013574.","DOI":"10.1145\/1007568.1007632"},{"key":"5157_CR33","doi-asserted-by":"crossref","unstructured":"Boldyreva A, Chenette N, Lee Y, O\u2019Neill A. Order-preserving symmetric encryption. In: 28th annual international conference on the theory and applications of cryptographic techniques. Berlin, Heidelberg: Springer; 2009. p. 224-241.","DOI":"10.1007\/978-3-642-01001-9_13"},{"key":"5157_CR34","first-page":"463","volume":"2013","author":"RA Popa","year":"2013","unstructured":"Popa RA, Li F, Zeldovich N. An ideal security protocol for order-preserving encoding. IEEE Symp Secur Privacy. 2013;2013:463\u201377.","journal-title":"IEEE Symp Secur Privacy"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-023-05157-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s12859-023-05157-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-023-05157-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,23]],"date-time":"2023-03-23T07:01:36Z","timestamp":1679554896000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/s12859-023-05157-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,31]]},"references-count":34,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2023,12]]}},"alternative-id":["5157"],"URL":"https:\/\/doi.org\/10.1186\/s12859-023-05157-8","relation":{"has-preprint":[{"id-type":"doi","id":"10.21203\/rs.3.rs-1941096\/v1","asserted-by":"object"}]},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,1,31]]},"assertion":[{"value":"8 August 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 January 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 January 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"The authors declare that they have no competing interests.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"34"}}