Abstract
Genomic data sharing is a collective family decision due to the inherent biological correlations between relatives. This paper introduces a Genomic-Privacy Preserving Mechanism (GPPM) that optimizes the disclosure of Single Nucleotide Polymorphisms (SNPs) to maximize research utility while respecting the privacy thresholds of a donor's family tree. The mechanism employs a two-step optimization process, first using linear programming for independent SNPs and then a fine-tuning heuristic to account for Linkage Disequilibrium (LD). Tested on the CEPH/Utah Pedigree 1463, the GPPM demonstrates efficient and effective balancing of kin privacy and scientific data utility.
Introduction
The rise of direct-to-consumer genetic testing and public data-sharing platforms has led to an increase in genomic data available for research. However, genomic data is inherently "interdependent"; sharing one's genome can reveal sensitive information about relatives, such as predispositions to hereditary diseases like Alzheimer’s or Parkinson’s. This "kin privacy" problem requires a mechanism that can navigate the complex interplay between Mendelian inheritance, biological correlations, and individual privacy preferences.
Methodology
The authors frame genomic data sharing as a variation of the Multidimensional Knapsack Problem. In this model, SNPs are treated as items with research utility (value) and privacy loss (weight) relative to each family member. The GPPM framework utilizes an adversary model based on Belief Propagation on graphical models (pedigrees) to quantify privacy risks based on Mendelian inheritance and background genomic knowledge.
The optimization occurs in two stages:
- Linear Optimization: A branch-and-bound algorithm identifies an optimal sharing set assuming SNP independence.
- Non-Linear Fine-Tuning: A heuristic adjusts the set to account for Linkage Disequilibrium (LD)—the biological reality that certain SNPs are correlated—ensuring that these correlations do not lead to unintended privacy leaks.
Experimental Results
The mechanism was evaluated using real genomic data from the CEPH/Utah Pedigree 1463, involving 11 family members (4 grandparents, 2 parents, and 5 children) and 50 SNPs on chromosome 1.
Key findings include:
- Utility Maximization: The GPPM successfully identifies the largest shareable SNP subset within strict privacy bounds for all 11 family members simultaneously.
- Impact of Linkage Disequilibrium: Accounting for LD is crucial. In scenarios where no family members had previously shared data, utility dropped from 19 to 13 SNPs when LD was considered, highlighting the risk of over-sharing if correlations are ignored. Conversely, if relatives have already shared data, the marginal privacy cost of sharing correlated SNPs may decrease, potentially increasing utility.
- Efficiency: Despite the NP-complete nature of the knapsack problem, the branch-and-bound approach solved the optimization for 50 SNPs in under one second, demonstrating practical feasibility.
Discussion and Limitations
By choosing to hide data rather than corrupting it with noise, the GPPM ensures that the data researchers receive is 100% accurate, maintaining scientific integrity. However, scaling to whole-genome sequences containing millions of SNPs will require "clustering" techniques to manage computational complexity. Future work could also incorporate more nuanced utility weights for specific medical research areas and explore probabilistic sharing models to further refine the utility-privacy frontier.
Summary updated