Finding highly similar regions of genomic sequences is a basic computation of genomic analysis. Genomic analyses on a large amount of data are efficiently processed in cloud environments, but outsourcing them to a cloud raises concerns over the privacy and security issues. Homomorphic encryption (HE) is a powerful cryptographic primitive that preserves privacy of genomic data in various analyses processed in an untrusted cloud environment. We introduce an efficient algorithm for finding highly similar regions of two homomorphically encrypted sequences, and describe how to implement it using the bit-wise and word-wise HE schemes. In the experiment, our algorithm outperforms an existing algorithm by up to two orders of magnitude in terms of elapsed time. Overall, it finds highly similar regions of the sequences in real data sets in a feasible time.
Get full access to this article
View all access options for this article.
References
1.
AltschulSF, GishW, MillerW, et al.Basic local alignment search tool. J Mol Biol, 1990; 215(3):403–410; doi: 10.1016/S0022-2836(05)80360-2.
2.
AsharovG, JainA, López-AltA, et al.Multiparty computation with low communication, computation and interaction via threshold FHE. In: Advances in Cryptology–EUROCRYPT 2012. (PointchevalD, JohanssonT. eds.) Springer: Berlin, Heidelberg; 2012; pp. 483–501; doi: 10.1007/978-3-642-29011-4_29.
3.
AzizM, SadatMN, AlhadidiD, et al.Privacy-preserving techniques of genomic data-a survey. Brief Bioinform, 2019; 20(3):887–895; doi: 10.1093/bib/bbx139.
4.
BataaM, SongS, ParkK, et al.Homomorphic computation of local alignment. In: Proceedings of the IEEE International Conference on Bioinformatics and Biomedicine (BIBM); Seoul, Korea (South); 2020; pp. 2167–2174; doi: 10.1109/BIBM49941.2020.9313199.
BlattM, GusevA, PolyakovY, et al.Secure large-scale genome-wide association studies using homomorphic encryption. Proc Natl Acad Sci U S A, 2020a;117(21):11608–11613; doi: 10.1073/pnas.1918257117.
7.
BlattM, GusevA, PolyakovY, et al.Optimized homomorphic encryption solution for secure genome-wide association studies. BMC Med Genomics, 2020b;13(7):1–13; doi: 10.1186/s12920-020-0719-9.
BrakerskiZ, GentryC, VaikuntanathanV. (Leveled) fully homomorphic encryption without bootstrapping. In: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference; 2012; pp. 309–325; doi: 10.1145/2090236.2090262.
10.
BrutlagDL, DautricourtJP, MaulikS, et al.Improved sensitivity of biological sequence database searches. Bioinformatics, 1990; 6(3):237–245; doi: 10.1093/bioinformatics/6.3.237.
11.
CarpovS, GamaN, GeorgievaM, et al.Privacy-preserving semi-parallel logistic regression training with fully homomorphic encryption. BMC Med Genomics, 2020; 13(7):1–10; doi: 10.1186/s12920-020-0723-0.
12.
ÇetinGS, ChenH, LaineK, et al.Private queries on encrypted genomic data. BMC Med Genomics, 2017; 10(2):1–14; doi: 10.1186/s12920-017-0276-z.
13.
ChenH, Gilad-BachrachR, HanK, et al.Logistic regression over encrypted data from fully homomorphic encryption. BMC Med Genomics, 2018; 11(4):3–12; doi: 10.1186/s12920-018-0397-z.
14.
ChenJ, GuoM, WangX, et al.A comprehensive review and comparison of different computational methods for protein remote homology detection. Brief Bioinform, 2016; 19(2):231–244; doi: 10.1093/bib/bbw108.
15.
CheonJH, KimA, KimM, et al.Homomorphic encryption for arithmetic of approximate numbers. In: Advances in Cryptology–ASIACRYPT. (TakagiT, PeyrinT. eds.) Springer: Cham; 2017; pp. 409–437; doi: 10.1007/978-3-319-70694-8_15.
16.
CheonJH, KimD, KimD, et al.Numerical method for comparison on homomorphically encrypted numbers. In: Advances in Cryptology–ASIACRYPT. (GalbraithS, MoriaiS. eds.) Springer: Cham; 2019; pp. 415–445; doi: 10.1007/978-3-030-34621-8_15.
17.
CheonJH, KimM, LauterK. Homomorphic computation of edit distance. In: Financial Cryptography and Data Security. (BrennerM, ChristinN, JohnsonB, RohloffK. eds.) Springer: Berlin, Heidelberg; 2015; pp. 194–212; doi: 10.1007/978-3-662-48051-9_15.
18.
ChillottiI, GamaN, GeorgievaM, et al. Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds. In: Advances in Cryptology–ASIACRYPT. (CheonJ, TakagiT. eds.) Springer: Berlin, Heidelberg; 2016a; pp. 3–33; doi: 10.1007/978-3-662-53887-6_1.
19.
ChillottiI, GamaN, GeorgievaM, et al. TFHE: Fast fully homomorphic encryption library. GitHub. 2016b. Available from: https://tfhe.github.io/tfhe. Last accessed on Nov.22, 2023.
20.
ChurchGM. The personal genome project. Mol Syst Biol, 2005; 1(1):2005–2030; doi: 10.1038/msb4100040.
21.
DucasL, MicciancioD. FHEW: Bootstrapping homomorphic encryption in less than a second. In: Advances in Cryptology–EUROCRYPT. (OswaldE, FischlinM. eds.) Springer: Berlin, Heidelberg; 2015; pp. 617–640; doi: 10.1007/978-3-662-46800-5_24.
22.
FuchsR, StoehrP. EMBLSearch: A CDROM based database query system. Bioinformatics, 1993; 9(1):71–77; doi: 10.1093/bioinformatics/9.1.71.
23.
GentryC. Fully Homomorphic Encryption Using Ideal Lattices. In: ACM Symposium on Theory of Computing. 2009; pp. 169–178; doi: 10.1145/1536414.1536440.
24.
GotohO. An improved algorithm for matching biological sequences. J Mol Biol, 1982; 162(3):705–708; doi: 10.1016/0022-2836(82)90398-9.
25.
GusfieldD. Efficient methods for multiple sequence alignment with guaranteed error bounds. Bull Math Biol, 1993; 55(1):141–154; doi: 10.1016/S0092-8240(05)80066-7.
26.
HomerN, MerrimanB, NelsonSF. Bfast: An alignment tool for large scale genome resequencing. PLoS One, 2009; 4(11):e7767; doi: 10.1371/journal.pone.0007767.
27.
Khajeh-SaeedA, PooleS, Blair PerotJ. Acceleration of the Smith–Waterman algorithm using single and multiple graphics processors. J Comput Phys, 2010; 229(11):4247–4258; doi: 10.1016/j.jcp.2010.02.009.
28.
KimA, SongY, KimM, et al.Logistic regression model training based on the approximate homomorphic encryption. BMC Med Genomics, 2018a;11(4):23–31; doi: 10.1186/s12920-018-0401-7.
29.
KimD, SonY, KimD, et al.Privacy-preserving approximate GWAS computation based on homomorphic encryption. BMC Med Genomics, 2020a;13(7):1–12; doi: 10.1186/s12920-020-0722-1.
30.
KimM, LauterK. Private genome analysis through homomorphic encryption. BMC Med Inform Decis Mak, 2015; 15(5):1–12; doi: 10.1186/1472-6947-15-S5-S3.
31.
KimM, SongY, CheonJH. Secure searching of biomarkers through hybrid homomorphic encryption scheme. BMC Med Genomics, 2017; 10(2):69–76; doi: 10.1186/s12920-017-0280-3.
32.
KimM, SongY, LiB, et al.Semi-parallel logistic regression for GWAS on encrypted data. BMC Med Genomics, 2020b;13(7):1–13; doi: 10.1186/s12920-020-0724-z.
33.
KimM, SongY, WangS, et al.Secure logistic regression based on homomorphic encryption: Design and evaluation. JMIR Med Inform, 2018b;6(2):e19; doi: 10.2196/medinform.8805.
34.
LangmeadB, SalzbergSL. Fast gapped-read alignment with bowtie 2. Nat Methods, 2012; 9(4):357–359; doi: 10.1038/nmeth.1923.
35.
LiuY, WirawanA, SchmidtB. Cudasw++ 3.0: Accelerating Smith–Waterman protein database search by coupling CPU and GPU SIMD instructions. BMC Bioinformatics, 2013; 14(1):1–10; doi: 10.1186/1471-2105-14-117.
36.
López-AltA, TromerE, VaikuntanathanV. On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption. In: ACM Symposium on Theory of Computing. 2012; pp. 1219–1234; doi: 10.1145/2213977.2214086.
37.
LuD, ZhangY, ZhangL, et al.Methods of privacy-preserving genomic sequencing data alignments. Brief Bioinform, 2021; 22(6):bbab151; doi: 10.1093/bib/bbab151.
38.
LuWJ, YamadaY, SakumaJ. Privacy-preserving genome-wide association studies on cloud environment using fully homomorphic encryption. BMC Med Inform Decis Mak, 2015; 15(5):1–8; doi: 10.1186/1472-6947-15-S5-S1.
39.
MouchetC, Troncoso-PastorizaJ, BossuatJP, et al.Multiparty homomorphic encryption from ring-learning-with-errors. Proc Priv Enhanc Technol, 2021; 2021(4):291–311; doi: 10.2478/popets-2021-0071.
40.
ParkS, KimM, SeoS, et al.A secure SNP panel scheme using homomorphically encrypted k-mers without SNP calling on the user side. BMC Genomics, 2019; 20(2):163–174; doi: 10.1186/s12864-019-5473-z.
41.
PearsonWR. An introduction to sequence similarity (homology) searching. Curr Protoc Bioinformatics, 2013; 42(1):3.1.1–3.1.8; doi: 10.1002/0471250953.bi0301s42.
42.
PerumallaK, DeoN. Parallel algorithms for maximum subsequence and maximum subarray. Parallel Process Lett, 1995; 5(3):367–373; doi: 10.1142/S0129626495000345.
43.
PoulletM, OrlandoL. Assessing DNA sequence alignment methods for characterizing ancient genomes and methylomes. Front Ecol Evol, 2020; 8:105; doi: 10.3389/fevo.2020.00105.
44.
SimJJ, ChanFM, ChenS, et al.Achieving GWAS with homomorphic encryption. BMC Med Genomics, 2020; 13(7):1–12; doi: 10.1186/s12920-020-0717-y.
45.
SmithTF, WatermanMS. Identification of common molecular subsequences. J Mol Biol, 1981; 147(1):195–197; doi: 10.1016/0022-2836(81)90087-5.
46.
SousaJS, LefebvreC, HuangZ, et al.Efficient and secure outsourcing of genomic data storage. BMC Med Genomics, 2017; 10(2):15–28; doi: 10.1186/s12920-017-0275-0.
47.
SdingJ. Protein homology detection by HMMHMM comparison. Bioinformatics, 2004; 21(7):951–960; doi: 10.1093/bioinformatics/bti125.
WangXS, HuangY, ZhaoY, et al.Efficient genome-wide, privacy-preserving similar patient query based on private edit distance. In: CCS '15: Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security. 2015; pp. 492–503; doi: 10.1145/2810103.2813725.
50.
YakubuAM, ChenYP. Ensuring privacy and security of genomic data and functionalities. Brief Bioinform, 2019; 21(2):511–526; doi: 10.1093/bib/bbz013.
Supplementary Material
Please find the following supplemental material available below.
For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.
For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.
