Efficient and Highly Accurate Differentially Private Statistical Genomic Analysis using Discrete Fourier Transform
Akito Yamamoto, Tetsuo Shibuya · 2022
As the amount of data containing human genome information increases, these data will be further utilized in medicine. However, if the statistics obtained from large-scale analyses are released unchanged, there is a risk of identifying individuals. Although there are several privacy-preserving techniques to release and utilize genomic statistics, most have the problem of poor accuracy at high privacy levels and do not provide correct results especially with an increased number of outputs. In addition, existing methods with relatively high accuracy are computationally intensive and hardly applicable to a large cohort such as those containing 106SNPs. In this paper, we propose innovative differentially private methods with both efficiency and high accuracy to release the top K significant SNPs based on genomic statistics data. First, we enhance the Fourier perturbation algorithm (FPA), which was proposed in the context of histogram publication, for use with genomic statistics. Then, we propose a new extended FPA with more accurate privacy guarantees and provide a proof that this method achieves ε-differential privacy. Furthermore, we present novel methods combining DFT with the Laplace and exponential mechanisms. These methods take only $\mathcal{O}(m{\text{log}}m)$ time for a dataset containing m SNPs. We also theoretically guarantee that the value of sensitivity for these methods is smaller than that for existing methods and therefore can provide more accurate outputs. In fact, our proposed algorithms can be conducted in less than 20 seconds even for a large cohort, and our experiments using real data show that our methods can achieve 1.5 to 8 times higher accuracy than state-of-the-art methods especially when K is large. Because retrieving multiple significant SNPs from large cohorts in genomic analysis is preferred, our proposed methods are remarkably advisable rather than existing methods. Supplementary materials and the Python implementation of our experiments are available at https://github.com/ay0408/DP-DFT.