Privacy-Preserving Pangenome Graphs

Motivation

• Known: Human pangenome graph는 다양한 인구집단의 genetic diversity를 포착하기 위해 PGGB, MinigraphCactus 등으로 구축되며, HPRC는 47명에서 350명 규모로 확장 중이다. 그러나 개인의 haplotype path를 그대로 공개하면 rare/unique variant를 통한 재식별(re-identification) 및 민감 형질 추론(linkage attack) 위험이 존재한다는 것이 알려져 있다.
• Gap: 기존 pangenome release model은 haplotype path를 완전히 공개하거나 전혀 공개하지 않는 이분법적 방식으로, privacy와 utility를 동시에 정량적으로 조율하며 선택적으로 obfuscation하는 원칙적인 프레임워크가 부재했다. 특히 HeLa 세포나 Havasupai Tribe 사례처럼 소외된 집단의 신뢰 문제를 해결할 수 있는 실질적 도구가 없었다.
• Why: Underrepresented population을 포함한 개인들이 privacy 우려 없이 pangenome reference에 참여할 수 있도록 함으로써, 유전체 연구의 대표성과 형평성을 높이는 동시에 대규모 pangenome 프로젝트의 공개 데이터 정책 설계에 실질적 지침을 제공한다.
• Approach: PanMixer는 LD block 단위로 obfuscation move를 정의하고, 각 move의 privacy 이득(PMI 감소)과 utility 비용(Weighted Path Edit Distance)을 계산한 뒤 0-1 knapsack 최적화(OR-Tools)를 통해 utility budget 내에서 privacy risk를 최소화하는 move 조합을 선택한다.

Achievement

1. Privacy-utility trade-off의 정량적 정식화: 재식별 위험을 Pointwise Mutual Information(PMI)으로, utility 손실을 Weighted Path Edit Distance(WPED)로 정의하고 이를 knapsack 문제로 통합했다.
2. 재식별 및 genome reconstruction 공격에 대한 견고성 검증: 47명의 draft human pangenome 데이터를 이용해 PanMixer가 linkage attack 및 genome reconstruction 시도 하의 재식별 위험을 효과적으로 감소시킴을 보였다.
3. 다운스트림 분석 정확도 보존: allele frequency 추정, linkage disequilibrium(LD) 분석, read mapping 등 주요 응용에서 obfuscation 이후에도 분석 정확도가 유지됨을 입증했다.
4. Privacy-utility trade-off 곡선의 대칭성/일관성 확인: 다양한 ancestry 집단에 걸쳐 utility 제약 하 privacy 최적화와 privacy 제약 하 utility 최적화 결과가 대칭적으로 일치함을 보여 프레임워크의 견고성을 입증했다.

How

• LD block을 linear reference backbone의 top-level SNP 기준으로 계산
• 각 LD block에 대해 population allele frequency 또는 Li-Stephens HMM 기반 샘플링으로 가능한 obfuscation outcome(move) 생성
• 각 move에 대해 PMI(privacy risk, weight/value 역할)와 WPED(utility loss, weight 역할)를 계산
• 0-1 knapsack 문제로 정식화하여 OR-Tools 선형 최적화 solver로 utility budget 제약 하에서 privacy risk를 최소화하는 move 조합 탐색
• 선택된 move를 적용해 target individual의 haplotype path를 obfuscated path로 대체, 최종 privacy-preserving pangenome graph 생성
• 다양한 utility-loss capacity 수준에서 trade-off curve를 생성하고 그 역(reciprocal) 최적화 결과와 비교하여 일관성 검증
• linkage attack 시뮬레이션 및 allele frequency/LD/read mapping 분석으로 실제 성능 평가

Originality

• Pangenome graph의 privacy 문제를 knapsack 최적화 문제로 정식화한 최초의 시도로 보임
• Information theory(PMI) 기반 privacy 정량화와 graph edit distance 기반 utility 정량화를 결합한 새로운 metric 설계
• Li-Stephens HMM을 obfuscation move 생성에 활용하여 LD 구조를 보존하면서 realistic한 haplotype 대체를 수행하는 방식이 독창적
• 전체 공개/비공개의 이분법을 넘어 개인별 선택적(selective) obfuscation을 가능하게 하는 실용적 프레임워크 제시

Limitation & Further Study

• 47명이라는 비교적 작은 규모의 draft pangenome에서 검증되어, HPRC가 목표로 하는 350명 이상 규모에서의 확장성 및 계산 효율성 검증이 필요함
• Knapsack 최적화의 NP-hardness로 인한 대규모 그래프에서의 연산 비용 문제가 논의되지 않음
• LD block 및 top-level SNP 기반 접근이 구조적으로 복잡한 SV(structural variant) 영역에서 얼마나 잘 작동하는지 불명확
• 다양한 공격 모델(예: 더 정교한 machine learning 기반 재식별 공격)에 대한 강건성 추가 검증 필요
• 실제 배포 시나리오에서 반복적 데이터 업데이트나 여러 버전의 pangenome 공개에 따른 누적 privacy 위험 분석 부재

Evaluation

총평: Pangenome graph 공개에 있어 privacy와 utility를 정량적으로 조율하는 실용적이고 일반화 가능한 프레임워크를 제시한 의미 있는 연구이며, 대규모 확장성 검증이 향후 과제로 남아있다.