Reconciling Utility with Privacy in Genomics

Mathias Humbert, Erman Ayday, Jean-Pierre Hubaux, Amalio Telenti

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 GPPM framework for quantifying and protecting genomic privacy through two-step optimization.

The optimization occurs in two stages:

  1. Linear Optimization: A branch-and-bound algorithm identifies an optimal sharing set assuming SNP independence.
  2. 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.

Pedigree structure of the study group (a) and the resulting utility-privacy trade-off under low privacy loss tolerance (b).

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

Abstract

Direct-to-consumer genetic testing makes it possible for everyone to learn their genome sequences. In order to contribute to medical research, a growing number of people publish their genomic data on the Web, sometimes under their real identities. However, this is at odds not only with their own privacy but also with the privacy of their relatives. The genomes of relatives being highly correlated, some family members might be opposed to revealing any of the family's genomic data. In this paper, we study the trade-off between utility and privacy in genomics. We focus on the most relevant kind of variants, namely single nucleotide polymorphisms (SNPs). We take into account the fact that the SNPs of an individual contain information about the SNPs of his family members and that SNPs are correlated with each other. Furthermore, we assume that SNPs can have different utilities in medical research and different levels of sensitivity for individuals. We propose an obfuscation mechanism that enables the genomic data to be publicly available for research, while protecting the genomic privacy of the individuals in a family. Our genomic-privacy preserving mechanism relies upon combinatorial optimization and graphical models to optimize utility and meet privacy requirements. We also present an extension of the optimization algorithm to cope with the non-linear constraints induced by the correlations between SNPs. Our results on real data show that our proposed technique maximizes the utility for genomic research and satisfies family members' privacy constraints.
BibTeX
@inproceedings{humbert2014reconciling,
  author = {Mathias Humbert and Erman Ayday and Jean-Pierre Hubaux and Amalio Telenti},
  title = {{Reconciling Utility with Privacy in Genomics}},
  booktitle = {WPES},
  year = {2014},
  doi = {10.1145/2665943.2665945},
}
Figure