Links to Exploration step
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">A secure SNP panel scheme using homomorphically encrypted K-mers without SNP calling on the user side</title><author><name sortKey="Park, Sungjoon" sort="Park, Sungjoon" uniqKey="Park S" first="Sungjoon" last="Park">Sungjoon Park</name><affiliation><nlm:aff id="Aff1"><institution-wrap><institution-id institution-id-type="ISNI">0000 0004 0470 5905</institution-id><institution-id institution-id-type="GRID">grid.31501.36</institution-id><institution>Department of Computer Science and Engineering, Seoul National University,</institution></institution-wrap>Seoul, Republic of Korea</nlm:aff></affiliation></author><author><name sortKey="Kim, Minsu" sort="Kim, Minsu" uniqKey="Kim M" first="Minsu" last="Kim">Minsu Kim</name><affiliation><nlm:aff id="Aff2"><institution-wrap><institution-id institution-id-type="ISNI">0000 0004 0470 5905</institution-id><institution-id institution-id-type="GRID">grid.31501.36</institution-id><institution>Interdisciplinary Program in Bioinformatics, Seoul National University,</institution></institution-wrap>Seoul, Republic of Korea</nlm:aff></affiliation></author><author><name sortKey="Seo, Seokjun" sort="Seo, Seokjun" uniqKey="Seo S" first="Seokjun" last="Seo">Seokjun Seo</name><affiliation><nlm:aff id="Aff3">Hyperconnect Inc, Seoul, Republic of Korea</nlm:aff></affiliation></author><author><name sortKey="Hong, Seungwan" sort="Hong, Seungwan" uniqKey="Hong S" first="Seungwan" last="Hong">Seungwan Hong</name><affiliation><nlm:aff id="Aff4"><institution-wrap><institution-id institution-id-type="ISNI">0000 0004 0470 5905</institution-id><institution-id institution-id-type="GRID">grid.31501.36</institution-id><institution>Department of Mathematical Sciences, Seoul National University,</institution></institution-wrap>Seoul, Republic of Korea</nlm:aff></affiliation></author><author><name sortKey="Han, Kyoohyung" sort="Han, Kyoohyung" uniqKey="Han K" first="Kyoohyung" last="Han">Kyoohyung Han</name><affiliation><nlm:aff id="Aff4"><institution-wrap><institution-id institution-id-type="ISNI">0000 0004 0470 5905</institution-id><institution-id institution-id-type="GRID">grid.31501.36</institution-id><institution>Department of Mathematical Sciences, Seoul National University,</institution></institution-wrap>Seoul, Republic of Korea</nlm:aff></affiliation></author><author><name sortKey="Lee, Keewoo" sort="Lee, Keewoo" uniqKey="Lee K" first="Keewoo" last="Lee">Keewoo Lee</name><affiliation><nlm:aff id="Aff4"><institution-wrap><institution-id institution-id-type="ISNI">0000 0004 0470 5905</institution-id><institution-id institution-id-type="GRID">grid.31501.36</institution-id><institution>Department of Mathematical Sciences, Seoul National University,</institution></institution-wrap>Seoul, Republic of Korea</nlm:aff></affiliation></author><author><name sortKey="Cheon, Jung Hee" sort="Cheon, Jung Hee" uniqKey="Cheon J" first="Jung Hee" last="Cheon">Jung Hee Cheon</name><affiliation><nlm:aff id="Aff4"><institution-wrap><institution-id institution-id-type="ISNI">0000 0004 0470 5905</institution-id><institution-id institution-id-type="GRID">grid.31501.36</institution-id><institution>Department of Mathematical Sciences, Seoul National University,</institution></institution-wrap>Seoul, Republic of Korea</nlm:aff></affiliation></author><author><name sortKey="Kim, Sun" sort="Kim, Sun" uniqKey="Kim S" first="Sun" last="Kim">Sun Kim</name><affiliation><nlm:aff id="Aff1"><institution-wrap><institution-id institution-id-type="ISNI">0000 0004 0470 5905</institution-id><institution-id institution-id-type="GRID">grid.31501.36</institution-id><institution>Department of Computer Science and Engineering, Seoul National University,</institution></institution-wrap>Seoul, Republic of Korea</nlm:aff></affiliation><affiliation><nlm:aff id="Aff2"><institution-wrap><institution-id institution-id-type="ISNI">0000 0004 0470 5905</institution-id><institution-id institution-id-type="GRID">grid.31501.36</institution-id><institution>Interdisciplinary Program in Bioinformatics, Seoul National University,</institution></institution-wrap>Seoul, Republic of Korea</nlm:aff></affiliation><affiliation><nlm:aff id="Aff5"><institution-wrap><institution-id institution-id-type="ISNI">0000 0004 0470 5905</institution-id><institution-id institution-id-type="GRID">grid.31501.36</institution-id><institution>Bioinformatics Institute, Seoul National University,</institution></institution-wrap>Seoul, Republic of Korea</nlm:aff></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">PMC</idno><idno type="pmid">30967116</idno><idno type="pmc">6456943</idno><idno type="url">http://www.ncbi.nlm.nih.gov/pmc/articles/PMC6456943</idno><idno type="RBID">PMC:6456943</idno><idno type="doi">10.1186/s12864-019-5473-z</idno><date when="2019">2019</date><idno type="wicri:Area/Pmc/Corpus">000303</idno><idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Corpus" wicri:corpus="PMC">000303</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en" level="a" type="main">A secure SNP panel scheme using homomorphically encrypted K-mers without SNP calling on the user side</title><author><name sortKey="Park, Sungjoon" sort="Park, Sungjoon" uniqKey="Park S" first="Sungjoon" last="Park">Sungjoon Park</name><affiliation><nlm:aff id="Aff1"><institution-wrap><institution-id institution-id-type="ISNI">0000 0004 0470 5905</institution-id><institution-id institution-id-type="GRID">grid.31501.36</institution-id><institution>Department of Computer Science and Engineering, Seoul National University,</institution></institution-wrap>Seoul, Republic of Korea</nlm:aff></affiliation></author><author><name sortKey="Kim, Minsu" sort="Kim, Minsu" uniqKey="Kim M" first="Minsu" last="Kim">Minsu Kim</name><affiliation><nlm:aff id="Aff2"><institution-wrap><institution-id institution-id-type="ISNI">0000 0004 0470 5905</institution-id><institution-id institution-id-type="GRID">grid.31501.36</institution-id><institution>Interdisciplinary Program in Bioinformatics, Seoul National University,</institution></institution-wrap>Seoul, Republic of Korea</nlm:aff></affiliation></author><author><name sortKey="Seo, Seokjun" sort="Seo, Seokjun" uniqKey="Seo S" first="Seokjun" last="Seo">Seokjun Seo</name><affiliation><nlm:aff id="Aff3">Hyperconnect Inc, Seoul, Republic of Korea</nlm:aff></affiliation></author><author><name sortKey="Hong, Seungwan" sort="Hong, Seungwan" uniqKey="Hong S" first="Seungwan" last="Hong">Seungwan Hong</name><affiliation><nlm:aff id="Aff4"><institution-wrap><institution-id institution-id-type="ISNI">0000 0004 0470 5905</institution-id><institution-id institution-id-type="GRID">grid.31501.36</institution-id><institution>Department of Mathematical Sciences, Seoul National University,</institution></institution-wrap>Seoul, Republic of Korea</nlm:aff></affiliation></author><author><name sortKey="Han, Kyoohyung" sort="Han, Kyoohyung" uniqKey="Han K" first="Kyoohyung" last="Han">Kyoohyung Han</name><affiliation><nlm:aff id="Aff4"><institution-wrap><institution-id institution-id-type="ISNI">0000 0004 0470 5905</institution-id><institution-id institution-id-type="GRID">grid.31501.36</institution-id><institution>Department of Mathematical Sciences, Seoul National University,</institution></institution-wrap>Seoul, Republic of Korea</nlm:aff></affiliation></author><author><name sortKey="Lee, Keewoo" sort="Lee, Keewoo" uniqKey="Lee K" first="Keewoo" last="Lee">Keewoo Lee</name><affiliation><nlm:aff id="Aff4"><institution-wrap><institution-id institution-id-type="ISNI">0000 0004 0470 5905</institution-id><institution-id institution-id-type="GRID">grid.31501.36</institution-id><institution>Department of Mathematical Sciences, Seoul National University,</institution></institution-wrap>Seoul, Republic of Korea</nlm:aff></affiliation></author><author><name sortKey="Cheon, Jung Hee" sort="Cheon, Jung Hee" uniqKey="Cheon J" first="Jung Hee" last="Cheon">Jung Hee Cheon</name><affiliation><nlm:aff id="Aff4"><institution-wrap><institution-id institution-id-type="ISNI">0000 0004 0470 5905</institution-id><institution-id institution-id-type="GRID">grid.31501.36</institution-id><institution>Department of Mathematical Sciences, Seoul National University,</institution></institution-wrap>Seoul, Republic of Korea</nlm:aff></affiliation></author><author><name sortKey="Kim, Sun" sort="Kim, Sun" uniqKey="Kim S" first="Sun" last="Kim">Sun Kim</name><affiliation><nlm:aff id="Aff1"><institution-wrap><institution-id institution-id-type="ISNI">0000 0004 0470 5905</institution-id><institution-id institution-id-type="GRID">grid.31501.36</institution-id><institution>Department of Computer Science and Engineering, Seoul National University,</institution></institution-wrap>Seoul, Republic of Korea</nlm:aff></affiliation><affiliation><nlm:aff id="Aff2"><institution-wrap><institution-id institution-id-type="ISNI">0000 0004 0470 5905</institution-id><institution-id institution-id-type="GRID">grid.31501.36</institution-id><institution>Interdisciplinary Program in Bioinformatics, Seoul National University,</institution></institution-wrap>Seoul, Republic of Korea</nlm:aff></affiliation><affiliation><nlm:aff id="Aff5"><institution-wrap><institution-id institution-id-type="ISNI">0000 0004 0470 5905</institution-id><institution-id institution-id-type="GRID">grid.31501.36</institution-id><institution>Bioinformatics Institute, Seoul National University,</institution></institution-wrap>Seoul, Republic of Korea</nlm:aff></affiliation></author></analytic><series><title level="j">BMC Genomics</title><idno type="eISSN">1471-2164</idno><imprint><date when="2019">2019</date></imprint></series></biblStruct></sourceDesc></fileDesc><profileDesc><textClass></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en"><sec><title>Background</title><p>Single Nucleotide Polymorphism (SNP) in the genome has become crucial information for clinical use. For example, the targeted cancer therapy is primarily based on the information which clinically important SNPs are detectable from the tumor. Many hospitals have developed their own panels that include clinically important SNPs. The genome information exchange between the patient and the hospital has become more popular. However, the genome sequence information is innate and irreversible and thus its leakage has serious consequences. Therefore, protecting one’s genome information is critical. On the other side, hospitals may need to protect their own panels. There is no known secure SNP panel scheme to protect both.</p></sec><sec><title>Results</title><p>In this paper, we propose a secure SNP panel scheme using homomorphically encrypted K-mers without requiring SNP calling on the user side and without revealing the panel information to the user. Use of the powerful homomorphic encryption technique is desirable, but there is no known algorithm to efficiently align two homomorphically encrypted sequences. Thus, we designed and implemented a novel secure SNP panel scheme utilizing the computationally feasible equality test on two homomorphically encrypted K-mers. To make the scheme work correctly, in addition to SNPs in the panel, sequence variations at the population level should be addressed. We designed a concept of Point Deviation Tolerance (PDT) level to address the false positives and false negatives. Using the TCGA BRCA dataset, we demonstrated that our scheme works at the level of over a hundred thousand somatic mutations. In addition, we provide a computational guideline for the panel design, including the size of K-mer and the number of SNPs.</p></sec><sec><title>Conclusions</title><p>The proposed method is the first of its kind to protect both the user’s sequence and the hospital’s panel information using the powerful homomorphic encryption scheme. We demonstrated that the scheme works with a simulated dataset and the TCGA BRCA dataset. In this study, we have shown only the feasibility of the proposed scheme and much more efforts should be done to make the scheme usable for clinical use.</p></sec></div></front><back><div1 type="bibliography"><listBibl><biblStruct><analytic><author><name sortKey="Kandoth, C" uniqKey="Kandoth C">C Kandoth</name></author><author><name sortKey="Mclellan, Md" uniqKey="Mclellan M">MD McLellan</name></author><author><name sortKey="Vandin, F" uniqKey="Vandin F">F Vandin</name></author><author><name sortKey="Ye, K" uniqKey="Ye K">K Ye</name></author><author><name sortKey="Niu, B" uniqKey="Niu B">B Niu</name></author><author><name sortKey="Lu, C" uniqKey="Lu C">C Lu</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Easton, Df" uniqKey="Easton D">DF Easton</name></author><author><name sortKey="Pharoah, Pd" uniqKey="Pharoah P">PD Pharoah</name></author><author><name sortKey="Antoniou, Ac" uniqKey="Antoniou A">AC Antoniou</name></author><author><name sortKey="Tischkowitz, M" uniqKey="Tischkowitz M">M Tischkowitz</name></author><author><name sortKey="Tavtigian, Sv" uniqKey="Tavtigian S">SV Tavtigian</name></author><author><name sortKey="Nathanson, Kl" uniqKey="Nathanson K">KL Nathanson</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Spataro, N" uniqKey="Spataro N">N Spataro</name></author><author><name sortKey="Rodriguez, Ja" uniqKey="Rodriguez J">JA Rodríguez</name></author><author><name sortKey="Navarro, A" uniqKey="Navarro A">A Navarro</name></author><author><name sortKey="Bosch, E" uniqKey="Bosch E">E Bosch</name></author></analytic></biblStruct><biblStruct></biblStruct><biblStruct><analytic><author><name sortKey="Lippert, C" uniqKey="Lippert C">C Lippert</name></author><author><name sortKey="Sabatini, R" uniqKey="Sabatini R">R Sabatini</name></author><author><name sortKey="Maher, Mc" uniqKey="Maher M">MC Maher</name></author><author><name sortKey="Kang, Ey" uniqKey="Kang E">EY Kang</name></author><author><name sortKey="Lee, S" uniqKey="Lee S">S Lee</name></author><author><name sortKey="Arikan, O" uniqKey="Arikan O">O Arikan</name></author></analytic></biblStruct><biblStruct></biblStruct><biblStruct><analytic><author><name sortKey="Naveed, M" uniqKey="Naveed M">M Naveed</name></author><author><name sortKey="Ayday, E" uniqKey="Ayday E">E Ayday</name></author><author><name sortKey="Clayton, Ew" uniqKey="Clayton E">EW Clayton</name></author><author><name sortKey="Fellay, J" uniqKey="Fellay J">J Fellay</name></author><author><name sortKey="Gunter, Ca" uniqKey="Gunter C">CA Gunter</name></author><author><name sortKey="Hubaux, Jp" uniqKey="Hubaux J">JP Hubaux</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Dowlin, N" uniqKey="Dowlin N">N Dowlin</name></author><author><name sortKey="Gilad Bachrach, R" uniqKey="Gilad Bachrach R">R Gilad-Bachrach</name></author><author><name sortKey="Laine, K" uniqKey="Laine K">K Laine</name></author><author><name sortKey="Lauter, K" uniqKey="Lauter K">K Lauter</name></author><author><name sortKey="Naehrig, M" uniqKey="Naehrig M">M Naehrig</name></author><author><name sortKey="Wernsing, J" uniqKey="Wernsing J">J Wernsing</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Homer, N" uniqKey="Homer N">N Homer</name></author><author><name sortKey="Szelinger, S" uniqKey="Szelinger S">S Szelinger</name></author><author><name sortKey="Redman, M" uniqKey="Redman M">M Redman</name></author><author><name sortKey="Duggan, D" uniqKey="Duggan D">D Duggan</name></author><author><name sortKey="Tembe, W" uniqKey="Tembe W">W Tembe</name></author><author><name sortKey="Muehling, J" uniqKey="Muehling J">J Muehling</name></author></analytic></biblStruct><biblStruct></biblStruct><biblStruct><analytic><author><name sortKey="Gymrek, M" uniqKey="Gymrek M">M Gymrek</name></author><author><name sortKey="Mcguire, Al" uniqKey="Mcguire A">AL McGuire</name></author><author><name sortKey="Golan, D" uniqKey="Golan D">D Golan</name></author><author><name sortKey="Halperin, E" uniqKey="Halperin E">E Halperin</name></author><author><name sortKey="Erlich, Y" uniqKey="Erlich Y">Y Erlich</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Shringarpure, Ss" uniqKey="Shringarpure S">SS Shringarpure</name></author><author><name sortKey="Bustamante, Cd" uniqKey="Bustamante C">CD Bustamante</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Humbert, M" uniqKey="Humbert M">M Humbert</name></author><author><name sortKey="Huguenin, K" uniqKey="Huguenin K">K Huguenin</name></author><author><name sortKey="Hugonot, J" uniqKey="Hugonot J">J Hugonot</name></author><author><name sortKey="Ayday, E" uniqKey="Ayday E">E Ayday</name></author><author><name sortKey="Hubaux, Jp" uniqKey="Hubaux J">JP Hubaux</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Uhlerop, C" uniqKey="Uhlerop C">C Uhlerop</name></author><author><name sortKey="Fienberg, Se" uniqKey="Fienberg S">SE Fienberg</name></author></analytic></biblStruct><biblStruct></biblStruct><biblStruct><analytic><author><name sortKey="Yu, F" uniqKey="Yu F">F Yu</name></author><author><name sortKey="Fienberg, Se" uniqKey="Fienberg S">SE Fienberg</name></author><author><name sortKey="Uhler, C" uniqKey="Uhler C">C Uhler</name></author></analytic></biblStruct><biblStruct></biblStruct><biblStruct><analytic><author><name sortKey="Simmons, S" uniqKey="Simmons S">S Simmons</name></author><author><name sortKey="Berger, B" uniqKey="Berger B">B Berger</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Simmons, S" uniqKey="Simmons S">S Simmons</name></author><author><name sortKey="Sahinalp, C" uniqKey="Sahinalp C">C Sahinalp</name></author><author><name sortKey="Berger, B" uniqKey="Berger B">B Berger</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Canim, M" uniqKey="Canim M">M Canim</name></author><author><name sortKey="Kantarcioglu, M" uniqKey="Kantarcioglu M">M Kantarcioglu</name></author><author><name sortKey="Malin, B" uniqKey="Malin B">B Malin</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Kamm, L" uniqKey="Kamm L">L Kamm</name></author><author><name sortKey="Bogdanov, D" uniqKey="Bogdanov D">D Bogdanov</name></author><author><name sortKey="Laur, S" uniqKey="Laur S">S Laur</name></author><author><name sortKey="Vilo, J" uniqKey="Vilo J">J Vilo</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Xie, W" uniqKey="Xie W">W Xie</name></author><author><name sortKey="Kantarcioglu, M" uniqKey="Kantarcioglu M">M Kantarcioglu</name></author><author><name sortKey="Bush, Ws" uniqKey="Bush W">WS Bush</name></author><author><name sortKey="Crawford, D" uniqKey="Crawford D">D Crawford</name></author><author><name sortKey="Denny, Jc" uniqKey="Denny J">JC Denny</name></author><author><name sortKey="Heatherly, R" uniqKey="Heatherly R">R Heatherly</name></author></analytic></biblStruct><biblStruct></biblStruct><biblStruct></biblStruct><biblStruct><analytic><author><name sortKey="Kantarcioglu, M" uniqKey="Kantarcioglu M">M Kantarcioglu</name></author><author><name sortKey="Jiang, W" uniqKey="Jiang W">W Jiang</name></author><author><name sortKey="Liu, Y" uniqKey="Liu Y">Y Liu</name></author><author><name sortKey="Malin, B" uniqKey="Malin B">B Malin</name></author></analytic></biblStruct><biblStruct></biblStruct><biblStruct></biblStruct><biblStruct></biblStruct><biblStruct></biblStruct><biblStruct></biblStruct><biblStruct><analytic><author><name sortKey="Wang, S" uniqKey="Wang S">S Wang</name></author><author><name sortKey="Zhang, Y" uniqKey="Zhang Y">Y Zhang</name></author><author><name sortKey="Dai, W" uniqKey="Dai W">W Dai</name></author><author><name sortKey="Lauter, K" uniqKey="Lauter K">K Lauter</name></author><author><name sortKey="Kim, M" uniqKey="Kim M">M Kim</name></author><author><name sortKey="Tang, Y" uniqKey="Tang Y">Y Tang</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Raisaro, Jl" uniqKey="Raisaro J">JL Raisaro</name></author><author><name sortKey="Choi, G" uniqKey="Choi G">G Choi</name></author><author><name sortKey="Pradervand, S" uniqKey="Pradervand S">S Pradervand</name></author><author><name sortKey="Colsenet, R" uniqKey="Colsenet R">R Colsenet</name></author><author><name sortKey="Jacquemont, N" uniqKey="Jacquemont N">N Jacquemont</name></author><author><name sortKey="Rosat, N" uniqKey="Rosat N">N Rosat</name></author><author><name sortKey="Mooser, V" uniqKey="Mooser V">V Mooser</name></author><author><name sortKey="Hubaux, J P" uniqKey="Hubaux J">J-P Hubaux</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Jagadeesh, Ka" uniqKey="Jagadeesh K">KA Jagadeesh</name></author><author><name sortKey="Wu, Dj" uniqKey="Wu D">DJ Wu</name></author><author><name sortKey="Birgmeier, Ja" uniqKey="Birgmeier J">JA Birgmeier</name></author><author><name sortKey="Boneh, D" uniqKey="Boneh D">D Boneh</name></author><author><name sortKey="Bejerano, G" uniqKey="Bejerano G">G Bejerano</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Jacquez, Gm" uniqKey="Jacquez G">GM Jacquez</name></author><author><name sortKey="Essex, A" uniqKey="Essex A">A Essex</name></author><author><name sortKey="Curtis, A" uniqKey="Curtis A">A Curtis</name></author><author><name sortKey="Kohler, B" uniqKey="Kohler B">B Kohler</name></author><author><name sortKey="Sherman, R" uniqKey="Sherman R">R Sherman</name></author><author><name sortKey="El Emam, K" uniqKey="El Emam K">K El Emam</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Ghasemi, R" uniqKey="Ghasemi R">R Ghasemi</name></author><author><name sortKey="Al Aziz, Mm" uniqKey="Al Aziz M">MM Al Aziz</name></author><author><name sortKey="Mohammed, N" uniqKey="Mohammed N">N Mohammed</name></author><author><name sortKey="Dehkordi, Mh" uniqKey="Dehkordi M">MH Dehkordi</name></author><author><name sortKey="Jiang, X" uniqKey="Jiang X">X Jiang</name></author></analytic></biblStruct><biblStruct></biblStruct><biblStruct><analytic><author><name sortKey="Tang, H" uniqKey="Tang H">H Tang</name></author><author><name sortKey="Jiang, X" uniqKey="Jiang X">X Jiang</name></author><author><name sortKey="Wang, X" uniqKey="Wang X">X Wang</name></author><author><name sortKey="Wang, S" uniqKey="Wang S">S Wang</name></author><author><name sortKey="Sofia, H" uniqKey="Sofia H">H Sofia</name></author><author><name sortKey="Fox, D" uniqKey="Fox D">D Fox</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Consortium, Ihgs" uniqKey="Consortium I">IHGS Consortium</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Casper, J" uniqKey="Casper J">J Casper</name></author><author><name sortKey="Zweig, As" uniqKey="Zweig A">AS Zweig</name></author><author><name sortKey="Villarreal, C" uniqKey="Villarreal C">C Villarreal</name></author><author><name sortKey="Tyner, C" uniqKey="Tyner C">C Tyner</name></author><author><name sortKey="Speir, Ml" uniqKey="Speir M">ML Speir</name></author><author><name sortKey="Rosenbloom, Kr" uniqKey="Rosenbloom K">KR Rosenbloom</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Network, Cga" uniqKey="Network C">CGA Network</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Milholland, B" uniqKey="Milholland B">B Milholland</name></author><author><name sortKey="Dong, X" uniqKey="Dong X">X Dong</name></author><author><name sortKey="Zhang, L" uniqKey="Zhang L">L Zhang</name></author><author><name sortKey="Hao, X" uniqKey="Hao X">X Hao</name></author><author><name sortKey="Suh, Y" uniqKey="Suh Y">Y Suh</name></author><author><name sortKey="Vijg, J" uniqKey="Vijg J">J Vijg</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Consortium, Gp" uniqKey="Consortium G">GP Consortium</name></author></analytic></biblStruct></listBibl></div1></back></TEI><pmc article-type="research-article"><pmc-dir>properties open_access</pmc-dir>
<front><journal-meta><journal-id journal-id-type="nlm-ta">BMC Genomics</journal-id><journal-id journal-id-type="iso-abbrev">BMC Genomics</journal-id><journal-title-group><journal-title>BMC Genomics</journal-title></journal-title-group><issn pub-type="epub">1471-2164</issn><publisher><publisher-name>BioMed Central</publisher-name><publisher-loc>London</publisher-loc></publisher></journal-meta><article-meta><article-id pub-id-type="pmid">30967116</article-id><article-id pub-id-type="pmc">6456943</article-id><article-id pub-id-type="publisher-id">5473</article-id><article-id pub-id-type="doi">10.1186/s12864-019-5473-z</article-id><article-categories><subj-group subj-group-type="heading"><subject>Research</subject></subj-group></article-categories><title-group><article-title>A secure SNP panel scheme using homomorphically encrypted K-mers without SNP calling on the user side</article-title></title-group><contrib-group><contrib contrib-type="author"><name><surname>Park</surname><given-names>Sungjoon</given-names></name><address><email>stj@snu.ac.kr</email></address><xref ref-type="aff" rid="Aff1">1</xref></contrib><contrib contrib-type="author"><name><surname>Kim</surname><given-names>Minsu</given-names></name><address><email>mdy89@snu.ac.kr</email></address><xref ref-type="aff" rid="Aff2">2</xref></contrib><contrib contrib-type="author"><name><surname>Seo</surname><given-names>Seokjun</given-names></name><address><email>dane2522@snu.ac.kr</email></address><xref ref-type="aff" rid="Aff3">3</xref></contrib><contrib contrib-type="author"><name><surname>Hong</surname><given-names>Seungwan</given-names></name><address><email>swanhong@snu.ac.kr</email></address><xref ref-type="aff" rid="Aff4">4</xref></contrib><contrib contrib-type="author"><name><surname>Han</surname><given-names>Kyoohyung</given-names></name><address><email>satanigh@snu.ac.kr</email></address><xref ref-type="aff" rid="Aff4">4</xref></contrib><contrib contrib-type="author"><name><surname>Lee</surname><given-names>Keewoo</given-names></name><address><email>activecondor@snu.ac.kr</email></address><xref ref-type="aff" rid="Aff4">4</xref></contrib><contrib contrib-type="author"><name><surname>Cheon</surname><given-names>Jung Hee</given-names></name><address><email>jhcheon@snu.ac.kr</email></address><xref ref-type="aff" rid="Aff4">4</xref></contrib><contrib contrib-type="author" corresp="yes"><name><surname>Kim</surname><given-names>Sun</given-names></name><address><email>sunkim.bioinfo@snu.ac.kr</email></address><xref ref-type="aff" rid="Aff1">1</xref><xref ref-type="aff" rid="Aff2">2</xref><xref ref-type="aff" rid="Aff5">5</xref></contrib><aff id="Aff1"><label>1</label><institution-wrap><institution-id institution-id-type="ISNI">0000 0004 0470 5905</institution-id><institution-id institution-id-type="GRID">grid.31501.36</institution-id><institution>Department of Computer Science and Engineering, Seoul National University,</institution></institution-wrap>Seoul, Republic of Korea</aff><aff id="Aff2"><label>2</label><institution-wrap><institution-id institution-id-type="ISNI">0000 0004 0470 5905</institution-id><institution-id institution-id-type="GRID">grid.31501.36</institution-id><institution>Interdisciplinary Program in Bioinformatics, Seoul National University,</institution></institution-wrap>Seoul, Republic of Korea</aff><aff id="Aff3"><label>3</label>Hyperconnect Inc, Seoul, Republic of Korea</aff><aff id="Aff4"><label>4</label><institution-wrap><institution-id institution-id-type="ISNI">0000 0004 0470 5905</institution-id><institution-id institution-id-type="GRID">grid.31501.36</institution-id><institution>Department of Mathematical Sciences, Seoul National University,</institution></institution-wrap>Seoul, Republic of Korea</aff><aff id="Aff5"><label>5</label><institution-wrap><institution-id institution-id-type="ISNI">0000 0004 0470 5905</institution-id><institution-id institution-id-type="GRID">grid.31501.36</institution-id><institution>Bioinformatics Institute, Seoul National University,</institution></institution-wrap>Seoul, Republic of Korea</aff></contrib-group><pub-date pub-type="epub"><day>4</day><month>4</month><year>2019</year></pub-date><pub-date pub-type="pmc-release"><day>4</day><month>4</month><year>2019</year></pub-date><pub-date pub-type="collection"><year>2019</year></pub-date><volume>20</volume><issue>Suppl 2</issue><issue-sponsor>Publication of this supplement has not been supported by sponsorship. Information about the source of funding for publication charges can be found in the individual articles. The articles have undergone the journal's standard peer review process for supplements. The Supplement Editors declare that they have no competing interests.</issue-sponsor><elocation-id>188</elocation-id><permissions><copyright-statement>© The Author(s) 2019</copyright-statement><license license-type="OpenAccess"><license-p><bold>Open Access</bold> This article is distributed under the terms of the Creative Commons Attribution 4.0 International License(<ext-link ext-link-type="uri" xlink:href="http://creativecommons.org/licenses/by/4.0/">http://creativecommons.org/licenses/by/4.0/</ext-link>), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made. The Creative Commons Public Domain Dedication waiver(<ext-link ext-link-type="uri" xlink:href="http://creativecommons.org/publicdomain/zero/1.0/">http://creativecommons.org/publicdomain/zero/1.0/</ext-link>) applies to the data made available in this article, unless otherwise stated.</license-p></license></permissions><abstract id="Abs1"><sec><title>Background</title><p>Single Nucleotide Polymorphism (SNP) in the genome has become crucial information for clinical use. For example, the targeted cancer therapy is primarily based on the information which clinically important SNPs are detectable from the tumor. Many hospitals have developed their own panels that include clinically important SNPs. The genome information exchange between the patient and the hospital has become more popular. However, the genome sequence information is innate and irreversible and thus its leakage has serious consequences. Therefore, protecting one’s genome information is critical. On the other side, hospitals may need to protect their own panels. There is no known secure SNP panel scheme to protect both.</p></sec><sec><title>Results</title><p>In this paper, we propose a secure SNP panel scheme using homomorphically encrypted K-mers without requiring SNP calling on the user side and without revealing the panel information to the user. Use of the powerful homomorphic encryption technique is desirable, but there is no known algorithm to efficiently align two homomorphically encrypted sequences. Thus, we designed and implemented a novel secure SNP panel scheme utilizing the computationally feasible equality test on two homomorphically encrypted K-mers. To make the scheme work correctly, in addition to SNPs in the panel, sequence variations at the population level should be addressed. We designed a concept of Point Deviation Tolerance (PDT) level to address the false positives and false negatives. Using the TCGA BRCA dataset, we demonstrated that our scheme works at the level of over a hundred thousand somatic mutations. In addition, we provide a computational guideline for the panel design, including the size of K-mer and the number of SNPs.</p></sec><sec><title>Conclusions</title><p>The proposed method is the first of its kind to protect both the user’s sequence and the hospital’s panel information using the powerful homomorphic encryption scheme. We demonstrated that the scheme works with a simulated dataset and the TCGA BRCA dataset. In this study, we have shown only the feasibility of the proposed scheme and much more efforts should be done to make the scheme usable for clinical use.</p></sec></abstract><kwd-group xml:lang="en"><title>Keywords</title><kwd>SNP panel</kwd><kwd>Homomorphic encryption</kwd><kwd>K-mer</kwd><kwd>Genomic security</kwd><kwd>Genomic privacy</kwd></kwd-group><conference xlink:href="http://glab.hzau.edu.cn/APBC2019/"><conf-name>The 17th Asia Pacific Bioinformatics Conference (APBC 2019)</conf-name><conf-acronym>APBC 2019</conf-acronym><conf-loc>Wuhan, China</conf-loc><conf-date>14-16 January 2019</conf-date></conference><custom-meta-group><custom-meta><meta-name>issue-copyright-statement</meta-name><meta-value>© The Author(s) 2019</meta-value></custom-meta></custom-meta-group></article-meta></front><body><sec id="Sec1"><title>Background</title><p>Single Nucleotide Polymorphism (SNP) is crucial information in medical sciences than ever before. A single aberrant nucleotide variation can incur dysfunction in a biological process, affecting individual vulnerability to certain diseases. Hence, SNP existence can be utilized to diagnose diseases. Sometimes, SNPs help determine effective treatment, especially in cancer. From The Cancer Genome Atlas (TCGA) project, numerous driver mutations are reported in many cancer types [<xref ref-type="bibr" rid="CR1">1</xref>] and panels using the curated mutation information have been developed [<xref ref-type="bibr" rid="CR2">2</xref>]. Furthermore, genetic disorders in Mendelian diseases are very well studied [<xref ref-type="bibr" rid="CR3">3</xref>] and thus SNP detection can be directly translated into the contribution to actual medical applications. Because of the importance of SNPs to disease, the US NIH has compiled a database called ClinVar [<xref ref-type="bibr" rid="CR4">4</xref>].</p><p>The utility of SNPs goes beyond the medicine domain. People are diverse in the genomic content, thus the difference in genomic content among people can be used to identify a specific person. For such reason, SNPs are often used for legal and forensic purposes. There are Direct-to-Customer SNP kits that are designed for non-medical use such as pedigree search. More people measure their genomes and use the information for various purposes.</p><p>As genomic data are widely used and disclosed, a potential threat to genomic privacy is a serious problem. DNA sequence is a blueprint of a human being since the information includes not only medical conditions but to the extent of even reconstructing facial model which is one of the most sensitive information of human being [<xref ref-type="bibr" rid="CR5">5</xref>]. Our knowledge on the human genome is very limited as of now and much more information encoded in the genome will be disclosed over the years. Thus, genomic information is critical and will cause severe damage to individuals if leaked. This could also lead to a social crisis because genomic data can be used to justify discrimination among people. Unlike other confidential data, genomic data are innate and immutable, making the damage irreversible and permanent throughout one’s lifetime. Due to its far-reaching and sensitive nature, the genomic data is prone to be monetized. For these reasons, It is very important to protect the genomic information from hackers, insurance establishments, hospitals, pharmaceuticals, government and all the possible threats yet to come.</p><p>Among recent measures to protect data, homomorphic encryption is a technology that gains attention recently. It refers to an encryption scheme that allows the third party to perform computations while not knowing any content of the original source data or the private key. If such computation includes addition and multiplication, then theoretically all computations can be performed and that is called fully homomorphic encryption. The result of the computation is also returned encrypted, thus the third party can provide its inference based on the data and at the same time cannot know the data content or perform inference at all. The first fully homomorphic encryption scheme is proposed by Gentry at 2009 [<xref ref-type="bibr" rid="CR6">6</xref>], and continually improved its efficiency.</p><p>For example, consider that Alice is running a company and Bob provides a cloud storage service. Alice stores her encrypted data on Bob’s cloud. When Alice wants to compute aggregate data, an average revenue per month for instance, she has to decrypt the data if it is traditionally encrypted. Decrypting on the cloud storage may reveal both the private key and the source data to Bob. Downloading the encrypted data to local and decrypting it goes against the purpose of utilizing cloud service in the first place. This is when homomorphic encryption comes useful. If the data is homomorphically encrypted, Alice does not have to decrypt the source data on Bob’s cloud to do the computation needed. Instead, the encrypted form of aggregate data can be computed as ciphertexts and downloaded to Alice’s computer, and then safely decrypted. This way, Alice can exploit Bob’s resource to compute the average revenue without giving any information to Bob.</p><p>In more formal notation, an encryption scheme is additive homomorphic encryption if and only if
<disp-formula id="Equa"><alternatives><tex-math id="M1">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document} $$\forall p ~ \forall q ~ \exists \odot : \mathcal{E} (p) \odot \mathcal{E} (q) = \mathcal{E} (p + q) $$ \end{document}</tex-math><mml:math id="M2"><mml:mrow><mml:mo>∀</mml:mo><mml:mi>p</mml:mi><mml:mspace width="1em"></mml:mspace><mml:mo>∀</mml:mo><mml:mi>q</mml:mi><mml:mspace width="1em"></mml:mspace><mml:mo>∃</mml:mo><mml:mo>⊙</mml:mo><mml:mo>:</mml:mo><mml:mi mathvariant="script">E</mml:mi><mml:mo>(</mml:mo><mml:mi>p</mml:mi><mml:mo>)</mml:mo><mml:mo>⊙</mml:mo><mml:mi mathvariant="script">E</mml:mi><mml:mo>(</mml:mo><mml:mi>q</mml:mi><mml:mo>)</mml:mo><mml:mo>=</mml:mo><mml:mi mathvariant="script">E</mml:mi><mml:mo>(</mml:mo><mml:mi>p</mml:mi><mml:mo>+</mml:mo><mml:mi>q</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:math><graphic xlink:href="12864_2019_5473_Article_Equa.gif" position="anchor"></graphic></alternatives></disp-formula> given plaintexts <italic>p</italic>, <italic>q</italic>, and <inline-formula id="IEq1"><alternatives><tex-math id="M3">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$ \mathcal {E} (\cdot) $\end{document}</tex-math><mml:math id="M4"><mml:mi mathvariant="script">E</mml:mi><mml:mo>(</mml:mo><mml:mo>·</mml:mo><mml:mo>)</mml:mo></mml:math><inline-graphic xlink:href="12864_2019_5473_Article_IEq1.gif"></inline-graphic></alternatives></inline-formula> an encryption procedure. <inline-formula id="IEq2"><alternatives><tex-math id="M5">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$ \mathcal {E} (p + q) $\end{document}</tex-math><mml:math id="M6"><mml:mi mathvariant="script">E</mml:mi><mml:mo>(</mml:mo><mml:mi>p</mml:mi><mml:mo>+</mml:mo><mml:mi>q</mml:mi><mml:mo>)</mml:mo></mml:math><inline-graphic xlink:href="12864_2019_5473_Article_IEq2.gif"></inline-graphic></alternatives></inline-formula> denotes a ciphertext that can be decrypted to plaintext <italic>p</italic>+<italic>q</italic> with the private key. Multiplicative homomorphic encryption works likewise.</p><sec id="Sec2"><title>Related work</title><p>Given the importance of genome information, there has recently been active research on genome security. Naveed et al. [<xref ref-type="bibr" rid="CR7">7</xref>] presented the history of genomics and related privacy issues including the homomorphic encryption. Dowlin et al. [<xref ref-type="bibr" rid="CR8">8</xref>] also demonstrated how homomorphic encryption and security could be used in the fields of bioinformatics. In detail, we categorize recent genomic security research works into three major groups: (1) differential privacy, (2) secure system design with traditional encryption scheme and (3) homomorphic encryption scheme.</p><p>Differential privacy includes de-identification, which refers to making genomic data unidentifiable by either anonymizing or discarding personally differential information. This aims to perturb the information so that any leak of data itself would not possibly lead to identifying the patient. However, it is shown in many papers that generic de-identification techniques are not powerful enough to prevent reconstructing identity [<xref ref-type="bibr" rid="CR9">9</xref>–<xref ref-type="bibr" rid="CR13">13</xref>]. To mitigate the risk, many improvements were made based on the domain knowledge of the genomic data [<xref ref-type="bibr" rid="CR14">14</xref>–<xref ref-type="bibr" rid="CR19">19</xref>].</p><p>The secure system design with traditional encryption focuses on controlling the flow of sensitive information. It relies on secret sharing of private keys with multiple parties that do not collude to ensure the confidentiality of the data. Canim et al. [<xref ref-type="bibr" rid="CR20">20</xref>] suggested secure operations based on a cryptographic coprocessor. Kamm et al. [<xref ref-type="bibr" rid="CR21">21</xref>] adopted multiple third parties to securely perform GWAS analyses in a distributed way. On the other hand, Xie et al. [<xref ref-type="bibr" rid="CR22">22</xref>] proposed a statistical approach called meta-analysis to recall aggregate features with reduced privacy risks. In the work of Wang et al. [<xref ref-type="bibr" rid="CR23">23</xref>], secure and efficient computation of genomic edit distance and querying similar sequence based on that is introduced.</p><p>The application of homomorphic encryption dates back only to few years since it is a new technology. Troncoso-Pastoriza et al. [<xref ref-type="bibr" rid="CR24">24</xref>] proposed error resilient private string search algorithm that is specially designed for DNAs using homomorphic encryption. Kantarcioglu et al. [<xref ref-type="bibr" rid="CR25">25</xref>] also adopted homomorphic encryption to securely share the aggregate data of genome sequence among researchers. Ayday et al. [<xref ref-type="bibr" rid="CR26">26</xref>, <xref ref-type="bibr" rid="CR27">27</xref>] proposed methods to query the disease susceptibility with clinical data encrypted. More recently, Kim et al. [<xref ref-type="bibr" rid="CR28">28</xref>] showed that homomorphic encryption can be used to obtain minor allele frequencies, <italic>χ</italic><sup>2</sup> statistic in GWAS and edit distance of sequences in a secure way. Lu et al. [<xref ref-type="bibr" rid="CR29">29</xref>] and Zhang et al. [<xref ref-type="bibr" rid="CR30">30</xref>] encrypted phenotype and genotype homomorphically and then was able to infer typical GWAS statistic. On the other hand, Wang et al. adopted homomorphic encryption on rare variants to perform homomorphic exact logistic regression [<xref ref-type="bibr" rid="CR31">31</xref>]. Raisaro et al. [<xref ref-type="bibr" rid="CR32">32</xref>] showed retrieving aggregate data computed under homomorphically encrypted data that is deployed to real world application on i2b2 data warehouse. Jagadeesh et al. [<xref ref-type="bibr" rid="CR33">33</xref>] also have shown secure SNP data sharing between hospitals to induce meaningful inference of disease. Other most recent works on homomorphic encryption include the works of Jacquez et al. [<xref ref-type="bibr" rid="CR34">34</xref>], Ghasemi et al. [<xref ref-type="bibr" rid="CR35">35</xref>], and Cheng <italic>et al</italic> [<xref ref-type="bibr" rid="CR36">36</xref>].</p><p>As described above, research on genomic privacy has been active and advanced significantly over the years. However, current research has been conducted assuming situations with some compromises. De-identification more or less manipulates the content of data and thus has possibility to contaminate the original information. The secure system design distributes the secret key and the computation to multiple third parties. However, either the trust or the resources for computing may not be available in reality. If the third parties are untrustworthy, they may collude to jeopardize the private system. Likewise, the shortage of resources such as storage, bandwidth and processing power is critical for such system to maintain.</p><p>Even the works with homomorphic encryptions have their own limitations, due to its inefficient nature. Most applications [<xref ref-type="bibr" rid="CR25">25</xref><italic>–</italic><xref ref-type="bibr" rid="CR27">27</xref><italic>,</italic><xref ref-type="bibr" rid="CR30">30</xref><italic>–</italic><xref ref-type="bibr" rid="CR32">32</xref>] encrypt a clean, annotated SNP existence information on the user side or clinic data as a plaintext. In this case, SNP calling should be done on the user side and then the SNP calling information is sent to the hospital. Some applications send sequences to the hospital [<xref ref-type="bibr" rid="CR25">25</xref><italic>–</italic><xref ref-type="bibr" rid="CR29">29</xref><italic>,</italic><xref ref-type="bibr" rid="CR37">37</xref>]. In this case, the querying result is limited to aggregate genomic data and clinical data. How to use these techniques for a secure SNP panel has not been explored.</p></sec><sec id="Sec3"><title>Motivation and contribution</title><p>In this paper, we propose a patient-to-hospital SNP panel scheme and its architecture is illustrated in Fig. <xref rid="Fig1" ref-type="fig">1</xref>. In our two party model, <bold>the patient</bold> has one’s raw sequence and the private key, and <bold>the hospital</bold> has computing power and the SNP panel. SNP panel refers to a tool owned by the hospital that can find the specific combination of SNPs.
<fig id="Fig1"><label>Fig. 1</label><caption><p>The traditional and homomorphic SNP detection scheme. In this figure, <inline-formula id="IEq3"><alternatives><tex-math id="M7">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\mathcal {E}(\cdot)$\end{document}</tex-math><mml:math id="M8"><mml:mi mathvariant="script">E</mml:mi><mml:mo>(</mml:mo><mml:mo>·</mml:mo><mml:mo>)</mml:mo></mml:math><inline-graphic xlink:href="12864_2019_5473_Article_IEq3.gif"></inline-graphic></alternatives></inline-formula> and <inline-formula id="IEq4"><alternatives><tex-math id="M9">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\mathcal {D}(\cdot)$\end{document}</tex-math><mml:math id="M10"><mml:mi mathvariant="script">D</mml:mi><mml:mo>(</mml:mo><mml:mo>·</mml:mo><mml:mo>)</mml:mo></mml:math><inline-graphic xlink:href="12864_2019_5473_Article_IEq4.gif"></inline-graphic></alternatives></inline-formula> denote encryption and decryption respectively. Encryption needs public key while decryption needs private key. The subscript refers to the owner of the private key. For example, <inline-formula id="IEq5"><alternatives><tex-math id="M11">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\mathcal {E}_{hos} (\cdot)$\end{document}</tex-math><mml:math id="M12"><mml:msub><mml:mrow><mml:mi mathvariant="script">E</mml:mi></mml:mrow><mml:mrow><mml:mtext mathvariant="italic">hos</mml:mtext></mml:mrow></mml:msub><mml:mo>(</mml:mo><mml:mo>·</mml:mo><mml:mo>)</mml:mo></mml:math><inline-graphic xlink:href="12864_2019_5473_Article_IEq5.gif"></inline-graphic></alternatives></inline-formula> means the data is encrypted with hospital’s public key thus only the hospital can decrypt it. <bold>a</bold> demonstrates traditional way of detecting SNP. ① The patient gives the hospital the raw sequence. In order to protect data from being stolen in the middle, the sequence is encrypted using the hospital’s public key. ② The hospital decrypts patient sequence and performs computation to detect SNP. ③ The hospital returns the SNP existence information encrypted with the patient’s public key to the patient. ④ The patient can decrypt and get the SNP information. <bold>b</bold> on the other hand, demonstrates the same SNP detection scheme in homomorphic way. ① The patient sends one’s encrypted raw sequence but this time with the public key. ② Due to its homomorphic property, the hospital can perform computations on the sequence only with the public key, without decrypting the sequence. ③ The result is acquired in encrypted form, and the hospital returns the result to patient not knowing its content. ④ The patient can decrypt the result in secure environment</p></caption><graphic xlink:href="12864_2019_5473_Fig1_HTML" id="MO1"></graphic></fig></p><p>A possible scenario is that the patient sends the raw sequence to the hospital to detect SNP existence. In order to protect data from being stolen in the middle, the transferring raw sequence must be encrypted. In traditional patient-to-hospital model, the sequence is encrypted using the hospital’s public key. This method reveals the patient’s raw sequence. On the other hand, with homomorphic encryption, the patient can send the raw sequence encrypted with his/her own public key. Plus, the homomorphic nature of encryption allows the hospital to match encrypted sequence with its SNP panels without the private key or knowing the raw sequence.</p><p>Another thing to note is that, homomorphic encryption is slow and expensive that it cannot be applied to raw sequence for practical usage due to its computational inefficiency. In addition, although additive and multiplicative homomorphic encryption schemes is considered fully homomorphic in theory, its functionality is limited in reality due to their computationally demanding nature. Thus, using domain knowledge of genomic sequence, we devise a patient-to-hospital communication protocol onto which homomorphic encryption is applicable in order to securely detect SNPs without revealing the patient’s raw sequence and the hospital’s SNP panel assets to each other.</p><p>Thus, we propose a secure SNP panel scheme using homomorphically encrypted K-mers without SNP calling on the user side. The major challenge is that there is no known algorithm to align two homomorphically encrypted sequences as whole. The basic idea to overcome this challenge is to utilize the equality testing operation on two homomorphically encrypted K-mers that is computationally feasible under the homomorphic encryption scheme. The major features of our scheme is as below:
<list list-type="order"><list-item><p>We introduce a secure scheme that uses homomorphically encrypted K-mer, a short subsequence of the raw sequence, and show that encrypted K-mers can detect SNPs as good as the raw sequence does under certain conditions. With properly tuned value of K, exploiting K-mer can achieve small error bounds and practical runtime at the same time.</p></list-item><list-item><p>Our method considers genome variations among individuals. We assayed TCGA breast cancer patient data to estimate individual variation ratio. We further define and compute false positive rate and false negative rate of our SNP detection scheme and either suggest a method to control or show that the error is bounded to an ignorable value.</p></list-item><list-item><p>Our contribution is also to the extent of providing a SNP panel design guideline. When a hospital selects SNP residues for the diagnosis of a certain disease and wants to use our secure SNP panel scheme, our method suggests guidelines on which SNP residues under consideration can be used.</p></list-item></list></p></sec></sec><sec id="Sec4"><title>Methods</title><sec id="Sec5"><title>Data description and panel preprocessing</title><p>In actual clinical case, a SNP <italic>panel</italic> consists of multiple SNP <italic>residues</italic>, where each SNP residue corresponds to a pre-determined disease-associated SNP residue (Fig. <xref rid="Fig1" ref-type="fig">1</xref>). A targeted DNA sequencing is then performed to assess SNP status of each residue.</p><p>For our study, we generated a synthesized dataset that simulates the aforementioned case. In the dataset, the SNP residues are randomly sampled from coding sequences of the hg19 reference genome [<xref ref-type="bibr" rid="CR38">38</xref>], where refSeq gene annotation is used to specify coding regions (downloaded from UCSC genome database [<xref ref-type="bibr" rid="CR39">39</xref>]). First, we chose 1000 SNP residues sampled from the hg19 genome, then randomly combined them into various size of panels. As a result, we generated panels having 10, 20,..., 100 residues randomly selected from the pool of 1000 SNP residues. Hence, 10 different SNP panels of size ranging from 10 to 100 were generated.</p><p>After combining 10 different SNP panels, we simulated a massive parallel sequencing data (or DNA-seq) using WgSim. From the 1300 bp length flanking sequences (650 bp for each side) from each SNP residue, short-read sequences (151 bp × 2) were simulated. Here, the 1300 bp and “151 bp × 2” parameters were set to simulate the actual targeted short-read sequencing condition. The exact parameter for WgSim is “-e 0 -1 151 -2 151 -r 0 -R 0 -X 0 -S 0 -N [VAR]”, where all the parameters for random sequencing errors are set to none and the throughput parameter “-N” depends on the size of each panel. The sequencing depth was set to 10, meaning that 10 sequencing reads are expected to cover each SNP residue in average. So, to cover more residues, it requires more sequencing reads to simulate (hence larger “-N”). Lastly, each residue has 50% chance of nucleotide substitution to simulate SNPs by design. For instance, if we check any SNP residue, we can expect to find 5 reads having reference allele and other 5 reads having variant allele as planted. In summary, we generated 10 DNA-seq data corresponding to 10 SNP panels having different combination of SNP residues, each having average 50% substitution rate.</p><p>There could be unwanted overlap of flanking sequences between two different SNP residues. The overlap between two SNP residues would require a large value K. Therefore, we either merge the overlapped residues or discard one of them. This problem is described in Fig. <xref rid="Fig2" ref-type="fig">2</xref>. If two SNP residues are fully overlapped without mismatch, we merge them into a single entity having extended flanking sequences to prevent unnecessary long search for Ks. And if not, we randomly chose one residue and discarded the other one. To avoid promiscuous merging, we set the cutoff for fully overlap situation to 100 bp. Assuming a uniform random distribution, the probability that two flanking sequences overlap 100 bp by chance is 1−(1−2·4<sup>−100</sup>)<sup>2</sup>. The computed p-value is negligible. Therefore, it is safe to merge the residues satisfying this condition. However, if an extreme case occurs that flanking sequences of two SNP residues overlap more than 150 bp, which is longer than short-read length, we treat them same as the case of partial overlap situation, hence they are discarded.
<fig id="Fig2"><label>Fig. 2</label><caption><p>Two possible cases where different SNP residues have an overlap in their flanking sequences. There can be two different cases where an overlapping occurs between flanking sequences of two different SNP residues. <bold>a</bold> Fully overlapped without mismatch, <bold>b</bold> Partially overlapped with mismatch. In case of (<bold>a</bold>), two SNP residues are merged into a single sequence to prevent unnecessary long search for K’s. However, in case of (<bold>b</bold>), we randomly chose one residue and discarded the other one</p></caption><graphic xlink:href="12864_2019_5473_Fig2_HTML" id="MO2"></graphic></fig></p><p>The handling of overlapping sequence enables that, even if more than two SNP residues exist near, possibly within the range of K so that there exists a K-mer which has both SNPs, the proposed SNP panel scheme finds both SNPs correctly. It only has to enumerate all possible K-mers and perform equality test on the user K-mers with corresponding SNP labels.</p><p>Now we have a panel that will be used for testing our secure SNP scheme. The panel should be designed by doctors for a specific disease. What we have shown is a computational scheme to test whether a panel with many residues can be used with our secure SNP panel scheme that is proposed in this paper.</p></sec><sec id="Sec6"><title>Workflow: a bird’s eye view</title><p>The goal of this paper is to propose a patient-to-hospital secure communication protocol such that a patient would conceal its genome sequence while requesting SNP detections to a hospital with a panel. Specifically, we are interested in separating access between to the SNP panel at the hospital and to the genomic sequence of the patient. The SNP panel information is an asset of the hospital which may not be revealed to the public. On the other hand, the user does not want the hospital to know one’s sequence. The goal is to protect both.</p><p>In our scheme illustrated in Fig. <xref rid="Fig3" ref-type="fig">3</xref>, the patient has one’s raw genomic sequence and the hospital has panel sequence. To apply homomorphic encryption to sequences, we chunk both the raw sequence of the patient and the panel sequence of the hospital into K-mers. In other words, we get K-mers from substring of the sequences with a sliding window of stride 1, size K. What we want to do is encrypt K-mers and perform <bold>homomorphic equality tests</bold> on two K-mers. The patient would receive an encrypted result of SNP calling from the hospital. If a K-mer from patient sequence matches a K-mer from the panel sequence annotated with a specific SNP, the patient can tell which SNP one has. Further medical diagnosis can be done based on the test result.
<fig id="Fig3"><label>Fig. 3</label><caption><p>The overall architecture of our new SNP detection scheme. This figure depicts the general process of proposed SNP detection scheme. The set of panel sequences noted in yellow and the patient genome sequence noted in blue are chunked down into K-mers, respectively. After we encrypt K-mers, the client-side patient’s encrypted K-mers are transmitted to the server. The black box depicted in the middle denotes the homomorphic evaluation procedure. Here, we check the matching correspondence between any member in panel K-mer set and in the patient K-mer set. The result noted green is returned to the patient. The patient can decrypt the result with the private key securely on the client-side environment</p></caption><graphic xlink:href="12864_2019_5473_Fig3_HTML" id="MO3"></graphic></fig></p><p>Note that the patient encrypts the K-mers and holds the private key so that the hospital does not gain any information about the patient’s sequence. Meanwhile, the computation is done on the hospital’s side, securing SNP panel assets from leakage.</p></sec><sec id="Sec7"><title>K-mer design</title><p>Our SNP detection scheme works under specific conditions. To determine SNP existence by performing K-mer equality testing, the corresponding K-mer should be unique throughout the whole SNP panel sequences. Otherwise, K-mer matching cannot guarantee the existence of SNP. Thus the core idea of K-mer design is to set K long enough for all K-mers that contain any panel SNP to be distinguishable. However, while long K ensures unique K-mers, longer K-mers will be computationally expensive.</p><p>Therefore, given a panel we computed panel-specific minimum value of K such that all K-mers in the panel that have a SNP are distinct. To achieve this goal, first K-merize all panel sequences and group them into two sets: (A) K-mers with SNPs and (B) K-mers without. Then, following conditions must hold for K-mers with SNPs to be distinct.
<list list-type="order"><list-item><p>K-mers in set (A) are unique (have no duplicate)</p></list-item><list-item><p>K-mers in set (B) do not appear in set (A)</p></list-item></list></p><p>Among the Ks that satisfy the above conditions, the minimum value is chosen.</p></sec><sec id="Sec8"><title>False positive/negative errors</title><p>In our system, K of K-mer is defined to make all K-mers distinguishable and thus no false positive or negative errors. However, we assumed that individual patient sequence derived from SNP panel varies only at the interested SNP residue and the flanking sequences are identical for all patients. This is not the case when <italic>the variations at the population level</italic> are considered. An actual sequence derived by SNP panel may present unannotated deviations from what is known to the panel, other than SNP residues in it. Examples include point mutation, individual genome variation and sequencing errors. Presence of such deviations may result in false positive and false negative errors. False positive error occurs when the scheme identifies a K-mer and declares a SNP existence but actually the patient does not have one. False negative error occurs when the patient indeed has a SNP yet the scheme fails to detect one. We henceforth refer to point deviation as a single nucleotide deviation from intended panel sequence, resulting from either point mutation, individual variation or sequencing error.</p><p>False positive occurs when the determined K-mer did not originate from the flanking sequence around the found SNP. Rather, it originated from other irrelevant parts of patient genome sequence that correspond to any other SNP residue in the processing panel. To deal with false positive errors, we devised <bold>Point Deviation Tolerance (PDT) level</bold>. Previously in the process of computing K, we had two conditions on K-mers. Both conditions utilized the equality test to check uniqueness of K-mers in (A) and exclusiveness of K-mers in (A) over those in (B). We generalize the equality test to the hamming distance check with its lower bound being PDT. In other words, we apply strict rules and regard similar sequences ambiguous. Here, being similar is defined by PDT point deviations. The uniqueness condition is the specific case of PDT being 0. Thus we can rewrite the K-mer conditions as below:
<list list-type="order"><list-item><p>K-mers in set (A) are distinct (any pairs’ hamming distance greater than PDT)</p></list-item><list-item><p>K-mers in set (B) are distinct from K-mers in set (A)</p></list-item></list></p><p>Given PDT, one can determine a minimum value K satisfying the updated conditions. PDT works as a safety margin to K-mer ambiguity. The point deviation, namely the sum of point mutations, individual variation and sequencing errors, is allowed up to maximum PDT. Therefore, if the aggregate point deviation occurs less than or equal to PDT, false positive cases do not appear.</p><p>On the contrary, we cannot prevent false negative cases. False negative happens when the system cannot determine a SNP when it is truly in the patient’s sequence. The major cause of this is also the point deviation in the sequences flanking a SNP. It is infeasible to prepare all the variant K-mers as we did to cope with the false positive errors. In this paper, we assayed TCGA BRCA data to determine the distance distribution of somatic mutations among patients. Based on the data, we estimate the probability of a point mutation lying on K-mers to estimate false negative errors.</p></sec><sec id="Sec9"><title>RLWE cryptosystem</title><p>In this paper, we used HEAAN (Homomorphic Encryption for Arithmetic of Approximate Numbers) library to implement the equality test on two homomorphically encrypted K-mers. HEAAN is based on RLWE (Ring-Learning With Error) encryption scheme. RLWE is a variation of LWE (Learning With Error) problem, which is a lattice-based cryptography. LWE exploits its hardness assumption to ensure security which follows:
<disp-formula id="Equb"><alternatives><tex-math id="M13">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document} $$ a\! \leftarrow\! {\mathbb{Z}}^{n}_{q}, s \!\leftarrow\! {\mathbb{Z}}^{n}_{q}, e \!\leftarrow\! {\chi}^{n}, r_{1}, r_{2} \!\leftarrow\! {\mathbb{Z}}^{n}_{q} : (a, \langle a, s \rangle + e) {\approx}^{c} (r_{1}, r_{2}) $$ \end{document}</tex-math><mml:math id="M14"><mml:mrow><mml:mspace width="-14.0pt"></mml:mspace><mml:mi>a</mml:mi><mml:mspace width="0.3em"></mml:mspace><mml:mo>←</mml:mo><mml:mspace width="0.3em"></mml:mspace><mml:msubsup><mml:mrow><mml:mi>ℤ</mml:mi></mml:mrow><mml:mrow><mml:mi>q</mml:mi></mml:mrow><mml:mrow><mml:mi>n</mml:mi></mml:mrow></mml:msubsup><mml:mo>,</mml:mo><mml:mi>s</mml:mi><mml:mspace width="0.3em"></mml:mspace><mml:mo>←</mml:mo><mml:mspace width="0.3em"></mml:mspace><mml:msubsup><mml:mrow><mml:mi>ℤ</mml:mi></mml:mrow><mml:mrow><mml:mi>q</mml:mi></mml:mrow><mml:mrow><mml:mi>n</mml:mi></mml:mrow></mml:msubsup><mml:mo>,</mml:mo><mml:mi>e</mml:mi><mml:mspace width="0.3em"></mml:mspace><mml:mo>←</mml:mo><mml:mspace width="0.3em"></mml:mspace><mml:msup><mml:mrow><mml:mi>χ</mml:mi></mml:mrow><mml:mrow><mml:mi>n</mml:mi></mml:mrow></mml:msup><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>r</mml:mi></mml:mrow><mml:mrow><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>r</mml:mi></mml:mrow><mml:mrow><mml:mn>2</mml:mn></mml:mrow></mml:msub><mml:mspace width="0.3em"></mml:mspace><mml:mo>←</mml:mo><mml:mspace width="0.3em"></mml:mspace><mml:msubsup><mml:mrow><mml:mi>ℤ</mml:mi></mml:mrow><mml:mrow><mml:mi>q</mml:mi></mml:mrow><mml:mrow><mml:mi>n</mml:mi></mml:mrow></mml:msubsup><mml:mo>:</mml:mo><mml:mo>(</mml:mo><mml:mi>a</mml:mi><mml:mo>,</mml:mo><mml:mo>〈</mml:mo><mml:mi>a</mml:mi><mml:mo>,</mml:mo><mml:mi>s</mml:mi><mml:mo>〉</mml:mo><mml:mo>+</mml:mo><mml:mi>e</mml:mi><mml:mo>)</mml:mo><mml:msup><mml:mrow><mml:mo>≈</mml:mo></mml:mrow><mml:mrow><mml:mi>c</mml:mi></mml:mrow></mml:msup><mml:mo>(</mml:mo><mml:msub><mml:mrow><mml:mi>r</mml:mi></mml:mrow><mml:mrow><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>r</mml:mi></mml:mrow><mml:mrow><mml:mn>2</mml:mn></mml:mrow></mml:msub><mml:mo>)</mml:mo></mml:mrow></mml:math><graphic xlink:href="12864_2019_5473_Article_Equb.gif" position="anchor"></graphic></alternatives></disp-formula> In other words, for some secret key <italic>s</italic> and some error distribution <italic>χ</italic>, the relation between <italic>a</italic> and 〈<italic>a</italic>,<italic>s</italic>〉+<italic>e</italic> are computationally indistinguishable from random numbers. RLWE uses polynomial integer rings instead of vectors. Namely, <inline-formula id="IEq6"><alternatives><tex-math id="M15">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}${\mathbb {Z}}^{n}_{q}$\end{document}</tex-math><mml:math id="M16"><mml:msubsup><mml:mrow><mml:mi>ℤ</mml:mi></mml:mrow><mml:mrow><mml:mi>q</mml:mi></mml:mrow><mml:mrow><mml:mi>n</mml:mi></mml:mrow></mml:msubsup></mml:math><inline-graphic xlink:href="12864_2019_5473_Article_IEq6.gif"></inline-graphic></alternatives></inline-formula> s are replaced with <inline-formula id="IEq7"><alternatives><tex-math id="M17">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}${\mathbb {Z}}_{q}[\!X]/{\Phi }_{m}(X)$\end{document}</tex-math><mml:math id="M18"><mml:msub><mml:mrow><mml:mi>ℤ</mml:mi></mml:mrow><mml:mrow><mml:mi>q</mml:mi></mml:mrow></mml:msub><mml:mo>[</mml:mo><mml:mspace width="0.3em"></mml:mspace><mml:mi>X</mml:mi><mml:mo>]</mml:mo><mml:mo>/</mml:mo><mml:msub><mml:mrow><mml:mi>Φ</mml:mi></mml:mrow><mml:mrow><mml:mi>m</mml:mi></mml:mrow></mml:msub><mml:mo>(</mml:mo><mml:mi>X</mml:mi><mml:mo>)</mml:mo></mml:math><inline-graphic xlink:href="12864_2019_5473_Article_IEq7.gif"></inline-graphic></alternatives></inline-formula> for <italic>n</italic>=<italic>ϕ</italic>(<italic>m</italic>), where <italic>Φ</italic>(·) is cyclotomic polynomial and <italic>ϕ</italic>(·) is Euler’s phi function. RLWE is estimated to achieve equal or less level of security compared to LWE. Other parameters for the scheme are <italic>p</italic> for message modulus, <italic>q</italic> ciphertext modulus and ring <inline-formula id="IEq8"><alternatives><tex-math id="M19">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$R = \mathbb {Z}/{\Phi }_{M}(X)$\end{document}</tex-math><mml:math id="M20"><mml:mi>R</mml:mi><mml:mo>=</mml:mo><mml:mi>ℤ</mml:mi><mml:mo>/</mml:mo><mml:msub><mml:mrow><mml:mi>Φ</mml:mi></mml:mrow><mml:mrow><mml:mi>M</mml:mi></mml:mrow></mml:msub><mml:mo>(</mml:mo><mml:mi>X</mml:mi><mml:mo>)</mml:mo></mml:math><inline-graphic xlink:href="12864_2019_5473_Article_IEq8.gif"></inline-graphic></alternatives></inline-formula> for integer <italic>M</italic>. We further denote by <italic>R</italic><sub><italic>q</italic></sub>=<italic>R</italic>/<italic>q</italic><italic>R</italic> and <italic>χ</italic> for error distribution. The scheme for cryptography used throughout this paper is described in detail below. SKGen(params) Choose random <italic>s</italic>(<italic>X</italic>)←<italic>χ</italic>, and set <inline-formula id="IEq9"><alternatives><tex-math id="M21">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}${sk} = \vec s = (1, s)\in R_{q}^{2}$\end{document}</tex-math><mml:math id="M22"><mml:mtext mathvariant="italic">sk</mml:mtext><mml:mo>=</mml:mo><mml:mover accent="true"><mml:mrow><mml:mi>s</mml:mi></mml:mrow><mml:mo>→</mml:mo></mml:mover><mml:mo>=</mml:mo><mml:mo>(</mml:mo><mml:mn>1</mml:mn><mml:mo>,</mml:mo><mml:mi>s</mml:mi><mml:mo>)</mml:mo><mml:mo>∈</mml:mo><mml:msubsup><mml:mrow><mml:mi>R</mml:mi></mml:mrow><mml:mrow><mml:mi>q</mml:mi></mml:mrow><mml:mrow><mml:mn>2</mml:mn></mml:mrow></mml:msubsup></mml:math><inline-graphic xlink:href="12864_2019_5473_Article_IEq9.gif"></inline-graphic></alternatives></inline-formula>. PKGen(params, sk) Choose random <italic>a</italic>(<italic>X</italic>),<italic>a</italic><sup>′</sup>(<italic>X</italic>)←<italic>R</italic><sub><italic>q</italic></sub>, <italic>e</italic>(<italic>X</italic>),<italic>e</italic><sup>′</sup>(<italic>X</italic>)←<italic>χ</italic>, and set <italic>b</italic>(<italic>X</italic>)=−<italic>a</italic>(<italic>X</italic>)<italic>s</italic>(<italic>X</italic>)+<italic>p</italic><italic>e</italic>(<italic>X</italic>)∈<italic>R</italic><sub><italic>q</italic></sub> and <italic>b</italic><sup>′</sup>(<italic>X</italic>)=−<italic>a</italic><sup>′</sup>(<italic>X</italic>)<italic>s</italic><sup>′</sup>(<italic>X</italic>)+<italic>p</italic><italic>e</italic><sup>′</sup>(<italic>X</italic>)∈<italic>R</italic><sub><italic>q</italic></sub>. The public key is <italic>p</italic><italic>k</italic>=(<italic>b</italic>,<italic>a</italic>)∈<italic>R</italic><sup>2</sup> and the evaluation key is <italic>e</italic><italic>v</italic><italic>k</italic>=(<italic>b</italic><sup>′</sup>+<italic>p</italic><italic>s</italic><sup>2</sup>,<italic>a</italic><sup>′</sup>)∈<italic>R</italic><sub><italic>q</italic></sub>. Enc(pk, <italic>m</italic>∈<italic>R</italic><sub><italic>p</italic></sub>) Choose <italic>v</italic>(<italic>X</italic>),<italic>e</italic><sub>0</sub>(<italic>X</italic>),<italic>e</italic><sub>1</sub>(<italic>X</italic>)←<italic>χ</italic> and let <italic>c</italic><sub>1</sub>(<italic>X</italic>)=<italic>m</italic>(<italic>X</italic>)+<italic>v</italic>(<italic>X</italic>)<italic>b</italic>(<italic>X</italic>)+<italic>p</italic><italic>e</italic><sub>0</sub>(<italic>X</italic>),<italic>c</italic><sub>2</sub>(<italic>X</italic>)=<italic>v</italic>(<italic>X</italic>)<italic>a</italic>(<italic>X</italic>)+<italic>p</italic><italic>e</italic><sub>1</sub>(<italic>X</italic>). Return <inline-formula id="IEq10"><alternatives><tex-math id="M23">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\vec c = (c_{1}, c_{2}) \in R_{q}^{2}$\end{document}</tex-math><mml:math id="M24"><mml:mover accent="true"><mml:mrow><mml:mi>c</mml:mi></mml:mrow><mml:mo>→</mml:mo></mml:mover><mml:mo>=</mml:mo><mml:mo>(</mml:mo><mml:msub><mml:mrow><mml:mi>c</mml:mi></mml:mrow><mml:mrow><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>c</mml:mi></mml:mrow><mml:mrow><mml:mn>2</mml:mn></mml:mrow></mml:msub><mml:mo>)</mml:mo><mml:mo>∈</mml:mo><mml:msubsup><mml:mrow><mml:mi>R</mml:mi></mml:mrow><mml:mrow><mml:mi>q</mml:mi></mml:mrow><mml:mrow><mml:mn>2</mml:mn></mml:mrow></mml:msubsup></mml:math><inline-graphic xlink:href="12864_2019_5473_Article_IEq10.gif"></inline-graphic></alternatives></inline-formula>. Dec(sk, <inline-formula id="IEq11"><alternatives><tex-math id="M25">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\vec c$\end{document}</tex-math><mml:math id="M26"><mml:mover accent="true"><mml:mrow><mml:mi>c</mml:mi></mml:mrow><mml:mo>→</mml:mo></mml:mover></mml:math><inline-graphic xlink:href="12864_2019_5473_Article_IEq11.gif"></inline-graphic></alternatives></inline-formula>) Return <inline-formula id="IEq12"><alternatives><tex-math id="M27">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$[\langle \vec c, {sk} \rangle $\end{document}</tex-math><mml:math id="M28"><mml:mo>[</mml:mo><mml:mo>〈</mml:mo><mml:mover accent="true"><mml:mrow><mml:mi>c</mml:mi></mml:mrow><mml:mo>→</mml:mo></mml:mover><mml:mo>,</mml:mo><mml:mtext mathvariant="italic">sk</mml:mtext><mml:mo>〉</mml:mo></mml:math><inline-graphic xlink:href="12864_2019_5473_Article_IEq12.gif"></inline-graphic></alternatives></inline-formula>. Add(<inline-formula id="IEq13"><alternatives><tex-math id="M29">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\vec c_{1}$\end{document}</tex-math><mml:math id="M30"><mml:msub><mml:mrow><mml:mover accent="true"><mml:mrow><mml:mi>c</mml:mi></mml:mrow><mml:mo>→</mml:mo></mml:mover></mml:mrow><mml:mrow><mml:mn>1</mml:mn></mml:mrow></mml:msub></mml:math><inline-graphic xlink:href="12864_2019_5473_Article_IEq13.gif"></inline-graphic></alternatives></inline-formula>, <inline-formula id="IEq14"><alternatives><tex-math id="M31">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\vec c_{2}$\end{document}</tex-math><mml:math id="M32"><mml:msub><mml:mrow><mml:mover accent="true"><mml:mrow><mml:mi>c</mml:mi></mml:mrow><mml:mo>→</mml:mo></mml:mover></mml:mrow><mml:mrow><mml:mn>2</mml:mn></mml:mrow></mml:msub></mml:math><inline-graphic xlink:href="12864_2019_5473_Article_IEq14.gif"></inline-graphic></alternatives></inline-formula>) Return <inline-formula id="IEq15"><alternatives><tex-math id="M33">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\vec c_{\text {add}} = \vec c_{1} + \vec c_{2}$\end{document}</tex-math><mml:math id="M34"><mml:msub><mml:mrow><mml:mover accent="true"><mml:mrow><mml:mi>c</mml:mi></mml:mrow><mml:mo>→</mml:mo></mml:mover></mml:mrow><mml:mrow><mml:mtext>add</mml:mtext></mml:mrow></mml:msub><mml:mo>=</mml:mo><mml:msub><mml:mrow><mml:mover accent="true"><mml:mrow><mml:mi>c</mml:mi></mml:mrow><mml:mo>→</mml:mo></mml:mover></mml:mrow><mml:mrow><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo>+</mml:mo><mml:msub><mml:mrow><mml:mover accent="true"><mml:mrow><mml:mi>c</mml:mi></mml:mrow><mml:mo>→</mml:mo></mml:mover></mml:mrow><mml:mrow><mml:mn>2</mml:mn></mml:mrow></mml:msub></mml:math><inline-graphic xlink:href="12864_2019_5473_Article_IEq15.gif"></inline-graphic></alternatives></inline-formula>. Mult(<inline-formula id="IEq16"><alternatives><tex-math id="M35">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\vec c_{1}$\end{document}</tex-math><mml:math id="M36"><mml:msub><mml:mrow><mml:mover accent="true"><mml:mrow><mml:mi>c</mml:mi></mml:mrow><mml:mo>→</mml:mo></mml:mover></mml:mrow><mml:mrow><mml:mn>1</mml:mn></mml:mrow></mml:msub></mml:math><inline-graphic xlink:href="12864_2019_5473_Article_IEq16.gif"></inline-graphic></alternatives></inline-formula>, <inline-formula id="IEq17"><alternatives><tex-math id="M37">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\vec c_{2}$\end{document}</tex-math><mml:math id="M38"><mml:msub><mml:mrow><mml:mover accent="true"><mml:mrow><mml:mi>c</mml:mi></mml:mrow><mml:mo>→</mml:mo></mml:mover></mml:mrow><mml:mrow><mml:mn>2</mml:mn></mml:mrow></mml:msub></mml:math><inline-graphic xlink:href="12864_2019_5473_Article_IEq17.gif"></inline-graphic></alternatives></inline-formula>, <italic>e</italic><italic>v</italic><italic>k</italic>) For <inline-formula id="IEq18"><alternatives><tex-math id="M39">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\vec c_{1} = (b_{1}, a_{1})$\end{document}</tex-math><mml:math id="M40"><mml:msub><mml:mrow><mml:mover accent="true"><mml:mrow><mml:mi>c</mml:mi></mml:mrow><mml:mo>→</mml:mo></mml:mover></mml:mrow><mml:mrow><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo>=</mml:mo><mml:mo>(</mml:mo><mml:msub><mml:mrow><mml:mi>b</mml:mi></mml:mrow><mml:mrow><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>a</mml:mi></mml:mrow><mml:mrow><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo>)</mml:mo></mml:math><inline-graphic xlink:href="12864_2019_5473_Article_IEq18.gif"></inline-graphic></alternatives></inline-formula> and <inline-formula id="IEq19"><alternatives><tex-math id="M41">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\vec c_{2} = (b_{2}, a_{2})$\end{document}</tex-math><mml:math id="M42"><mml:msub><mml:mrow><mml:mover accent="true"><mml:mrow><mml:mi>c</mml:mi></mml:mrow><mml:mo>→</mml:mo></mml:mover></mml:mrow><mml:mrow><mml:mn>2</mml:mn></mml:mrow></mml:msub><mml:mo>=</mml:mo><mml:mo>(</mml:mo><mml:msub><mml:mrow><mml:mi>b</mml:mi></mml:mrow><mml:mrow><mml:mn>2</mml:mn></mml:mrow></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>a</mml:mi></mml:mrow><mml:mrow><mml:mn>2</mml:mn></mml:mrow></mml:msub><mml:mo>)</mml:mo></mml:math><inline-graphic xlink:href="12864_2019_5473_Article_IEq19.gif"></inline-graphic></alternatives></inline-formula>. Return <inline-formula id="IEq20"><alternatives><tex-math id="M43">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\vec c_{\text {mult}} = (b_{1}b_{2}, b_{1}a_{2} + b_{2}a_{1}) + a_{1}a_{2}\cdot evk \in R_{q}$\end{document}</tex-math><mml:math id="M44"><mml:msub><mml:mrow><mml:mover accent="true"><mml:mrow><mml:mi>c</mml:mi></mml:mrow><mml:mo>→</mml:mo></mml:mover></mml:mrow><mml:mrow><mml:mtext>mult</mml:mtext></mml:mrow></mml:msub><mml:mo>=</mml:mo><mml:mo>(</mml:mo><mml:msub><mml:mrow><mml:mi>b</mml:mi></mml:mrow><mml:mrow><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:msub><mml:mrow><mml:mi>b</mml:mi></mml:mrow><mml:mrow><mml:mn>2</mml:mn></mml:mrow></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mi>b</mml:mi></mml:mrow><mml:mrow><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:msub><mml:mrow><mml:mi>a</mml:mi></mml:mrow><mml:mrow><mml:mn>2</mml:mn></mml:mrow></mml:msub><mml:mo>+</mml:mo><mml:msub><mml:mrow><mml:mi>b</mml:mi></mml:mrow><mml:mrow><mml:mn>2</mml:mn></mml:mrow></mml:msub><mml:msub><mml:mrow><mml:mi>a</mml:mi></mml:mrow><mml:mrow><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo>)</mml:mo><mml:mo>+</mml:mo><mml:msub><mml:mrow><mml:mi>a</mml:mi></mml:mrow><mml:mrow><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:msub><mml:mrow><mml:mi>a</mml:mi></mml:mrow><mml:mrow><mml:mn>2</mml:mn></mml:mrow></mml:msub><mml:mo>·</mml:mo><mml:mtext mathvariant="italic">evk</mml:mtext><mml:mo>∈</mml:mo><mml:msub><mml:mrow><mml:mi>R</mml:mi></mml:mrow><mml:mrow><mml:mi>q</mml:mi></mml:mrow></mml:msub></mml:math><inline-graphic xlink:href="12864_2019_5473_Article_IEq20.gif"></inline-graphic></alternatives></inline-formula>.</p><p>RLWE-based homomorphic encryption supports batching (or SIMD) encoding and data array movement. If we call the each element of data array as slot, the scheme has permutation of message slots. This functionality can be used to make our homomorphic evaluation algorithm more efficient and split and merge DNA information. KeySwitchingMatrixGen(params, <italic>s</italic><italic>k</italic><sub>1</sub>→<italic>s</italic><italic>k</italic><sub>2</sub>) KeySwitch(<italic>c</italic>, <inline-formula id="IEq21"><alternatives><tex-math id="M45">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}${KS}_{{sk}_{1} \rightarrow {sk}_{2}}$\end{document}</tex-math><mml:math id="M46"><mml:msub><mml:mrow><mml:mtext mathvariant="italic">KS</mml:mtext></mml:mrow><mml:mrow><mml:msub><mml:mrow><mml:mtext mathvariant="italic">sk</mml:mtext></mml:mrow><mml:mrow><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo>→</mml:mo><mml:msub><mml:mrow><mml:mtext mathvariant="italic">sk</mml:mtext></mml:mrow><mml:mrow><mml:mn>2</mml:mn></mml:mrow></mml:msub></mml:mrow></mml:msub></mml:math><inline-graphic xlink:href="12864_2019_5473_Article_IEq21.gif"></inline-graphic></alternatives></inline-formula>) KeySwitchingMatrixGen (<italic>p</italic><italic>a</italic><italic>r</italic><italic>a</italic><italic>m</italic><italic>s</italic>,<italic>s</italic><italic>k</italic>(<italic>X</italic><sup><italic>k</italic></sup>) → <italic>s</italic><italic>k</italic>(<italic>X</italic>))Automorphism<inline-formula id="IEq22"><alternatives><tex-math id="M47">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\left (\textit {c}, X \rightarrow X^{k},\ {KS}_{{sk}\left (X^{k}\right) \rightarrow {sk}(X)}\right)\phantom {\dot {i}\!}$\end{document}</tex-math><mml:math id="M48"><mml:mfenced close=")" open="(" separators=""><mml:mrow><mml:mtext mathvariant="italic">c</mml:mtext><mml:mo>,</mml:mo><mml:mi>X</mml:mi><mml:mo>→</mml:mo><mml:msup><mml:mrow><mml:mi>X</mml:mi></mml:mrow><mml:mrow><mml:mi>k</mml:mi></mml:mrow></mml:msup><mml:mo>,</mml:mo><mml:mspace width="1em"></mml:mspace><mml:msub><mml:mrow><mml:mtext mathvariant="italic">KS</mml:mtext></mml:mrow><mml:mrow><mml:mtext mathvariant="italic">sk</mml:mtext><mml:mfenced close=")" open="(" separators=""><mml:mrow><mml:msup><mml:mrow><mml:mi>X</mml:mi></mml:mrow><mml:mrow><mml:mi>k</mml:mi></mml:mrow></mml:msup></mml:mrow></mml:mfenced><mml:mo>→</mml:mo><mml:mtext mathvariant="italic">sk</mml:mtext><mml:mo>(</mml:mo><mml:mi>X</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:msub></mml:mrow></mml:mfenced></mml:math><inline-graphic xlink:href="12864_2019_5473_Article_IEq22.gif"></inline-graphic></alternatives></inline-formula></p></sec><sec id="Sec10"><title>Data encoding and encryption</title><p>To perform equality tests of K-mers in numerical system, we regard each K-mer as a quaternary number via mapping each nucleobase A, C, G, T to 0,1,2,3, respectively and encode K-mers into integers. In this view, for example, if "GACT" is a K-mer of length 4, then it corresponds to <italic>K</italic>=2013<sub>(4)</sub>=2×4<sup>3</sup>+0×4<sup>2</sup>+1×4<sup>1</sup>+3=135.</p><p>However, encoding DNA sequence of length <italic>L</italic> wholly as an integer is inefficient when <italic>L</italic> is large, requiring a huge set of scheme parameters. To achieve a better performance, we suggest a method of breaking K-mers into smaller blocks of same length and performing equality tests for each block simultaneously. Henceforth for <italic>N</italic> user-side K-mers and <italic>M</italic> panel-side K-mers divided into <italic>B</italic> blocks respectively, we denote the data as following:
<list list-type="bullet"><list-item><p><italic>n</italic>-th user-side K-mer : <inline-formula id="IEq23"><alternatives><tex-math id="M49">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$K_{usr}^{(n)}$\end{document}</tex-math><mml:math id="M50"><mml:msubsup><mml:mrow><mml:mi>K</mml:mi></mml:mrow><mml:mrow><mml:mtext mathvariant="italic">usr</mml:mtext></mml:mrow><mml:mrow><mml:mo>(</mml:mo><mml:mi>n</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:msubsup></mml:math><inline-graphic xlink:href="12864_2019_5473_Article_IEq23.gif"></inline-graphic></alternatives></inline-formula>, or <italic>K</italic><sup>(<italic>n</italic>)</sup> when obvious. (<italic>n</italic>=0,1,⋯,<italic>N</italic>−1)</p></list-item><list-item><p><italic>m</italic>-th panel-side K-mer : <inline-formula id="IEq24"><alternatives><tex-math id="M51">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$K_{ref}^{(m)} (m = 0, 1, \cdots, M-1)$\end{document}</tex-math><mml:math id="M52"><mml:msubsup><mml:mrow><mml:mi>K</mml:mi></mml:mrow><mml:mrow><mml:mtext mathvariant="italic">ref</mml:mtext></mml:mrow><mml:mrow><mml:mo>(</mml:mo><mml:mi>m</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:msubsup><mml:mo>(</mml:mo><mml:mi>m</mml:mi><mml:mo>=</mml:mo><mml:mn>0</mml:mn><mml:mo>,</mml:mo><mml:mn>1</mml:mn><mml:mo>,</mml:mo><mml:mo>⋯</mml:mo><mml:mspace width="0.3em"></mml:mspace><mml:mo>,</mml:mo><mml:mi>M</mml:mi><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo>)</mml:mo></mml:math><inline-graphic xlink:href="12864_2019_5473_Article_IEq24.gif"></inline-graphic></alternatives></inline-formula></p></list-item><list-item><p><italic>b</italic>-th block of <inline-formula id="IEq25"><alternatives><tex-math id="M53">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$K_{usr}^{(n)}$\end{document}</tex-math><mml:math id="M54"><mml:msubsup><mml:mrow><mml:mi>K</mml:mi></mml:mrow><mml:mrow><mml:mtext mathvariant="italic">usr</mml:mtext></mml:mrow><mml:mrow><mml:mo>(</mml:mo><mml:mi>n</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:msubsup></mml:math><inline-graphic xlink:href="12864_2019_5473_Article_IEq25.gif"></inline-graphic></alternatives></inline-formula> : <inline-formula id="IEq26"><alternatives><tex-math id="M55">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$K_{usr}^{(n)}[\!b]$\end{document}</tex-math><mml:math id="M56"><mml:msubsup><mml:mrow><mml:mi>K</mml:mi></mml:mrow><mml:mrow><mml:mtext mathvariant="italic">usr</mml:mtext></mml:mrow><mml:mrow><mml:mo>(</mml:mo><mml:mi>n</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:msubsup><mml:mo>[</mml:mo><mml:mspace width="0.3em"></mml:mspace><mml:mi>b</mml:mi><mml:mo>]</mml:mo></mml:math><inline-graphic xlink:href="12864_2019_5473_Article_IEq26.gif"></inline-graphic></alternatives></inline-formula>, or <italic>K</italic><sup>(<italic>n</italic>)</sup>[ <italic>b</italic>] when obvious. (<italic>b</italic>=0,1,⋯,<italic>B</italic>−1)</p></list-item><list-item><p>size of a block: L</p></list-item></list></p><p>Once the set of user-side K-mers is ready, we can encode all user K-mers into <italic>B</italic> vectors. Specifically, <italic>b</italic>-th blocks of <italic>N</italic> user-side K-mers {<italic>K</italic><sup>(<italic>n</italic>)</sup>[ <italic>b</italic>]}<sub><italic>n</italic>∈[<italic>N</italic>]</sub> are encoded into a single vector <inline-formula id="IEq27"><alternatives><tex-math id="M57">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\vec {v}_{b} = \left (\vec {v}_{b}[\!0], \cdots, \vec {v}_{b}[\texttt {\!slots} - 1]\right)$\end{document}</tex-math><mml:math id="M58"><mml:msub><mml:mrow><mml:mover accent="true"><mml:mrow><mml:mi>v</mml:mi></mml:mrow><mml:mo>→</mml:mo></mml:mover></mml:mrow><mml:mrow><mml:mi>b</mml:mi></mml:mrow></mml:msub><mml:mo>=</mml:mo><mml:mfenced close=")" open="(" separators=""><mml:mrow><mml:msub><mml:mrow><mml:mover accent="true"><mml:mrow><mml:mi>v</mml:mi></mml:mrow><mml:mo>→</mml:mo></mml:mover></mml:mrow><mml:mrow><mml:mi>b</mml:mi></mml:mrow></mml:msub><mml:mo>[</mml:mo><mml:mspace width="0.3em"></mml:mspace><mml:mn>0</mml:mn><mml:mo>]</mml:mo><mml:mo>,</mml:mo><mml:mo>⋯</mml:mo><mml:mspace width="0.3em"></mml:mspace><mml:mo>,</mml:mo><mml:msub><mml:mrow><mml:mover accent="true"><mml:mrow><mml:mi>v</mml:mi></mml:mrow><mml:mo>→</mml:mo></mml:mover></mml:mrow><mml:mrow><mml:mi>b</mml:mi></mml:mrow></mml:msub><mml:mo>[</mml:mo><mml:mtext mathvariant="monospace">slots</mml:mtext><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo>]</mml:mo></mml:mrow></mml:mfenced></mml:math><inline-graphic xlink:href="12864_2019_5473_Article_IEq27.gif"></inline-graphic></alternatives></inline-formula>, where each component of <inline-formula id="IEq28"><alternatives><tex-math id="M59">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\vec v_{b}$\end{document}</tex-math><mml:math id="M60"><mml:msub><mml:mrow><mml:mover accent="true"><mml:mrow><mml:mi>v</mml:mi></mml:mrow><mml:mo>→</mml:mo></mml:mover></mml:mrow><mml:mrow><mml:mi>b</mml:mi></mml:mrow></mml:msub></mml:math><inline-graphic xlink:href="12864_2019_5473_Article_IEq28.gif"></inline-graphic></alternatives></inline-formula> is defined as
<disp-formula id="Equc"><alternatives><tex-math id="M61">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document} $$ \vec{v}_{b}[\!i]= \left\{ \begin{array}{ll} 1, & \text{if } i=K^{(n)}[\!b]\cdot N + n\text{ for some }n\in[\!N]\\ 0, & \text{otherwise } \end{array}\right.. $$ \end{document}</tex-math><mml:math id="M62"><mml:mrow><mml:msub><mml:mrow><mml:mover accent="true"><mml:mrow><mml:mi>v</mml:mi></mml:mrow><mml:mo>→</mml:mo></mml:mover></mml:mrow><mml:mrow><mml:mi>b</mml:mi></mml:mrow></mml:msub><mml:mo>[</mml:mo><mml:mspace width="0.3em"></mml:mspace><mml:mi>i</mml:mi><mml:mo>]</mml:mo><mml:mo>=</mml:mo><mml:mfenced close="" open="{" separators=""><mml:mrow><mml:mtable><mml:mtr><mml:mtd><mml:mn>1</mml:mn><mml:mo>,</mml:mo></mml:mtd><mml:mtd><mml:mtext>if</mml:mtext><mml:mi>i</mml:mi><mml:mo>=</mml:mo><mml:msup><mml:mrow><mml:mi>K</mml:mi></mml:mrow><mml:mrow><mml:mo>(</mml:mo><mml:mi>n</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:msup><mml:mo>[</mml:mo><mml:mspace width="0.3em"></mml:mspace><mml:mi>b</mml:mi><mml:mo>]</mml:mo><mml:mo>·</mml:mo><mml:mi>N</mml:mi><mml:mo>+</mml:mo><mml:mi>n</mml:mi><mml:mtext>for some</mml:mtext><mml:mi>n</mml:mi><mml:mo>∈</mml:mo><mml:mo>[</mml:mo><mml:mspace width="0.3em"></mml:mspace><mml:mi>N</mml:mi><mml:mo>]</mml:mo></mml:mtd></mml:mtr><mml:mtr><mml:mtd><mml:mn>0</mml:mn><mml:mo>,</mml:mo></mml:mtd><mml:mtd><mml:mtext>otherwise</mml:mtext></mml:mtd></mml:mtr></mml:mtable></mml:mrow></mml:mfenced><mml:mi>.</mml:mi></mml:mrow></mml:math><graphic xlink:href="12864_2019_5473_Article_Equc.gif" position="anchor"></graphic></alternatives></disp-formula></p><p>Here, we choose the dimension of vector slots by smallest power of 2 which does not exceed 4<sup><italic>L</italic></sup>·<italic>N</italic>, or the maximum of <italic>K</italic><sup>(<italic>n</italic>)</sup>[ <italic>b</italic>]·<italic>N</italic>+<italic>n</italic>. It is noteworthy that <italic>K</italic><sup>(<italic>n</italic>)</sup>[ <italic>b</italic>]·<italic>N</italic>+<italic>n</italic>=<italic>K</italic><sup>(<italic>m</italic>)</sup>[ <italic>b</italic>]·<italic>N</italic>+<italic>m</italic> if and only if <italic>n</italic>=<italic>m</italic>, since <italic>n</italic>,<italic>m</italic><<italic>N</italic>.</p><p>HEAAN supports a technique to pack <italic>k</italic> complex numbers in a single polynomial using a variant of the complex canonical embedding map <inline-formula id="IEq29"><alternatives><tex-math id="M63">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\phi :\mathbb {C}^{k} \rightarrow \mathcal {R}$\end{document}</tex-math><mml:math id="M64"><mml:mi>ϕ</mml:mi><mml:mo>:</mml:mo><mml:msup><mml:mrow><mml:mi>ℂ</mml:mi></mml:mrow><mml:mrow><mml:mi>k</mml:mi></mml:mrow></mml:msup><mml:mo>→</mml:mo><mml:mi mathvariant="script">R</mml:mi></mml:math><inline-graphic xlink:href="12864_2019_5473_Article_IEq29.gif"></inline-graphic></alternatives></inline-formula>. We make use of the technique and encrypt each of <inline-formula id="IEq30"><alternatives><tex-math id="M65">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\vec {v}_{b}$\end{document}</tex-math><mml:math id="M66"><mml:msub><mml:mrow><mml:mover accent="true"><mml:mrow><mml:mi>v</mml:mi></mml:mrow><mml:mo>→</mml:mo></mml:mover></mml:mrow><mml:mrow><mml:mi>b</mml:mi></mml:mrow></mml:msub></mml:math><inline-graphic xlink:href="12864_2019_5473_Article_IEq30.gif"></inline-graphic></alternatives></inline-formula>’s as a single ciphertext <inline-formula id="IEq31"><alternatives><tex-math id="M67">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\vec {c}_{b}$\end{document}</tex-math><mml:math id="M68"><mml:msub><mml:mrow><mml:mover accent="true"><mml:mrow><mml:mi>c</mml:mi></mml:mrow><mml:mo>→</mml:mo></mml:mover></mml:mrow><mml:mrow><mml:mi>b</mml:mi></mml:mrow></mml:msub></mml:math><inline-graphic xlink:href="12864_2019_5473_Article_IEq31.gif"></inline-graphic></alternatives></inline-formula>. An example of parallel K-mer encryption is depicted in Fig. <xref rid="Fig4" ref-type="fig">4</xref>.
<fig id="Fig4"><label>Fig. 4</label><caption><p>A detailed example to how multiple K-mers are encoded into vectors in parallel. This figure depicts how K-mers are divided into small blocks and then encrypted to vectors. In this example, two 6-mers <italic>K</italic><sup>(0)</sup>=<italic>C</italic><italic>A</italic><italic>T</italic><italic>C</italic><italic>A</italic><italic>T</italic> and <italic>K</italic><sup>(1)</sup>=<italic>C</italic><italic>A</italic><italic>T</italic><italic>G</italic><italic>T</italic><italic>A</italic> are encoded into <italic>B</italic>=3 blocks each of size <italic>L</italic>=2 to reduce the size of ciphertext space. Here, the value of slots is a power of 2 bounded by (4<sup>2</sup>)·2. The subscript <italic>b</italic> of <inline-formula id="IEq32"><alternatives><tex-math id="M69">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\vec {v}_{b}$\end{document}</tex-math><mml:math id="M70"><mml:msub><mml:mrow><mml:mover accent="true"><mml:mrow><mml:mi>v</mml:mi></mml:mrow><mml:mo>→</mml:mo></mml:mover></mml:mrow><mml:mrow><mml:mi>b</mml:mi></mml:mrow></mml:msub></mml:math><inline-graphic xlink:href="12864_2019_5473_Article_IEq32.gif"></inline-graphic></alternatives></inline-formula> indicates the index of blocks encoded starting from 0. The values of elements in the vectors are indicators to <inline-formula id="IEq33"><alternatives><tex-math id="M71">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$K^{n}[b]= \frac {i-n}{2}$\end{document}</tex-math><mml:math id="M72"><mml:msup><mml:mrow><mml:mi>K</mml:mi></mml:mrow><mml:mrow><mml:mi>n</mml:mi></mml:mrow></mml:msup><mml:mo>[</mml:mo><mml:mi>b</mml:mi><mml:mo>]</mml:mo><mml:mo>=</mml:mo><mml:mfrac><mml:mrow><mml:mi>i</mml:mi><mml:mo>−</mml:mo><mml:mi>n</mml:mi></mml:mrow><mml:mrow><mml:mn>2</mml:mn></mml:mrow></mml:mfrac></mml:math><inline-graphic xlink:href="12864_2019_5473_Article_IEq33.gif"></inline-graphic></alternatives></inline-formula>. In this sense, <inline-formula id="IEq34"><alternatives><tex-math id="M73">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\vec {v}_{0}[16]$\end{document}</tex-math><mml:math id="M74"><mml:msub><mml:mrow><mml:mover accent="true"><mml:mrow><mml:mi>v</mml:mi></mml:mrow><mml:mo>→</mml:mo></mml:mover></mml:mrow><mml:mrow><mml:mn>0</mml:mn></mml:mrow></mml:msub><mml:mo>[</mml:mo><mml:mn>16</mml:mn><mml:mo>]</mml:mo></mml:math><inline-graphic xlink:href="12864_2019_5473_Article_IEq34.gif"></inline-graphic></alternatives></inline-formula>, <inline-formula id="IEq35"><alternatives><tex-math id="M75">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\vec {v}_{0}[17]$\end{document}</tex-math><mml:math id="M76"><mml:msub><mml:mrow><mml:mover accent="true"><mml:mrow><mml:mi>v</mml:mi></mml:mrow><mml:mo>→</mml:mo></mml:mover></mml:mrow><mml:mrow><mml:mn>0</mml:mn></mml:mrow></mml:msub><mml:mo>[</mml:mo><mml:mn>17</mml:mn><mml:mo>]</mml:mo></mml:math><inline-graphic xlink:href="12864_2019_5473_Article_IEq35.gif"></inline-graphic></alternatives></inline-formula>, <inline-formula id="IEq36"><alternatives><tex-math id="M77">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\vec {v}_{1}[52]$\end{document}</tex-math><mml:math id="M78"><mml:msub><mml:mrow><mml:mover accent="true"><mml:mrow><mml:mi>v</mml:mi></mml:mrow><mml:mo>→</mml:mo></mml:mover></mml:mrow><mml:mrow><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo>[</mml:mo><mml:mn>52</mml:mn><mml:mo>]</mml:mo></mml:math><inline-graphic xlink:href="12864_2019_5473_Article_IEq36.gif"></inline-graphic></alternatives></inline-formula>, <inline-formula id="IEq37"><alternatives><tex-math id="M79">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\vec {v}_{1}[57]$\end{document}</tex-math><mml:math id="M80"><mml:msub><mml:mrow><mml:mover accent="true"><mml:mrow><mml:mi>v</mml:mi></mml:mrow><mml:mo>→</mml:mo></mml:mover></mml:mrow><mml:mrow><mml:mn>1</mml:mn></mml:mrow></mml:msub><mml:mo>[</mml:mo><mml:mn>57</mml:mn><mml:mo>]</mml:mo></mml:math><inline-graphic xlink:href="12864_2019_5473_Article_IEq37.gif"></inline-graphic></alternatives></inline-formula>, <inline-formula id="IEq38"><alternatives><tex-math id="M81">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\vec {v}_{2}[12]$\end{document}</tex-math><mml:math id="M82"><mml:msub><mml:mrow><mml:mover accent="true"><mml:mrow><mml:mi>v</mml:mi></mml:mrow><mml:mo>→</mml:mo></mml:mover></mml:mrow><mml:mrow><mml:mn>2</mml:mn></mml:mrow></mml:msub><mml:mo>[</mml:mo><mml:mn>12</mml:mn><mml:mo>]</mml:mo></mml:math><inline-graphic xlink:href="12864_2019_5473_Article_IEq38.gif"></inline-graphic></alternatives></inline-formula>, and <inline-formula id="IEq39"><alternatives><tex-math id="M83">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\vec {v}_{2}[49]$\end{document}</tex-math><mml:math id="M84"><mml:msub><mml:mrow><mml:mover accent="true"><mml:mrow><mml:mi>v</mml:mi></mml:mrow><mml:mo>→</mml:mo></mml:mover></mml:mrow><mml:mrow><mml:mn>2</mml:mn></mml:mrow></mml:msub><mml:mo>[</mml:mo><mml:mn>49</mml:mn><mml:mo>]</mml:mo></mml:math><inline-graphic xlink:href="12864_2019_5473_Article_IEq39.gif"></inline-graphic></alternatives></inline-formula> are 1’s. The vectors <inline-formula id="IEq40"><alternatives><tex-math id="M85">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$[\vec {v}_{b}]$\end{document}</tex-math><mml:math id="M86"><mml:mo>[</mml:mo><mml:msub><mml:mrow><mml:mover accent="true"><mml:mrow><mml:mi>v</mml:mi></mml:mrow><mml:mo>→</mml:mo></mml:mover></mml:mrow><mml:mrow><mml:mi>b</mml:mi></mml:mrow></mml:msub><mml:mo>]</mml:mo></mml:math><inline-graphic xlink:href="12864_2019_5473_Article_IEq40.gif"></inline-graphic></alternatives></inline-formula> are encrypted into polynomials <inline-formula id="IEq41"><alternatives><tex-math id="M87">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$[\vec {c}_{b}]$\end{document}</tex-math><mml:math id="M88"><mml:mo>[</mml:mo><mml:msub><mml:mrow><mml:mover accent="true"><mml:mrow><mml:mi>c</mml:mi></mml:mrow><mml:mo>→</mml:mo></mml:mover></mml:mrow><mml:mrow><mml:mi>b</mml:mi></mml:mrow></mml:msub><mml:mo>]</mml:mo></mml:math><inline-graphic xlink:href="12864_2019_5473_Article_IEq41.gif"></inline-graphic></alternatives></inline-formula> and then rotated by corresponding value of <inline-formula id="IEq42"><alternatives><tex-math id="M89">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$K_{ref}^{(m)}$\end{document}</tex-math><mml:math id="M90"><mml:msubsup><mml:mrow><mml:mi>K</mml:mi></mml:mrow><mml:mrow><mml:mtext mathvariant="italic">ref</mml:mtext></mml:mrow><mml:mrow><mml:mo>(</mml:mo><mml:mi>m</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:msubsup></mml:math><inline-graphic xlink:href="12864_2019_5473_Article_IEq42.gif"></inline-graphic></alternatives></inline-formula>. This rotation ensures that the first <italic>N</italic> blocks indicate the agreement of <italic>N</italic><italic>b</italic>-th block of K-mers and <italic>b</italic>-th block of <inline-formula id="IEq43"><alternatives><tex-math id="M91">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$K_{ref}^{(m)}$\end{document}</tex-math><mml:math id="M92"><mml:msubsup><mml:mrow><mml:mi>K</mml:mi></mml:mrow><mml:mrow><mml:mtext mathvariant="italic">ref</mml:mtext></mml:mrow><mml:mrow><mml:mo>(</mml:mo><mml:mi>m</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:msubsup></mml:math><inline-graphic xlink:href="12864_2019_5473_Article_IEq43.gif"></inline-graphic></alternatives></inline-formula>. Later, these values are multiplied in component-wise manner. Therefore, <inline-formula id="IEq44"><alternatives><tex-math id="M93">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\vec {d}[n]$\end{document}</tex-math><mml:math id="M94"><mml:mover accent="true"><mml:mrow><mml:mi>d</mml:mi></mml:mrow><mml:mo>→</mml:mo></mml:mover><mml:mo>[</mml:mo><mml:mi>n</mml:mi><mml:mo>]</mml:mo></mml:math><inline-graphic xlink:href="12864_2019_5473_Article_IEq44.gif"></inline-graphic></alternatives></inline-formula> indicates 1 if <italic>n</italic>-th K-mer agrees with <inline-formula id="IEq45"><alternatives><tex-math id="M95">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$K_{ref}^{(m)}$\end{document}</tex-math><mml:math id="M96"><mml:msubsup><mml:mrow><mml:mi>K</mml:mi></mml:mrow><mml:mrow><mml:mtext mathvariant="italic">ref</mml:mtext></mml:mrow><mml:mrow><mml:mo>(</mml:mo><mml:mi>m</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:msubsup></mml:math><inline-graphic xlink:href="12864_2019_5473_Article_IEq45.gif"></inline-graphic></alternatives></inline-formula> in all <italic>B</italic> blocks and 0 if any pair of blocks from both K-mers does not match</p></caption><graphic xlink:href="12864_2019_5473_Fig4_HTML" id="MO4"></graphic></fig></p></sec><sec id="Sec11"><title>Homomorphic equality test of K-mers</title><p>In the proposed system, encrypted K-mers are compared in homomorphic way to detect SNPs. The evaluation operation consists of following steps.</p><p><bold>Step 1:</bold> The HEAAN scheme supports the rotation operation on plaintext slots, i.e., it enables us to securely obtain an encryption of the shifted plaintext vector (<italic>w</italic><sub><italic>r</italic></sub>,…,<italic>w</italic><sub><italic>k</italic>−1</sub>,<italic>w</italic><sub>0</sub>,…,<italic>w</italic><sub><italic>r</italic>−1</sub>) from an encryption of (<italic>w</italic><sub>0</sub>,…,<italic>w</italic><sub><italic>k</italic>−1</sub>). We denote the rotation operation as <inline-formula id="IEq46"><alternatives><tex-math id="M97">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\texttt {Rotate}(\vec {c}; r)$\end{document}</tex-math><mml:math id="M98"><mml:mtext mathvariant="monospace">Rotate</mml:mtext><mml:mo>(</mml:mo><mml:mover accent="true"><mml:mrow><mml:mi>c</mml:mi></mml:mrow><mml:mo>→</mml:mo></mml:mover><mml:mo>;</mml:mo><mml:mi>r</mml:mi><mml:mo>)</mml:mo></mml:math><inline-graphic xlink:href="12864_2019_5473_Article_IEq46.gif"></inline-graphic></alternatives></inline-formula>. It outputs a ciphertext <inline-formula id="IEq47"><alternatives><tex-math id="M99">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\vec {c}_{r}$\end{document}</tex-math><mml:math id="M100"><mml:msub><mml:mrow><mml:mover accent="true"><mml:mrow><mml:mi>c</mml:mi></mml:mrow><mml:mo>→</mml:mo></mml:mover></mml:mrow><mml:mrow><mml:mi>r</mml:mi></mml:mrow></mml:msub></mml:math><inline-graphic xlink:href="12864_2019_5473_Article_IEq47.gif"></inline-graphic></alternatives></inline-formula> encrypting the rotated plaintext vector of <inline-formula id="IEq48"><alternatives><tex-math id="M101">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\vec {c}$\end{document}</tex-math><mml:math id="M102"><mml:mover accent="true"><mml:mrow><mml:mi>c</mml:mi></mml:mrow><mml:mo>→</mml:mo></mml:mover></mml:math><inline-graphic xlink:href="12864_2019_5473_Article_IEq48.gif"></inline-graphic></alternatives></inline-formula> by <italic>r</italic> positions. Define and compute
<disp-formula id="Equd"><alternatives><tex-math id="M103">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document} $${\vec{c}}_{b,m} = \texttt{Rotate}\left(\vec{c_{b}}; N\cdot K_{}{ref}^{(m)}[\!b]\right). $$ \end{document}</tex-math><mml:math id="M104"><mml:mrow><mml:msub><mml:mrow><mml:mover accent="true"><mml:mrow><mml:mi>c</mml:mi></mml:mrow><mml:mo>→</mml:mo></mml:mover></mml:mrow><mml:mrow><mml:mi>b</mml:mi><mml:mo>,</mml:mo><mml:mi>m</mml:mi></mml:mrow></mml:msub><mml:mo>=</mml:mo><mml:mtext mathvariant="monospace">Rotate</mml:mtext><mml:mfenced close=")" open="(" separators=""><mml:mrow><mml:mover accent="true"><mml:mrow><mml:msub><mml:mrow><mml:mi>c</mml:mi></mml:mrow><mml:mrow><mml:mi>b</mml:mi></mml:mrow></mml:msub></mml:mrow><mml:mo>→</mml:mo></mml:mover><mml:mo>;</mml:mo><mml:mi>N</mml:mi><mml:mo>·</mml:mo><mml:msub><mml:mrow><mml:mi>K</mml:mi></mml:mrow><mml:mrow></mml:mrow></mml:msub><mml:msup><mml:mrow><mml:mtext mathvariant="italic">ref</mml:mtext></mml:mrow><mml:mrow><mml:mo>(</mml:mo><mml:mi>m</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:msup><mml:mo>[</mml:mo><mml:mspace width="0.3em"></mml:mspace><mml:mi>b</mml:mi><mml:mo>]</mml:mo></mml:mrow></mml:mfenced><mml:mi>.</mml:mi></mml:mrow></mml:math><graphic xlink:href="12864_2019_5473_Article_Equd.gif" position="anchor"></graphic></alternatives></disp-formula></p><p>Note that for <italic>n</italic>∈[ <italic>N</italic>], <inline-formula id="IEq49"><alternatives><tex-math id="M105">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\vec {c}_{b,m}[\!n]$\end{document}</tex-math><mml:math id="M106"><mml:msub><mml:mrow><mml:mover accent="true"><mml:mrow><mml:mi>c</mml:mi></mml:mrow><mml:mo>→</mml:mo></mml:mover></mml:mrow><mml:mrow><mml:mi>b</mml:mi><mml:mo>,</mml:mo><mml:mi>m</mml:mi></mml:mrow></mml:msub><mml:mo>[</mml:mo><mml:mspace width="0.3em"></mml:mspace><mml:mi>n</mml:mi><mml:mo>]</mml:mo></mml:math><inline-graphic xlink:href="12864_2019_5473_Article_IEq49.gif"></inline-graphic></alternatives></inline-formula> is 1 if <italic>K</italic><sup>(<italic>n</italic>)</sup>[ <italic>b</italic>]=<italic>K</italic><italic>r</italic><italic>e</italic><italic>f</italic><sup>(<italic>m</italic>)</sup>[ <italic>b</italic>] and 0 otherwise.</p><p><bold>Step 2:</bold> Define and compute
<disp-formula id="Eque"><alternatives><tex-math id="M107">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document} $$\vec{d}_{m} = \prod_{b\in[B]}{\vec{c}_{b,m}}, $$ \end{document}</tex-math><mml:math id="M108"><mml:mrow><mml:msub><mml:mrow><mml:mover accent="true"><mml:mrow><mml:mi>d</mml:mi></mml:mrow><mml:mo>→</mml:mo></mml:mover></mml:mrow><mml:mrow><mml:mi>m</mml:mi></mml:mrow></mml:msub><mml:mo>=</mml:mo><mml:munder><mml:mrow><mml:mo mathsize="big">∏</mml:mo></mml:mrow><mml:mrow><mml:mi>b</mml:mi><mml:mo>∈</mml:mo><mml:mo>[</mml:mo><mml:mi>B</mml:mi><mml:mo>]</mml:mo></mml:mrow></mml:munder><mml:msub><mml:mrow><mml:mover accent="true"><mml:mrow><mml:mi>c</mml:mi></mml:mrow><mml:mo>→</mml:mo></mml:mover></mml:mrow><mml:mrow><mml:mi>b</mml:mi><mml:mo>,</mml:mo><mml:mi>m</mml:mi></mml:mrow></mml:msub><mml:mo>,</mml:mo></mml:mrow></mml:math><graphic xlink:href="12864_2019_5473_Article_Eque.gif" position="anchor"></graphic></alternatives></disp-formula> where <inline-formula id="IEq50"><alternatives><tex-math id="M109">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\prod $\end{document}</tex-math><mml:math id="M110"><mml:mo>∏</mml:mo></mml:math><inline-graphic xlink:href="12864_2019_5473_Article_IEq50.gif"></inline-graphic></alternatives></inline-formula> denotes component-wise multiplication. Note that for <italic>n</italic>∈[ <italic>N</italic>], <inline-formula id="IEq51"><alternatives><tex-math id="M111">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\vec {d}_{m}[\!n]$\end{document}</tex-math><mml:math id="M112"><mml:msub><mml:mrow><mml:mover accent="true"><mml:mrow><mml:mi>d</mml:mi></mml:mrow><mml:mo>→</mml:mo></mml:mover></mml:mrow><mml:mrow><mml:mi>m</mml:mi></mml:mrow></mml:msub><mml:mo>[</mml:mo><mml:mspace width="0.3em"></mml:mspace><mml:mi>n</mml:mi><mml:mo>]</mml:mo></mml:math><inline-graphic xlink:href="12864_2019_5473_Article_IEq51.gif"></inline-graphic></alternatives></inline-formula> is 1 if <italic>K</italic><sup>(<italic>n</italic>)</sup>=<italic>K</italic><italic>r</italic><italic>e</italic><italic>f</italic><sup>(<italic>m</italic>)</sup> and 0 otherwise.</p><p><bold>Step 3:</bold> Define and compute
<disp-formula id="Equf"><alternatives><tex-math id="M113">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document} $$\vec{d} = \sum_{m\in[L]}{\vec{d}_{m}}. $$ \end{document}</tex-math><mml:math id="M114"><mml:mrow><mml:mover accent="true"><mml:mrow><mml:mi>d</mml:mi></mml:mrow><mml:mo>→</mml:mo></mml:mover><mml:mo>=</mml:mo><mml:munder><mml:mrow><mml:mo mathsize="big">∑</mml:mo></mml:mrow><mml:mrow><mml:mi>m</mml:mi><mml:mo>∈</mml:mo><mml:mo>[</mml:mo><mml:mi>L</mml:mi><mml:mo>]</mml:mo></mml:mrow></mml:munder><mml:msub><mml:mrow><mml:mover accent="true"><mml:mrow><mml:mi>d</mml:mi></mml:mrow><mml:mo>→</mml:mo></mml:mover></mml:mrow><mml:mrow><mml:mi>m</mml:mi></mml:mrow></mml:msub><mml:mi>.</mml:mi></mml:mrow></mml:math><graphic xlink:href="12864_2019_5473_Article_Equf.gif" position="anchor"></graphic></alternatives></disp-formula></p><p>Note that for <italic>n</italic>∈[ <italic>N</italic>], <inline-formula id="IEq52"><alternatives><tex-math id="M115">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\vec {d}[\!n]$\end{document}</tex-math><mml:math id="M116"><mml:mover accent="true"><mml:mrow><mml:mi>d</mml:mi></mml:mrow><mml:mo>→</mml:mo></mml:mover><mml:mo>[</mml:mo><mml:mspace width="0.3em"></mml:mspace><mml:mi>n</mml:mi><mml:mo>]</mml:mo></mml:math><inline-graphic xlink:href="12864_2019_5473_Article_IEq52.gif"></inline-graphic></alternatives></inline-formula> is the number of <italic>m</italic> such that <italic>K</italic><sup>(<italic>n</italic>)</sup>[ <italic>b</italic>]=<italic>K</italic><italic>r</italic><italic>e</italic><italic>f</italic><sup>(<italic>m</italic>)</sup>[ <italic>b</italic>]. However, it is very unlikely <italic>K</italic><italic>r</italic><italic>e</italic><italic>f</italic> to have multiple identical subsequences. We may assume that <italic>K</italic><italic>r</italic><italic>e</italic><italic>f</italic> does not have multiple identical subsequences. If this is the case, <inline-formula id="IEq53"><alternatives><tex-math id="M117">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\vec {d}[\!n]$\end{document}</tex-math><mml:math id="M118"><mml:mover accent="true"><mml:mrow><mml:mi>d</mml:mi></mml:mrow><mml:mo>→</mml:mo></mml:mover><mml:mo>[</mml:mo><mml:mspace width="0.3em"></mml:mspace><mml:mi>n</mml:mi><mml:mo>]</mml:mo></mml:math><inline-graphic xlink:href="12864_2019_5473_Article_IEq53.gif"></inline-graphic></alternatives></inline-formula> has the value 1 if <italic>K</italic><sup>(<italic>n</italic>)</sup>=<italic>K</italic><italic>r</italic><italic>e</italic><italic>f</italic><sup>(<italic>m</italic>)</sup> for some <italic>m</italic> and 0 if not.</p><p><bold>Step 4:</bold> Define and compute
<disp-formula id="Equg"><alternatives><tex-math id="M119">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document} $$\vec{c_{res}} = \sum_{n\in[N]}{ \texttt{Rotate}\left(\vec{d}; n\right)}. $$ \end{document}</tex-math><mml:math id="M120"><mml:mrow><mml:mover accent="true"><mml:mrow><mml:msub><mml:mrow><mml:mi>c</mml:mi></mml:mrow><mml:mrow><mml:mtext mathvariant="italic">res</mml:mtext></mml:mrow></mml:msub></mml:mrow><mml:mo>→</mml:mo></mml:mover><mml:mo>=</mml:mo><mml:munder><mml:mrow><mml:mo mathsize="big">∑</mml:mo></mml:mrow><mml:mrow><mml:mi>n</mml:mi><mml:mo>∈</mml:mo><mml:mo>[</mml:mo><mml:mi>N</mml:mi><mml:mo>]</mml:mo></mml:mrow></mml:munder><mml:mtext mathvariant="monospace">Rotate</mml:mtext><mml:mfenced close=")" open="(" separators=""><mml:mrow><mml:mover accent="true"><mml:mrow><mml:mi>d</mml:mi></mml:mrow><mml:mo>→</mml:mo></mml:mover><mml:mo>;</mml:mo><mml:mi>n</mml:mi></mml:mrow></mml:mfenced><mml:mi>.</mml:mi></mml:mrow></mml:math><graphic xlink:href="12864_2019_5473_Article_Equg.gif" position="anchor"></graphic></alternatives></disp-formula></p><p>Note that the 0th component of <inline-formula id="IEq54"><alternatives><tex-math id="M121">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\vec {c_{res}}$\end{document}</tex-math><mml:math id="M122"><mml:mover accent="true"><mml:mrow><mml:msub><mml:mrow><mml:mi>c</mml:mi></mml:mrow><mml:mrow><mml:mtext mathvariant="italic">res</mml:mtext></mml:mrow></mml:msub></mml:mrow><mml:mo>→</mml:mo></mml:mover></mml:math><inline-graphic xlink:href="12864_2019_5473_Article_IEq54.gif"></inline-graphic></alternatives></inline-formula> is the encryption of what we wanted: the number of <italic>n</italic> satisfying <italic>K</italic><sup>(<italic>n</italic>)</sup>=<italic>K</italic><italic>r</italic><italic>e</italic><italic>f</italic><sup>(<italic>m</italic>)</sup> for some <italic>m</italic>∈[<italic>L</italic>]. The fact can be seen by an easy computation below.
<disp-formula id="Equh"><alternatives><tex-math id="M123">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document} $$\vec{c_{res}}[\!0] = \sum_{n\in[N]}{ \texttt{Rotate}\left(\vec{d}; n\right)[\!0]} = \sum_{n\in[N]}{\vec{d}[\!n]} $$ \end{document}</tex-math><mml:math id="M124"><mml:mrow><mml:mover accent="true"><mml:mrow><mml:msub><mml:mrow><mml:mi>c</mml:mi></mml:mrow><mml:mrow><mml:mtext mathvariant="italic">res</mml:mtext></mml:mrow></mml:msub></mml:mrow><mml:mo>→</mml:mo></mml:mover><mml:mo>[</mml:mo><mml:mspace width="0.3em"></mml:mspace><mml:mn>0</mml:mn><mml:mo>]</mml:mo><mml:mo>=</mml:mo><mml:munder><mml:mrow><mml:mo mathsize="big">∑</mml:mo></mml:mrow><mml:mrow><mml:mi>n</mml:mi><mml:mo>∈</mml:mo><mml:mo>[</mml:mo><mml:mi>N</mml:mi><mml:mo>]</mml:mo></mml:mrow></mml:munder><mml:mtext mathvariant="monospace">Rotate</mml:mtext><mml:mfenced close=")" open="(" separators=""><mml:mrow><mml:mover accent="true"><mml:mrow><mml:mi>d</mml:mi></mml:mrow><mml:mo>→</mml:mo></mml:mover><mml:mo>;</mml:mo><mml:mi>n</mml:mi></mml:mrow></mml:mfenced><mml:mo>[</mml:mo><mml:mspace width="0.3em"></mml:mspace><mml:mn>0</mml:mn><mml:mo>]</mml:mo><mml:mo>=</mml:mo><mml:munder><mml:mrow><mml:mo mathsize="big">∑</mml:mo></mml:mrow><mml:mrow><mml:mi>n</mml:mi><mml:mo>∈</mml:mo><mml:mo>[</mml:mo><mml:mi>N</mml:mi><mml:mo>]</mml:mo></mml:mrow></mml:munder><mml:mover accent="true"><mml:mrow><mml:mi>d</mml:mi></mml:mrow><mml:mo>→</mml:mo></mml:mover><mml:mo>[</mml:mo><mml:mspace width="0.3em"></mml:mspace><mml:mi>n</mml:mi><mml:mo>]</mml:mo></mml:mrow></mml:math><graphic xlink:href="12864_2019_5473_Article_Equh.gif" position="anchor"></graphic></alternatives></disp-formula></p></sec></sec><sec id="Sec16" sec-type="results"><title>Results</title><sec id="Sec17"><title>Panel scheme accuracy</title><p>As mentioned in the subsection “False positive/negative errors”, the false positive risk of our model can be controlled to some extent by setting a PDT parameter. Therefore, we focused on evaluating the false negative risk by performing an additional experiment. In our model, false negative occurs if a patient has individual sequence variations near the panel SNPs. Unlike the conventional unencrypted mutation-calling procedure allowing few mismatches, our model depends on the equality test process, which always needs perfect matching nearby the panel SNPs. Therefore, even a single unexpected variation neighboring a panel SNP can sabotage the calling of the residue. Considering the prevalent somatic mutations observed in cancer patients, we can consider it as a major source of risk. Therefore, we tested the false negative risk caused by somatic mutations by using residues having mutations in actual breast cancer patients, where the data is provided by TCGA BRCA [<xref ref-type="bibr" rid="CR40">40</xref>]. By this test, we estimated the empirical probability of false negative risk in various experimental conditions.</p><p>We collected 116,607 somatic mutations from TCGA BRCA dataset, then computed the distribution of pairwise distances between two mutations in terms of chromosomal positions. The goal of this test is to estimate the probability that any two mutations are located in proximity by chance. We set the threshold of proximity as 32 bp, which requires at least 32 bp as K-mer size to avoid false positive SNP calling. We will discuss about K-mer size later in detail. For now, the total number of all possible SNP pairs is calculated as follows.
<disp-formula id="Equi"><alternatives><tex-math id="M125">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document} $${{116,607}\choose 2} = {6,798,537,921} $$ \end{document}</tex-math><mml:math id="M126"><mml:mrow><mml:mfenced close=")" open="(" separators=""><mml:mfrac linethickness="0"><mml:mrow><mml:mn>116</mml:mn><mml:mo>,</mml:mo><mml:mn>607</mml:mn></mml:mrow><mml:mrow><mml:mn>2</mml:mn></mml:mrow></mml:mfrac></mml:mfenced><mml:mo>=</mml:mo><mml:mn>6</mml:mn><mml:mo>,</mml:mo><mml:mn>798</mml:mn><mml:mo>,</mml:mo><mml:mn>537</mml:mn><mml:mo>,</mml:mo><mml:mn>921</mml:mn></mml:mrow></mml:math><graphic xlink:href="12864_2019_5473_Article_Equi.gif" position="anchor"></graphic></alternatives></disp-formula> and thus the probability <italic>P</italic> of a panel with <italic>N</italic> SNP residues having at least a SNP pair that exists within 32-mer is
<disp-formula id="Equ1"><label>1</label><alternatives><tex-math id="M127">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document} $$ 1 - \left(1 - \frac{{1,308}}{{6,798,537,921}}\right)^{N\choose 2}. $$ \end{document}</tex-math><mml:math id="M128"><mml:mn>1</mml:mn><mml:mo>−</mml:mo><mml:msup><mml:mrow><mml:mfenced close=")" open="(" separators=""><mml:mrow><mml:mn>1</mml:mn><mml:mo>−</mml:mo><mml:mfrac><mml:mrow><mml:mn>1</mml:mn><mml:mo>,</mml:mo><mml:mn>308</mml:mn></mml:mrow><mml:mrow><mml:mn>6</mml:mn><mml:mo>,</mml:mo><mml:mn>798</mml:mn><mml:mo>,</mml:mo><mml:mn>537</mml:mn><mml:mo>,</mml:mo><mml:mn>921</mml:mn></mml:mrow></mml:mfrac></mml:mrow></mml:mfenced></mml:mrow><mml:mrow><mml:mfenced close=")" open="(" separators=""><mml:mfrac linethickness="0"><mml:mrow><mml:mi>N</mml:mi></mml:mrow><mml:mrow><mml:mn>2</mml:mn></mml:mrow></mml:mfrac></mml:mfenced></mml:mrow></mml:msup><mml:mi>.</mml:mi></mml:math><graphic xlink:href="12864_2019_5473_Article_Equ1.gif" position="anchor"></graphic></alternatives></disp-formula></p><p>Table <xref rid="Tab1" ref-type="table">1</xref> shows the probability of false negative risk calculated by aforementioned formula (Eq. <xref rid="Equ1" ref-type="">1</xref>). The result indicates that even though the risk gradually increases as the size of panels grows, the false positive risk still remains insignificant even when it reaches to 100 residues. It means that our model can handle panels having large size without significant false negative risk.
<table-wrap id="Tab1"><label>Table 1</label><caption><p>Probability P of two SNPs residing in a 32-mer given N SNP residues</p></caption><table frame="hsides" rules="groups"><thead><tr><th align="left"><italic>N</italic></th><th align="left"><italic>P</italic> (%)</th></tr></thead><tbody><tr><td align="left">10</td><td align="left">0.00087</td></tr><tr><td align="left">20</td><td align="left">0.0037</td></tr><tr><td align="left">30</td><td align="left">0.0084</td></tr><tr><td align="left">40</td><td align="left">0.015</td></tr><tr><td align="left">50</td><td align="left">0.024</td></tr><tr><td align="left">60</td><td align="left">0.034</td></tr><tr><td align="left">70</td><td align="left">0.046</td></tr><tr><td align="left">80</td><td align="left">0.060</td></tr><tr><td align="left">90</td><td align="left">0.070</td></tr><tr><td align="left">100</td><td align="left">0.095</td></tr></tbody></table><table-wrap-foot><p>N indicates the number of residues selected from 116,607 somatic mutations. P indicates the probability that any two residues are located in 32 bp window. Note that P still remains insignificant even when the N reaches to 100. All numbers are rounded down to 2 significant figures</p></table-wrap-foot></table-wrap></p><p>As shown in Table <xref rid="Tab1" ref-type="table">1</xref>, the false negative risk of our model caused by somatic mutation is not significant. Even though there can be other source of risks that we did not consider such as germline variations, the chance of false negative caused by germline variation is relatively small compared to the one caused by somatic mutation [<xref ref-type="bibr" rid="CR41">41</xref><italic>,</italic><xref ref-type="bibr" rid="CR42">42</xref>]. Although a SNP residue of interest has a sequence variation in its flanking sequence, there are other adjacent K-mers that might still detect the residue. Only when more than two sequence variations are simultaneously occurred and located in K bp on both sides of the panel residue, the scheme completely fails. Hence the actual hazard of false negative is expected to be small in practice. Moreover, even if the false negative error occurs, the system can still know the occurrence of it because there would be no positive count for that SNP residue at all. Therefore, the model can easily detect false negative errors and can recommend to avoid fatal situations.</p></sec><sec id="Sec18"><title>Running time of the proposed panel scheme</title><p>In our model, one of the major factors that determine running time is the PDT level. As mentioned, PDT level indicates the tolerance for mismatches. Using a higher PDT guarantees less false positive risk, but it increases the length of K-mer i.e., K, which in turn increases the running time. Especially, the homomorphic equality test procedure is significantly affected by K. As shown in Table <xref rid="Tab2" ref-type="table">2</xref>, the running time of homomorphic equality test has almost linear relationship with K (Pearson correlation coefficient of 0.99).
<table-wrap id="Tab2"><label>Table 2</label><caption><p>Length K of product K-mers, time needed to encrypt K-mers and perform equality test to detect SNPs</p></caption><table frame="hsides" rules="groups"><thead><tr><th align="left">N</th><th align="left">PDT</th><th align="left">K</th><th align="left">K-mer encryption (ms)</th><th align="left">equality test (sec)</th></tr></thead><tbody><tr><td align="left">10</td><td align="left">0</td><td align="left">10</td><td align="left">45</td><td align="left">82</td></tr><tr><td align="left">10</td><td align="left">1</td><td align="left">13</td><td align="left">56</td><td align="left">141</td></tr><tr><td align="left">10</td><td align="left">2</td><td align="left">17</td><td align="left">92</td><td align="left">300</td></tr><tr><td align="left">10</td><td align="left">3</td><td align="left">20</td><td align="left">101</td><td align="left">418</td></tr><tr><td align="left">10</td><td align="left">4</td><td align="left">24</td><td align="left">119</td><td align="left">603</td></tr></tbody></table><table-wrap-foot><p>N indicates the number of SNP residues included in the panel. PDT is the mismatch tolerance, where higher PDT indicates lower false positive risks. The table shows how the changes in PDT and K affect the running time. The result indicates that larger K results in longer running time to encrypt and test equality</p></table-wrap-foot></table-wrap></p><p>With 10 SNP residues and PDT level 4, K is found to be 24 (Table <xref rid="Tab3" ref-type="table">3</xref>). In detail, we have 480 24-mers in the user’s K-mer set and 960 24-mers in the panel K-mer set. The comparison of the two sets took 603 seconds (Table <xref rid="Tab2" ref-type="table">2</xref>). Considering that the PDT level 4 with finding K-mers is overgenerous, despite the wide genome variation our work shows that homomorphic encryption can be computationally feasible to apply on SNP panel scheme.
<table-wrap id="Tab3"><label>Table 3</label><caption><p>The estimated values of K given the number of SNP residues and PDT levels</p></caption><table frame="hsides" rules="groups"><thead><tr><th align="left"></th><th align="left"><italic>N</italic>=10</th><th align="left">20</th><th align="left">30</th><th align="left">40</th><th align="left">50</th><th align="left">60</th><th align="left">70</th><th align="left">80</th><th align="left">90</th><th align="left">100</th></tr></thead><tbody><tr><td align="left">PDT = 0</td><td align="left">10</td><td align="left">21</td><td align="left">21</td><td align="left">21</td><td align="left">21</td><td align="left">21</td><td align="left">21</td><td align="left">21</td><td align="left">21</td><td align="left">21</td></tr><tr><td align="left">1</td><td align="left">13</td><td align="left">23</td><td align="left">23</td><td align="left">23</td><td align="left">23</td><td align="left">23</td><td align="left">23</td><td align="left">24</td><td align="left">24</td><td align="left">24</td></tr><tr><td align="left">2</td><td align="left">17</td><td align="left">26</td><td align="left">26</td><td align="left">26</td><td align="left">26</td><td align="left">26</td><td align="left">26</td><td align="left">26</td><td align="left">26</td><td align="left">26</td></tr><tr><td align="left">3</td><td align="left">20</td><td align="left">27</td><td align="left">27</td><td align="left">27</td><td align="left">27</td><td align="left">27</td><td align="left">27</td><td align="left">28</td><td align="left">28</td><td align="left">28</td></tr><tr><td align="left">4</td><td align="left">24</td><td align="left">32</td><td align="left">32</td><td align="left">32</td><td align="left">32</td><td align="left">32</td><td align="left">32</td><td align="left">32</td><td align="left">32</td><td align="left">32</td></tr></tbody></table><table-wrap-foot><p>PDT indicates mismatch tolerance and N indicates the panel size. The number inside of table is value of K, which is the minimal length of K-mer for the model. Usually, larger K requires longer running time and more resources. The table shows how the changes in PDT and N affect the value of K. The result indicates that K is positively correlated with both factors respectively</p></table-wrap-foot></table-wrap></p></sec><sec id="Sec19"><title>Panel design guideline for scheme feasibility</title><p>The practicality of our scheme relies on shorter K-mers, and minimizing K is one of our best interest. As mentioned in the Method section, K increases as (1) the number of SNP residues included in panels grow and (2) the higher PDT level required. The estimated value of K with the simulated data is shown below (Table <xref rid="Tab3" ref-type="table">3</xref>).</p><p>However, the values of K tend to saturate very quickly. There is ignorable difference among the values of K along the number of SNP residues from 20 to 100. The saturating tendency implies that our scheme is likely to be effective even regarding the panel with large number of SNP residues. In the data preprocessing stage, we have discarded SNP residues with redundant flanking sequences to prevent very large number of K. Table <xref rid="Tab4" ref-type="table">4</xref> shows the number of discarded SNP residues with respect to the initial number of SNP residues of panels. Note that the panels do not drop many SNP residues as their number grows. That is, with carefully chosen SNP residues not to share the redundant flanking sequences, some value roughly around 32 for K would be long enough for any practical number of SNP residues. The value drops to about 21 when PDT is not concerned. Considering the trade-offs these parameters can provide, any user can fully avail oneself to our SNP panel scheme under most circumstances.
<table-wrap id="Tab4"><label>Table 4</label><caption><p>The number of discarded and remaining panels given the original number of SNP residues randomly selected. N indicates the number of residues in each panel</p></caption><table frame="hsides" rules="groups"><thead><tr><th align="left"></th><th align="left"><italic>N</italic>=10</th><th align="left">20</th><th align="left">30</th><th align="left">40</th><th align="left">50</th><th align="left">60</th><th align="left">70</th><th align="left">80</th><th align="left">90</th><th align="left">100</th></tr></thead><tbody><tr><td align="left">Total</td><td align="left">10</td><td align="left">20</td><td align="left">30</td><td align="left">40</td><td align="left">50</td><td align="left">60</td><td align="left">70</td><td align="left">80</td><td align="left">90</td><td align="left">100</td></tr><tr><td align="left">Discarded</td><td align="left">0</td><td align="left">0</td><td align="left">2</td><td align="left">3</td><td align="left">5</td><td align="left">6</td><td align="left">7</td><td align="left">9</td><td align="left">9</td><td align="left">13</td></tr><tr><td align="left">Remaining</td><td align="left">10</td><td align="left">20</td><td align="left">28</td><td align="left">37</td><td align="left">45</td><td align="left">54</td><td align="left">63</td><td align="left">71</td><td align="left">81</td><td align="left">87</td></tr><tr><td align="left">Survival rate</td><td align="left">1.0</td><td align="left">1.0</td><td align="left">.93</td><td align="left">.93</td><td align="left">.90</td><td align="left">.90</td><td align="left">.90</td><td align="left">.89</td><td align="left">.90</td><td align="left">.87</td></tr></tbody></table><table-wrap-foot><p>Discarded indicates the number of residues abandoned during preprocessing. During preprocessing, the model checks if there are residues having too much similarity in their neighboring sequences. If two residues have too much similarity in neighboring sequence contexts, they cannot be distinguished by NGS-seq due to the limited read length. Table shows that remaining rate is consistent even when N reaches 100, which indicates that the model can handle panels with large size without losing too much residues</p></table-wrap-foot></table-wrap></p></sec></sec><sec id="Sec20" sec-type="conclusion"><title>Conclusions</title><p>Although homomorphic encryption has a good potential for protecting security of data, the encryption method combined with the current computer systems has not achieved practical performance to fully utilize the power. In the field of genomics, the usage of homomorphic encryption has been mostly limited to querying aggregate or annotated data, requiring the preprocessing of data. However, to preprocess the genomic data, the raw genome sequence should be reveled without adequate protection, thus more reliable scheme for protecting the genome information is much needed. In addition, the SNP panel at the hospital should be protected. In this paper, we propose a secure SNP panel scheme that protects both the user’s genome information and the SNP panel information owned by the hospitals. Since the current homomorphic encryption technologies are not computationally efficient, it is not trivial to develop a secure SNP panel scheme that can be used in reality. By chunking the part of genome down into K-mers, we have minimized the size of ciphertext space and overcome the current inefficiency of the homomorphic encryption. The scheme has yet many further possible improvements such as parallel processing and new algorithmic techniques. We expect our method to protect the raw sequence from possible threats and further return the control of genomic data to its owner, and at the same time protect the hospital’s SNP panel assets safely. However, we emphasize that our method shows the feasibility of our scheme. Applying our proposed method to hospitals will certainly require extensive evaluation and improvement.</p></sec></body><back><glossary><title>Abbreviations</title><def-list><def-item><term>BRCA</term><def><p>Breast cancer susceptibility gene</p></def></def-item><def-item><term>DNA</term><def><p>Deoxyribonucleic acid</p></def></def-item><def-item><term>GWAS</term><def><p>Genome-wide association study</p></def></def-item><def-item><term>HEAAN</term><def><p>Homomorphic encryption for arithmetic of approximate numbers</p></def></def-item><def-item><term>LWE</term><def><p>Learning with error</p></def></def-item><def-item><term>NIH</term><def><p>National institutes of health</p></def></def-item><def-item><term>PDT</term><def><p>Point deviation tolerance</p></def></def-item><def-item><term>RLWE</term><def><p>Ring-learning with error</p></def></def-item><def-item><term>SIMD</term><def><p>Single instruction multiple data</p></def></def-item><def-item><term>SNP</term><def><p>Single-nucleotide polymorphism</p></def></def-item><def-item><term>TCGA</term><def><p>The cancer genome atlas</p></def></def-item><def-item><term>UCSC</term><def><p>University of California, Santa Cruz</p></def></def-item><def-item><term>US</term><def><p>United states</p></def></def-item></def-list></glossary><fn-group><fn><p><bold>Availability of data and materials</bold></p><p>The source data for simulating panels can be downloaded from <ext-link ext-link-type="uri" xlink:href="https://genome.ucsc.edu/">https://genome.ucsc.edu/</ext-link>. The sequencing reads simulator can be downloaded from <ext-link ext-link-type="uri" xlink:href="https://github.com/lh3/wgsim">https://github.com/lh3/wgsim</ext-link>and its parameters are described in the Method section. HEAAN library can be downloaded from <ext-link ext-link-type="uri" xlink:href="https://github.com/snucrypto/HEAAN">https://github.com/snucrypto/HEAAN</ext-link>. The data used to study somatic mutations can be downloaded from <ext-link ext-link-type="uri" xlink:href="https://portal.gdc.cancer.gov/projects/TCGA-BRCA">https://portal.gdc.cancer.gov/projects/TCGA-BRCA</ext-link>.</p></fn></fn-group><ack><title>Acknowledgements</title><p>Authors are grateful to anonymous reviewers for their useful comments on the manuscript.</p><sec id="d29e4699"><title>Funding</title><p>This research is supported by National Research Foundation of Korea (NRF) funded by the Ministry of Science, ICT (No. NRF-2017M3C4A7065887), The Collaborative Genome Program for Fostering New Post-Genome Industry of the National Research Foundation (NRF) funded by the Ministry of Science and ICT (MSIT) (No. NRF-2014M3C9A3063541), A grant of the Korea Health Technology R&D Project through the Korea Health Industry Development Institute (KHIDI), funded by the Ministry of Health & Welfare, Republic of Korea (grant number: HI15C3224), and Institute for Information & communications Technology Promotion (IITP) grant funded by the Korea government (MSIP) (B0717-16-0098, Development of homomorphic encryption for DNA analysis and biometry authentication). The publication cost will be paid by the Seoul National University Office of Research.</p></sec><sec id="d29e4704"><title>About this supplement</title><p>This article has been published as part of <italic>BMC Genomics Volume 20 Supplement 2, 2019: Selected articles from the 17th Asia Pacific Bioinformatics Conference (APBC 2019): genomics</italic>. The full contents of the supplement are available online at <ext-link ext-link-type="uri" xlink:href="https://bmcgenomics.biomedcentral.com/articles/supplements/volume-20-supplement-2">https://bmcgenomics.biomedcentral.com/articles/supplements/volume-20-supplement-2</ext-link>.</p></sec></ack><notes notes-type="author-contribution"><title>Authors’ contributions</title><p>SK conceived of the presented idea. SP designed the algorithm to find K with support from SS. MK processed the experimental data. SH and KH designed the algorithm for K-mer equality test with support from KL. SP conducted the experiment. SP wrote the manuscript with support from MK and SH. SK and JC supervised the project. All authors read and approved the final manuscript.</p></notes><notes notes-type="COI-statement"><sec><title>Ethics approval and consent to participate</title><p>Not applicable.</p></sec><sec><title>Consent for publication</title><p>Not applicable.</p></sec><sec><title>Competing interests</title><p>The authors declare that they have no competing interests.</p></sec><sec><title>Publisher’s Note</title><p>Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.</p></sec></notes><ref-list id="Bib1"><title>References</title><ref id="CR1"><label>1</label><element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Kandoth</surname><given-names>C</given-names></name><name><surname>McLellan</surname><given-names>MD</given-names></name><name><surname>Vandin</surname><given-names>F</given-names></name><name><surname>Ye</surname><given-names>K</given-names></name><name><surname>Niu</surname><given-names>B</given-names></name><name><surname>Lu</surname><given-names>C</given-names></name><etal></etal></person-group><article-title>Mutational landscape and significance across 12 major cancer types</article-title><source>Nature</source><year>2013</year><volume>502</volume><issue>7471</issue><fpage>333</fpage><pub-id pub-id-type="doi">10.1038/nature12634</pub-id><pub-id pub-id-type="pmid">24132290</pub-id></element-citation></ref><ref id="CR2"><label>2</label><element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Easton</surname><given-names>DF</given-names></name><name><surname>Pharoah</surname><given-names>PD</given-names></name><name><surname>Antoniou</surname><given-names>AC</given-names></name><name><surname>Tischkowitz</surname><given-names>M</given-names></name><name><surname>Tavtigian</surname><given-names>SV</given-names></name><name><surname>Nathanson</surname><given-names>KL</given-names></name><etal></etal></person-group><article-title>Gene-panel sequencing and the prediction of breast-cancer risk</article-title><source>N Engl J Med</source><year>2015</year><volume>372</volume><issue>23</issue><fpage>2243</fpage><lpage>57</lpage><pub-id pub-id-type="doi">10.1056/NEJMsr1501341</pub-id><pub-id pub-id-type="pmid">26014596</pub-id></element-citation></ref><ref id="CR3"><label>3</label><element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Spataro</surname><given-names>N</given-names></name><name><surname>Rodríguez</surname><given-names>JA</given-names></name><name><surname>Navarro</surname><given-names>A</given-names></name><name><surname>Bosch</surname><given-names>E</given-names></name></person-group><article-title>Properties of human disease genes and the role of genes linked to Mendelian disorders in complex disease aetiology</article-title><source>Hum Mol Genet</source><year>2017</year><volume>26</volume><issue>3</issue><fpage>489</fpage><lpage>500</lpage><pub-id pub-id-type="pmid">28053046</pub-id></element-citation></ref><ref id="CR4"><label>4</label><mixed-citation publication-type="other">ClinVar Database. Available from: <ext-link ext-link-type="uri" xlink:href="https://www.ncbi.nlm.nih.gov/clinvar/">https://www.ncbi.nlm.nih.gov/clinvar/</ext-link>.</mixed-citation></ref><ref id="CR5"><label>5</label><element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Lippert</surname><given-names>C</given-names></name><name><surname>Sabatini</surname><given-names>R</given-names></name><name><surname>Maher</surname><given-names>MC</given-names></name><name><surname>Kang</surname><given-names>EY</given-names></name><name><surname>Lee</surname><given-names>S</given-names></name><name><surname>Arikan</surname><given-names>O</given-names></name><etal></etal></person-group><article-title>Identification of individuals by trait prediction using whole-genome sequencing data</article-title><source>Proc Natl Acad Sci</source><year>2017</year><volume>114</volume><issue>38</issue><fpage>10166</fpage><lpage>71</lpage><pub-id pub-id-type="doi">10.1073/pnas.1711125114</pub-id><pub-id pub-id-type="pmid">28874526</pub-id></element-citation></ref><ref id="CR6"><label>6</label><mixed-citation publication-type="other">Gentry C, Boneh D. A fully homomorphic encryption scheme. vol. 20.Stanford University Stanford; 2009.</mixed-citation></ref><ref id="CR7"><label>7</label><element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Naveed</surname><given-names>M</given-names></name><name><surname>Ayday</surname><given-names>E</given-names></name><name><surname>Clayton</surname><given-names>EW</given-names></name><name><surname>Fellay</surname><given-names>J</given-names></name><name><surname>Gunter</surname><given-names>CA</given-names></name><name><surname>Hubaux</surname><given-names>JP</given-names></name><etal></etal></person-group><article-title>Privacy in the genomic era</article-title><source>ACM Comput Surv (CSUR)</source><year>2015</year><volume>48</volume><issue>1</issue><fpage>6</fpage><pub-id pub-id-type="doi">10.1145/2767007</pub-id></element-citation></ref><ref id="CR8"><label>8</label><element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Dowlin</surname><given-names>N</given-names></name><name><surname>Gilad-Bachrach</surname><given-names>R</given-names></name><name><surname>Laine</surname><given-names>K</given-names></name><name><surname>Lauter</surname><given-names>K</given-names></name><name><surname>Naehrig</surname><given-names>M</given-names></name><name><surname>Wernsing</surname><given-names>J</given-names></name></person-group><article-title>Manual for using homomorphic encryption for bioinformatics</article-title><source>Proc IEEE</source><year>2017</year><volume>105</volume><issue>3</issue><fpage>552</fpage><lpage>67</lpage></element-citation></ref><ref id="CR9"><label>9</label><element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Homer</surname><given-names>N</given-names></name><name><surname>Szelinger</surname><given-names>S</given-names></name><name><surname>Redman</surname><given-names>M</given-names></name><name><surname>Duggan</surname><given-names>D</given-names></name><name><surname>Tembe</surname><given-names>W</given-names></name><name><surname>Muehling</surname><given-names>J</given-names></name><etal></etal></person-group><article-title>Resolving individuals contributing trace amounts of DNA to highly complex mixtures using high-density SNP genotyping microarrays</article-title><source>PLoS Genet</source><year>2008</year><volume>4</volume><issue>8</issue><fpage>e1000167</fpage><pub-id pub-id-type="doi">10.1371/journal.pgen.1000167</pub-id><pub-id pub-id-type="pmid">18769715</pub-id></element-citation></ref><ref id="CR10"><label>10</label><mixed-citation publication-type="other">Wang R, Li YF, Wang X, Tang H, Zhou X. Learning your identity and disease from research papers: information leaks in genome wide association study. In: Proceedings of the 16th ACM conference on Computer and communications security. ACM: 2009. p. 534–544.</mixed-citation></ref><ref id="CR11"><label>11</label><element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Gymrek</surname><given-names>M</given-names></name><name><surname>McGuire</surname><given-names>AL</given-names></name><name><surname>Golan</surname><given-names>D</given-names></name><name><surname>Halperin</surname><given-names>E</given-names></name><name><surname>Erlich</surname><given-names>Y</given-names></name></person-group><article-title>Identifying personal genomes by surname inference</article-title><source>Science</source><year>2013</year><volume>339</volume><issue>6117</issue><fpage>321</fpage><lpage>4</lpage><pub-id pub-id-type="doi">10.1126/science.1229566</pub-id><pub-id pub-id-type="pmid">23329047</pub-id></element-citation></ref><ref id="CR12"><label>12</label><element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Shringarpure</surname><given-names>SS</given-names></name><name><surname>Bustamante</surname><given-names>CD</given-names></name></person-group><article-title>Privacy risks from genomic data-sharing beacons</article-title><source>Am J Hum Genet</source><year>2015</year><volume>97</volume><issue>5</issue><fpage>631</fpage><lpage>46</lpage><pub-id pub-id-type="doi">10.1016/j.ajhg.2015.09.010</pub-id><pub-id pub-id-type="pmid">26522470</pub-id></element-citation></ref><ref id="CR13"><label>13</label><element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Humbert</surname><given-names>M</given-names></name><name><surname>Huguenin</surname><given-names>K</given-names></name><name><surname>Hugonot</surname><given-names>J</given-names></name><name><surname>Ayday</surname><given-names>E</given-names></name><name><surname>Hubaux</surname><given-names>JP</given-names></name></person-group><article-title>De-anonymizing genomic databases using phenotypic traits</article-title><source>Proc Priv Enhancing Technol</source><year>2015</year><volume>2015</volume><issue>2</issue><fpage>99</fpage><lpage>114</lpage><pub-id pub-id-type="doi">10.1515/popets-2015-0020</pub-id></element-citation></ref><ref id="CR14"><label>14</label><element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Uhlerop</surname><given-names>C</given-names></name><collab>Slavković A</collab><name><surname>Fienberg</surname><given-names>SE</given-names></name></person-group><article-title>Privacy-preserving data sharing for genome-wide association studies</article-title><source>J Priv Confidentiality</source><year>2013</year><volume>5</volume><issue>1</issue><fpage>137</fpage></element-citation></ref><ref id="CR15"><label>15</label><mixed-citation publication-type="other">Johnson A, Shmatikov V. Privacy-preserving data exploration in genome-wide association studies. In: Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM: 2013. p. 1079–87.</mixed-citation></ref><ref id="CR16"><label>16</label><element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Yu</surname><given-names>F</given-names></name><name><surname>Fienberg</surname><given-names>SE</given-names></name><collab>Slavković AB</collab><name><surname>Uhler</surname><given-names>C</given-names></name></person-group><article-title>Scalable privacy-preserving data sharing methodology for genome-wide association studies</article-title><source>J Biomed Inform</source><year>2014</year><volume>50</volume><fpage>133</fpage><lpage>41</lpage><pub-id pub-id-type="doi">10.1016/j.jbi.2014.01.008</pub-id><pub-id pub-id-type="pmid">24509073</pub-id></element-citation></ref><ref id="CR17"><label>17</label><mixed-citation publication-type="other">Tramèr F, Huang Z, Hubaux JP, Ayday E. Differential privacy with bounded priors: reconciling utility and privacy in genome-wide association studies. In: Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security. ACM: 2015. p. 1286–97.</mixed-citation></ref><ref id="CR18"><label>18</label><element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Simmons</surname><given-names>S</given-names></name><name><surname>Berger</surname><given-names>B</given-names></name></person-group><article-title>Realizing privacy preserving genome-wide association studies</article-title><source>Bioinformatics</source><year>2016</year><volume>32</volume><issue>9</issue><fpage>1293</fpage><lpage>300</lpage><pub-id pub-id-type="doi">10.1093/bioinformatics/btw009</pub-id><pub-id pub-id-type="pmid">26769317</pub-id></element-citation></ref><ref id="CR19"><label>19</label><element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Simmons</surname><given-names>S</given-names></name><name><surname>Sahinalp</surname><given-names>C</given-names></name><name><surname>Berger</surname><given-names>B</given-names></name></person-group><article-title>Enabling privacy-preserving GWASs in heterogeneous human populations</article-title><source>Cell Syst</source><year>2016</year><volume>3</volume><issue>1</issue><fpage>54</fpage><lpage>61</lpage><pub-id pub-id-type="doi">10.1016/j.cels.2016.04.013</pub-id><pub-id pub-id-type="pmid">27453444</pub-id></element-citation></ref><ref id="CR20"><label>20</label><element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Canim</surname><given-names>M</given-names></name><name><surname>Kantarcioglu</surname><given-names>M</given-names></name><name><surname>Malin</surname><given-names>B</given-names></name></person-group><article-title>Secure management of biomedical data with cryptographic hardware</article-title><source>IEEE Trans Inf Technol Biomed</source><year>2012</year><volume>16</volume><issue>1</issue><fpage>166</fpage><lpage>75</lpage><pub-id pub-id-type="doi">10.1109/TITB.2011.2171701</pub-id><pub-id pub-id-type="pmid">22010157</pub-id></element-citation></ref><ref id="CR21"><label>21</label><element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Kamm</surname><given-names>L</given-names></name><name><surname>Bogdanov</surname><given-names>D</given-names></name><name><surname>Laur</surname><given-names>S</given-names></name><name><surname>Vilo</surname><given-names>J</given-names></name></person-group><article-title>A new way to protect privacy in large-scale genome-wide association studies</article-title><source>Bioinformatics</source><year>2013</year><volume>29</volume><issue>7</issue><fpage>886</fpage><lpage>93</lpage><pub-id pub-id-type="doi">10.1093/bioinformatics/btt066</pub-id><pub-id pub-id-type="pmid">23413435</pub-id></element-citation></ref><ref id="CR22"><label>22</label><element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Xie</surname><given-names>W</given-names></name><name><surname>Kantarcioglu</surname><given-names>M</given-names></name><name><surname>Bush</surname><given-names>WS</given-names></name><name><surname>Crawford</surname><given-names>D</given-names></name><name><surname>Denny</surname><given-names>JC</given-names></name><name><surname>Heatherly</surname><given-names>R</given-names></name><etal></etal></person-group><article-title>SecureMA: protecting participant privacy in genetic association meta-analysis</article-title><source>Bioinformatics</source><year>2014</year><volume>30</volume><issue>23</issue><fpage>3334</fpage><lpage>41</lpage><pub-id pub-id-type="doi">10.1093/bioinformatics/btu561</pub-id><pub-id pub-id-type="pmid">25147357</pub-id></element-citation></ref><ref id="CR23"><label>23</label><mixed-citation publication-type="other">Wang XS, Huang Y, Zhao Y, Tang H, Wang X, Bu D. Efficient genome-wide, privacy-preserving similar patient query based on private edit distance. In: Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security. ACM: 2015. p. 492–503.</mixed-citation></ref><ref id="CR24"><label>24</label><mixed-citation publication-type="other">Troncoso-Pastoriza JR, Katzenbeisser S, Celik M. Privacy preserving error resilient DNA searching through oblivious automata. In: Proceedings of the 14th ACM conference on Computer and communications security. ACM: 2007. p. 519–28.</mixed-citation></ref><ref id="CR25"><label>25</label><element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Kantarcioglu</surname><given-names>M</given-names></name><name><surname>Jiang</surname><given-names>W</given-names></name><name><surname>Liu</surname><given-names>Y</given-names></name><name><surname>Malin</surname><given-names>B</given-names></name></person-group><article-title>A cryptographic approach to securely share and query genomic sequences</article-title><source>IEEE Trans Inf Technol Biomed</source><year>2008</year><volume>12</volume><issue>5</issue><fpage>606</fpage><lpage>17</lpage><pub-id pub-id-type="doi">10.1109/TITB.2007.908465</pub-id><pub-id pub-id-type="pmid">18779075</pub-id></element-citation></ref><ref id="CR26"><label>26</label><mixed-citation publication-type="other">Ayday E, Raisaro JL, Hubaux JP, Rougemont J. Protecting and evaluating genomic privacy in medical tests and personalized medicine. In: Proceedings of the 12th ACM workshop on Workshop on privacy in the electronic society. ACM: 2013. p. 95–106.</mixed-citation></ref><ref id="CR27"><label>27</label><mixed-citation publication-type="other">Ayday E, Raisaro JL, Laren M, Jack P, Fellay J, Hubaux JP. Privacy-preserving computation of disease risk by using genomic, clinical, and environmental data. In: Proceedings of USENIX Security Workshop on Health Information Technologies (HealthTech’13). USENIX Security: 2013.</mixed-citation></ref><ref id="CR28"><label>28</label><mixed-citation publication-type="other">Kim M, Lauter K. Private genome analysis through homomorphic encryption. In: BMC medical informatics and decision making. vol. 15. BioMed Central: 2015. p. S3.</mixed-citation></ref><ref id="CR29"><label>29</label><mixed-citation publication-type="other">Lu WJ, Yamada Y, Sakuma J. Privacy-preserving genome-wide association studies on cloud environment using fully homomorphic encryption. In: BMC medical informatics and decision making. vol. 15. BioMed Central: 2015. p. S1.</mixed-citation></ref><ref id="CR30"><label>30</label><mixed-citation publication-type="other">Zhang Y, Dai W, Jiang X, Xiong H, Wang S. Foresee: Fully outsourced secure genome study based on homomorphic encryption. In: BMC medical informatics and decision making, vol. 15. BioMed Central: 2015. p. S5.</mixed-citation></ref><ref id="CR31"><label>31</label><element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Wang</surname><given-names>S</given-names></name><name><surname>Zhang</surname><given-names>Y</given-names></name><name><surname>Dai</surname><given-names>W</given-names></name><name><surname>Lauter</surname><given-names>K</given-names></name><name><surname>Kim</surname><given-names>M</given-names></name><name><surname>Tang</surname><given-names>Y</given-names></name><etal></etal></person-group><article-title>HEALER: Homomorphic computation of ExAct Logistic rEgRession for secure rare disease variants analysis in GWAS</article-title><source>Bioinformatics</source><year>2015</year><volume>32</volume><issue>2</issue><fpage>211</fpage><lpage>8</lpage><pub-id pub-id-type="pmid">26446135</pub-id></element-citation></ref><ref id="CR32"><label>32</label><element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Raisaro</surname><given-names>JL</given-names></name><name><surname>Choi</surname><given-names>G</given-names></name><name><surname>Pradervand</surname><given-names>S</given-names></name><name><surname>Colsenet</surname><given-names>R</given-names></name><name><surname>Jacquemont</surname><given-names>N</given-names></name><name><surname>Rosat</surname><given-names>N</given-names></name><name><surname>Mooser</surname><given-names>V</given-names></name><name><surname>Hubaux</surname><given-names>J-P</given-names></name></person-group><article-title>Protecting privacy and security of genomic data in I2B2 with homomorphic encryption and differential privacy</article-title><source>IEEE/ACM Trans Comput Biol Bioinforma</source><year>2018</year><volume>15</volume><issue>5</issue><fpage>1413</fpage><lpage>26</lpage></element-citation></ref><ref id="CR33"><label>33</label><element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Jagadeesh</surname><given-names>KA</given-names></name><name><surname>Wu</surname><given-names>DJ</given-names></name><name><surname>Birgmeier</surname><given-names>JA</given-names></name><name><surname>Boneh</surname><given-names>D</given-names></name><name><surname>Bejerano</surname><given-names>G</given-names></name></person-group><article-title>Deriving genomic diagnoses without revealing patient genomes</article-title><source>Science</source><year>2017</year><volume>357</volume><issue>6352</issue><fpage>692</fpage><lpage>5</lpage><pub-id pub-id-type="doi">10.1126/science.aam9710</pub-id><pub-id pub-id-type="pmid">28818945</pub-id></element-citation></ref><ref id="CR34"><label>34</label><element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Jacquez</surname><given-names>GM</given-names></name><name><surname>Essex</surname><given-names>A</given-names></name><name><surname>Curtis</surname><given-names>A</given-names></name><name><surname>Kohler</surname><given-names>B</given-names></name><name><surname>Sherman</surname><given-names>R</given-names></name><name><surname>El Emam</surname><given-names>K</given-names></name><etal></etal></person-group><article-title>Geospatial cryptography: enabling researchers to access private, spatially referenced, human subjects data for cancer control and prevention</article-title><source>J Geogr Syst</source><year>2017</year><volume>19</volume><issue>3</issue><fpage>197</fpage><lpage>220</lpage><pub-id pub-id-type="doi">10.1007/s10109-017-0252-3</pub-id><pub-id pub-id-type="pmid">29085255</pub-id></element-citation></ref><ref id="CR35"><label>35</label><element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Ghasemi</surname><given-names>R</given-names></name><name><surname>Al Aziz</surname><given-names>MM</given-names></name><name><surname>Mohammed</surname><given-names>N</given-names></name><name><surname>Dehkordi</surname><given-names>MH</given-names></name><name><surname>Jiang</surname><given-names>X</given-names></name></person-group><article-title>Private and efficient query processing on outsourced genomic databases</article-title><source>IEEE J Biomed Health Inform</source><year>2017</year><volume>21</volume><issue>5</issue><fpage>1466</fpage><lpage>72</lpage><pub-id pub-id-type="doi">10.1109/JBHI.2016.2625299</pub-id><pub-id pub-id-type="pmid">27834660</pub-id></element-citation></ref><ref id="CR36"><label>36</label><mixed-citation publication-type="other">Cheng K, Hou Y, Wang L. Secure Similar Sequence Query on Outsourced Genomic Data. In: Proceedings of the 2018 on Asia Conference on Computer and Communications Security. ACM: 2018. p. 237–51.</mixed-citation></ref><ref id="CR37"><label>37</label><element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Tang</surname><given-names>H</given-names></name><name><surname>Jiang</surname><given-names>X</given-names></name><name><surname>Wang</surname><given-names>X</given-names></name><name><surname>Wang</surname><given-names>S</given-names></name><name><surname>Sofia</surname><given-names>H</given-names></name><name><surname>Fox</surname><given-names>D</given-names></name><etal></etal></person-group><article-title>Protecting genomic data analytics in the cloud: state of the art and opportunities</article-title><source>BMC Med Genom</source><year>2016</year><volume>9</volume><issue>1</issue><fpage>63</fpage><pub-id pub-id-type="doi">10.1186/s12920-016-0224-3</pub-id></element-citation></ref><ref id="CR38"><label>38</label><element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Consortium</surname><given-names>IHGS</given-names></name><etal></etal></person-group><article-title>Initial sequencing and analysis of the human genome</article-title><source>Nature</source><year>2001</year><volume>409</volume><issue>6822</issue><fpage>860</fpage><pub-id pub-id-type="doi">10.1038/35057062</pub-id><pub-id pub-id-type="pmid">11237011</pub-id></element-citation></ref><ref id="CR39"><label>39</label><element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Casper</surname><given-names>J</given-names></name><name><surname>Zweig</surname><given-names>AS</given-names></name><name><surname>Villarreal</surname><given-names>C</given-names></name><name><surname>Tyner</surname><given-names>C</given-names></name><name><surname>Speir</surname><given-names>ML</given-names></name><name><surname>Rosenbloom</surname><given-names>KR</given-names></name><etal></etal></person-group><article-title>The UCSC genome browser database: 2018 update</article-title><source>Nucleic Acids Res</source><year>2017</year><volume>46</volume><issue>D1</issue><fpage>D762</fpage><lpage>D769</lpage></element-citation></ref><ref id="CR40"><label>40</label><element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Network</surname><given-names>CGA</given-names></name><etal></etal></person-group><article-title>Comprehensive molecular portraits of human breast tumours</article-title><source>Nature</source><year>2012</year><volume>490</volume><issue>7418</issue><fpage>61</fpage><pub-id pub-id-type="doi">10.1038/nature11412</pub-id><pub-id pub-id-type="pmid">23000897</pub-id></element-citation></ref><ref id="CR41"><label>41</label><element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Milholland</surname><given-names>B</given-names></name><name><surname>Dong</surname><given-names>X</given-names></name><name><surname>Zhang</surname><given-names>L</given-names></name><name><surname>Hao</surname><given-names>X</given-names></name><name><surname>Suh</surname><given-names>Y</given-names></name><name><surname>Vijg</surname><given-names>J</given-names></name></person-group><article-title>Differences between germline and somatic mutation rates in humans and mice</article-title><source>Nat Commun</source><year>2017</year><volume>8</volume><fpage>15183</fpage><pub-id pub-id-type="doi">10.1038/ncomms15183</pub-id><pub-id pub-id-type="pmid">28485371</pub-id></element-citation></ref><ref id="CR42"><label>42</label><element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Consortium</surname><given-names>GP</given-names></name><etal></etal></person-group><article-title>A global reference for human genetic variation</article-title><source>Nature</source><year>2015</year><volume>526</volume><issue>7571</issue><fpage>68</fpage><pub-id pub-id-type="doi">10.1038/nature15393</pub-id><pub-id pub-id-type="pmid">26432245</pub-id></element-citation></ref></ref-list></back></pmc></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Sante/explor/MersV1/Data/Pmc/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 0003038 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Pmc/Corpus/biblio.hfd -nk 0003038 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Sante
|area= MersV1
|flux= Pmc
|étape= Corpus
|type= RBID
|clé=
|texte=
}}
| This area was generated with Dilib version V0.6.33. |  |