TL;DR
This paper presents a novel method for privacy-preserving genotype imputation using machine learning and partially homomorphic encryption (PHE). By adapting linear ML models and optimizing the Paillier cryptosystem, they achieve state-of-the-art accuracy while protecting sensitive genetic data during outsourced computations.
What Problem Does This Paper Address?
Genomic sequencing is advancing rapidly, offering incredible insights into human health and disease. However, analyzing entire genomes for large populations is prohibitively expensive. Genotype imputation, which predicts missing genetic variants, is a crucial technique for cost-effective analysis, especially in Genome-Wide Association Studies (GWAS). The challenge arises when this computationally intensive imputation is outsourced to cloud services. This raises significant privacy concerns, as genetic data is highly sensitive and identifying. Existing privacy-preserving methods often struggle with the computational overhead or require complex modifications to standard algorithms, making them impractical for large-scale genomic tasks.
Methods
The core of this work lies in combining machine learning (ML) with partially homomorphic encryption (PHE) to enable privacy-preserving genotype imputation.
- Linear ML Models for Imputation: Instead of complex non-linear ML models (which are computationally expensive in encrypted domains), the authors focus on linear ML models. They demonstrate that these linear models can achieve accuracy comparable to state-of-the-art non-linear methods for genotype imputation.
- Paillier Cryptosystem: The Paillier cryptosystem, a well-established PHE scheme, is chosen for its efficiency in handling modular multiplication.
- Optimizations for PHE: To overcome the limitations of Paillier (e.g., lack of floating-point support, handling of negative numbers), the authors introduce several optimizations:
- Positive Operands: They use Keras's built-in training constraints to clip weights and biases to be non-negative.
- Integer Operands: Floating-point weights are scaled to larger integer values to maintain their relative ranking while fitting within the PHE framework.
- Batching: Multiple individuals' data are packed into a single ciphertext to speed up encryption and decryption.
- Optimized Encryption/Decryption: They leverage GMP for efficient arithmetic and precompute values to avoid costly exponentiations during encryption.
- Thread-Level Parallelism: They apply parallelism to matrix multiplication, encryption, and decryption.
Datasets
The study utilizes several datasets for training and evaluation:
- 1000 Genomes Project: Used as the primary dataset for training and testing.
- iDASH Secure Genome Analysis Challenge '19: Provided tag and target SNPs for chromosome 1, split into two subsets:
- 1k dataset: Tag SNPs at 1kb genomic distance.
- 10k dataset: Tag SNPs at 10kb genomic distance.
- GTEx (Genotype-Tissue Expression) Project: Used as an independent dataset for testing.
- ALSPAC (Avon Longitudinal Study of Parents and Children) Project: Another independent dataset used for testing.
- Real-world scenario: Imputing 80,000 target SNPs using 16,184 tag SNPs from chromosome 22.
Key Insights and Ideas
- Linear Models are Sufficient: The paper convincingly shows that for genotype imputation, linear ML models can achieve accuracy comparable to more complex non-linear models, making them ideal for privacy-preserving computation with PHE.
- PHE is Practical for Genomics: By carefully optimizing the Paillier cryptosystem and adapting ML models, the authors demonstrate that PHE can be a viable and efficient solution for privacy-preserving genomic analysis, overcoming the prohibitive overheads of FHE for such tasks.
- "Phasing-Free" Imputation is Viable: Their approach bypasses the computationally expensive genome phasing step, which is a significant advantage for speed and simplicity, even with a slight accuracy trade-off for heterozygous genotypes.
- Trade-offs are Manageable: The study highlights that the slight reduction in accuracy from approximations and optimizations is well worth the massive gains in privacy and computational efficiency.
Key Results
- High Accuracy: The privacy-preserving imputation method achieved micro-average AUC scores up to 99% on real-world datasets, comparable to state-of-the-art plaintext methods like IMPUTE2 and Beagle.
- Efficiency: For a large-scale imputation of 80,000 target SNPs for 1,000 individuals, the entire encrypted process (encryption, computation, decryption) took approximately 925.7 seconds.
- Scalability: The costs scale linearly with the number of target SNPs, and the memory requirements are practical.
- Comparison to Non-Linear Models: The proposed linear model with PHE achieved accuracy very close to non-linear logistic regression and deep neural networks using FHE, but was orders of magnitude faster.
Limitations and Future Work
- Honest but Curious Threat Model: The security relies on the assumption that the imputation server is "honest but curious," meaning it follows instructions but might try to infer information from the data it processes. It does not protect against a malicious server actively trying to corrupt results.
- Approximations: While effective, the method uses approximations (e.g., not calculating final probabilities) to fit within the PHE framework.
- Future Work: The authors suggest exploring federated learning for privacy-preserving model training and applying these techniques to other large-scale privacy-preserving genome analysis tools, such as haplotype phasing.
Summary updated