A Joint Permute-and-Flip and Its Enhancement for Large-Scale Genomic Statistical Analysis
Akito Yamamoto, Tetsuo Shibuya · 2023
Owing to an increase in the amount of biomedical and healthcare data, privacy concerns regarding the use of genomic data have become well-recognized. Specifically, it is essential to develop personalized medicine to extract significant loci associated with diseases through large-scale genomic statistical analyses while protecting privacy. Although there are several differentially private methods for this purpose, they are too computationally complex to achieve high accuracy, and there is room for improvement in terms of the output error. In this study, we propose a novel mechanism, Joint Permute-and-Flip, that can provide higher-quality outputs than state-of-the-art techniques for top-K selection. We also present an efficient algorithm that can perform Joint Permute-and-Flip in $\mathcal{O}(m\log m)$ time when the dataset contains m elements, making it applicable even to large-scale analyses involving 106elements. Additionally, we propose new score functions suitable for genomic statistical analysis that can be expressed as a single equation and achieve high accuracy. This is expected to facilitate the construction of accurate and efficient scores for a wider variety of genome statistics. Experimental results demonstrate that our Joint Permute-and-Flip method outperforms existing methods in terms of both accuracy and rank error and requires only half the run time of the exponential mechanism. The supplemental materials and the Python implementation of our experiments are available at https://github.com/ay0408/Joint-PnF.