TY - GEN
T1 - Efficient genome-wide, privacy-preserving Similar Patient Query based on private edit distance
AU - Wang, Xiao
AU - Huang, Yan
AU - Zhao, Yongan
AU - Tang, Haixu
AU - Wang, Xiao Feng
AU - Bu, Diyue
N1 - Funding Information:
We would like to thank Jonathan Katz for numerous helpful discussions. This work is supported by NSF award #1111599, #1464113, #1117106, #1223477, #1223495, #1408874 and NIH HG007078.
PY - 2015/10/12
Y1 - 2015/10/12
N2 - Edit distance has been proven to be an important and frequentlyused metric in many human genomic research, with Similar Patient Query (SPQ) being a particularly promising and attractive example. However, due to the widespread privacy concerns on revealing personal genomic data, the scope and scale of many novel use of genome edit distance are substantially limited. While the problem of private genomic edit distance has been studied by the research community for over a decade [5], the state-of-the-art solution [30] is far from even close to be applicable to real genome sequences. In this paper, we propose several private edit distance protocols that feature unprecedentedly high efficiency and precision. Our construction is a combination of a novel genomic edit distance approximation algorithm and new construction of private set difference size protocols. With the private edit distance based secure SPQ primitive, we propose GENSETS, a genome-wide, privacy-preserving similar patient query system. It is able to support searching large-scale, distributed genome databases across the nation. We have implemented a prototype of GENSETS. The experimental results show that, with 100 Mbps network connection, it would take GENSETS less than 200 minutes to search through 1 million breast cancer patients (distributed nation-wide in 250 hospitals, each having 4000 patients), based on edit distances between their genomes of lengths about 75 million nucleotides each.
AB - Edit distance has been proven to be an important and frequentlyused metric in many human genomic research, with Similar Patient Query (SPQ) being a particularly promising and attractive example. However, due to the widespread privacy concerns on revealing personal genomic data, the scope and scale of many novel use of genome edit distance are substantially limited. While the problem of private genomic edit distance has been studied by the research community for over a decade [5], the state-of-the-art solution [30] is far from even close to be applicable to real genome sequences. In this paper, we propose several private edit distance protocols that feature unprecedentedly high efficiency and precision. Our construction is a combination of a novel genomic edit distance approximation algorithm and new construction of private set difference size protocols. With the private edit distance based secure SPQ primitive, we propose GENSETS, a genome-wide, privacy-preserving similar patient query system. It is able to support searching large-scale, distributed genome databases across the nation. We have implemented a prototype of GENSETS. The experimental results show that, with 100 Mbps network connection, it would take GENSETS less than 200 minutes to search through 1 million breast cancer patients (distributed nation-wide in 250 hospitals, each having 4000 patients), based on edit distances between their genomes of lengths about 75 million nucleotides each.
KW - Edit distance
KW - Genomic computation
KW - Secure computation
UR - http://www.scopus.com/inward/record.url?scp=84954167566&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84954167566&partnerID=8YFLogxK
U2 - 10.1145/2810103.2813725
DO - 10.1145/2810103.2813725
M3 - Conference contribution
AN - SCOPUS:84954167566
T3 - Proceedings of the ACM Conference on Computer and Communications Security
SP - 492
EP - 503
BT - CCS 2015 - Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security
PB - Association for Computing Machinery
T2 - 22nd ACM SIGSAC Conference on Computer and Communications Security, CCS 2015
Y2 - 12 October 2015 through 16 October 2015
ER -