Finding Highly Similar Regions of Genomic Sequences through Homomorphic Encryption

Abstract

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 is a powerful cryptographic primitive that preserves privacy of genomic data in various analyses processed in an untrusted cloud environment.

First, we present an efficient algorithm for finding highly similar regions of two homomorphically encrypted sequences, based on the Smith-Waterman recurrence. With the efficient location retrieval, parallel computations, and a proper HE scheme, it shows good performances in the experiment so as to be useful in practice.

Second, we also propose an efficient algorithm for finding highly similar regions of two sequences represented by homomorphically encrypted variants, and conduct extensive experiments and parameter sensitivity analysis on real and synthetic datasets to show its performance. In the experiment, it finds highly similar regions of the sequences in real datasets in a feasible time.

유전체 분석의 기초적인 연산 중 하나는 유전체 서열에서 높은 유사도를 가지는 부분을 찾는 것이다. 클라우드 환경에서는 대량의 유전체 데이터를 효율적으로 처리할 수 있지만, 클라우드로 외주하는 것은 개인 정보 및 보안 문제가 발생할수 있다. 동형 암호 체계는 신뢰할 수 없는 클라우드 환경에서 처리되는 다양한 분석에서 유전체 데이터의 개인 정보를 보존하는 강력한 암호화 기법이다.

먼저 본 논문에서는 스미스-워터만 알고리즘을 기반으로 동형암호화된 두 서열 간의 유사도가 높은 부분을 찾는 효율적인 알고리즘을 제안한다. 효율적인 위치 탐색, 병렬 연산과 적절한 동형암호 구성을 갖추고 있으므로 실험에서 좋은 성능을 보여 실제로도 유용할 것이다.

다음으로는 두 동형암호화된 시퀀스 사이에서 고도로 흡사한 부분을 찾는 효 율적인 알고리즘을 제시하였다. 알고리즘의 성능을 보이기 위해 실제와 합성 데이터셋에 대해 광범위한 실험을 실시했고 매개변수 응용 정도 분석을 수행하여 성능을 제시하였다. 실험에서는 실제 데이터셋에서 시퀀스와 매우 유사한 영역을 적절한 시간 안에 찾을 수 있었다.