SNP連鎖不平衡下的基因隱私保護(hù)模型*

劉 海,吳振強(qiáng),彭長(zhǎng)根,雷秀娟

1(陜西師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院,陜西 西安 710119)

2(貴州省公共大數(shù)據(jù)重點(diǎn)實(shí)驗(yàn)室(貴州大學(xué)),貴州 貴陽 550025)

基因數(shù)據(jù)是富含人類重要信息的生物大數(shù)據(jù)[1],并且是人類脫氧核糖核酸(deoxyribonucleic acid,簡(jiǎn)稱DNA)序列的總稱.DNA是生物遺傳信息的攜帶者,與生物的繁殖、遺傳及變異密切相關(guān).DNA序列包含 30億由4種核苷酸(腺嘌呤A、鳥嘌呤G、胸腺嘧啶T、胞嘧啶C)組成的堿基對(duì),人類有99.9%共同的DNA序列,其中,大約有 5 000萬單核苷酸多態(tài)性(single nucleotide polymorphism,簡(jiǎn)稱 SNP).SNP是最常見的 DNA變異,SNP是指?jìng)€(gè)體DNA序列同一位置單個(gè)核苷酸變異所引起的多態(tài)性.SNP變異由單個(gè)堿基的轉(zhuǎn)換(C?T,在其互補(bǔ)鏈上則為 C?A)或顛換(C?A,G?T,C?G,A?T)所引起,一般所說的 SNP變異由堿基轉(zhuǎn)換所致.通常對(duì)于每個(gè) SNP位點(diǎn)具有兩個(gè)不同核苷酸(稱為等位基因),一個(gè)是高頻率的主要等位基因,一個(gè)是低頻率的次要等位基因.等位基因是同源染色體上的相同位點(diǎn)控制同一性狀的不同形式的基因.位點(diǎn)是染色體上一個(gè)基因或標(biāo)記的位置.SNP的連鎖不平衡(linkage disequilibrium,簡(jiǎn)稱LD)是一種普遍存在的生物現(xiàn)象,指的是基因序列中任意兩個(gè)鄰近SNP之間的等位基因在多代遺傳中的非隨機(jī)組合現(xiàn)象.

隨著高通量基因測(cè)序技術(shù)的發(fā)展,測(cè)序成本大幅度降低,產(chǎn)生了海量高維的基因數(shù)據(jù).基因數(shù)據(jù)廣泛用于科學(xué)研究、面向消費(fèi)者服務(wù)和法律與司法鑒定等[2].例如,在全基因組關(guān)聯(lián)研究(genome-wide association studies,簡(jiǎn)稱GWAS)中可以識(shí)別與SNP相關(guān)的疾病[3].但是,SNP攜帶個(gè)體健康的隱私敏感信息,并且可以唯一標(biāo)識(shí)人類個(gè)體,基因數(shù)據(jù)使用不當(dāng)會(huì)導(dǎo)致敏感信息泄露[4],例如,載脂蛋白 E(apolipoprotein E)基因的兩個(gè) SNP(rs7412和rs429358)會(huì)增加患老年癡呆癥(Alzheimer’s disease)的風(fēng)險(xiǎn).并且在連鎖不平衡下,可以從SNP相關(guān)的敏感信息推斷出其他SNP相關(guān)的敏感信息.因此,本文基于SNP連鎖不平衡相關(guān)系數(shù),提出基因隱私保護(hù)模型:矩陣差分隱私(matrix differential privacy,簡(jiǎn)稱MDP).該模型既可以保護(hù)基因數(shù)據(jù)和SNP連鎖不平衡的隱私,同時(shí)確?；驍?shù)據(jù)具有一定的效用.

由于 SNP可以唯一標(biāo)識(shí)人類個(gè)體,并且關(guān)聯(lián)表型和血緣關(guān)系等隱私敏感信息.如果沒有適當(dāng)?shù)貙?duì)基因數(shù)據(jù)進(jìn)行隱私保護(hù),將會(huì)阻礙科學(xué)研究的進(jìn)步和發(fā)展,并給人類社會(huì)帶來巨大影響.例如,在基因組序列中只需 30～80個(gè)獨(dú)立的SNP位點(diǎn)就可以唯一重識(shí)別個(gè)體[5],進(jìn)而導(dǎo)致其關(guān)聯(lián)的隱私敏感信息泄露.從GWAS中揭示個(gè)體的疾病狀態(tài)[6]可能會(huì)導(dǎo)致工作和保險(xiǎn)中的基因歧視[7].考慮到具有血緣關(guān)系個(gè)體之間的基因數(shù)據(jù)非常相似,可以從GWAS中推斷個(gè)體的親戚及其相關(guān)的表型敏感信息[4].因此需要聯(lián)合法律法規(guī)和隱私保護(hù)技術(shù)來實(shí)現(xiàn)基因數(shù)據(jù)的隱私保護(hù).目前國(guó)內(nèi)尚未有專門的基因隱私保護(hù)法律法規(guī),美國(guó)于 1996年頒布了 HIPAA(health insurance portability and accountability act)禁止基因歧視.

除了專門的基因隱私保護(hù)法律法規(guī)外,還需要隱私保護(hù)技術(shù)來實(shí)現(xiàn)基因數(shù)據(jù)的隱私保護(hù).由于基因與人類的敏感信息密切相關(guān),基因-疾病關(guān)聯(lián)分析中目前主要有 3類基因隱私保護(hù)方法,包括密碼學(xué)[8-11]、安全計(jì)算[12,13]和差分隱私[14-18].

為了從分布式基因數(shù)據(jù)中分析罕見疾病,Chen等人[8]提出隱私保護(hù)分布式協(xié)作框架 PRINCESS,并使用AES-GCM(advanced encryption standard in galois counter mode)加密所有基因數(shù)據(jù),PRINCESS為了保護(hù)健康信息的隱私對(duì)加密數(shù)據(jù)執(zhí)行安全的分布式計(jì)算.在使用 AES-GCM 加密基因數(shù)據(jù)時(shí),由于密鑰分發(fā)通信代價(jià)高而使加解密受限,并且不可信用戶解密后通過分析基因數(shù)據(jù)導(dǎo)致患者隱私泄露.因此,為了防止不可信用戶解密后分析基因數(shù)據(jù)導(dǎo)致的隱私泄露,使用同態(tài)加密直接對(duì)密文進(jìn)行計(jì)算.Ayday[9]使用Paillier密碼系統(tǒng)和Honey加密方法保護(hù)基因數(shù)據(jù)的隱私.為了發(fā)現(xiàn)罕見變異與疾病易感性的關(guān)系,基于懲罰似然的確切邏輯回歸(exact logistic regression)減少偏差的方法,Wang等人[10]在同態(tài)加密的確切邏輯回歸的基礎(chǔ)上提出HEALER框架,便于在 GWAS中安全地實(shí)現(xiàn)小抽樣的罕見疾病變異分析.為了實(shí)現(xiàn)查詢和結(jié)果的隱私保護(hù),Shimizu等人[11]基于加法同態(tài)加密的不經(jīng)意傳輸(oblivious transfer)隱藏序列查詢和感興趣的基因區(qū)域.由于同態(tài)加密基于有限域數(shù)學(xué)理論,計(jì)算效率非常低,并且在不可信用戶解密后同樣面臨隱私泄露的問題.

在人類基因序列之間,安全計(jì)算編輯距離(edit distance)在醫(yī)學(xué)的個(gè)人基因數(shù)據(jù)和公共健康領(lǐng)域呈現(xiàn)出許多有趣的應(yīng)用.Wang等人[12]結(jié)合基因編輯距離近似算法和隱私集合差大小協(xié)議設(shè)計(jì)隱私編輯距離協(xié)議,并基于此,設(shè)計(jì)全基因組安全相似患者查詢系統(tǒng)GenSets.最近的工作表明,個(gè)體的微生物DNA序列與人類個(gè)體標(biāo)識(shí)相符合,并且可以關(guān)聯(lián)基因數(shù)據(jù)集中敏感屬性的實(shí)際身份.目前,DNA隱私保護(hù)分析工具不滿足微生物測(cè)序研究的要求.為了解決微生物測(cè)序的隱私問題,Wagner等人[13]使用安全計(jì)算實(shí)現(xiàn)宏基因組分析.基因數(shù)據(jù)的安全計(jì)算中計(jì)算效率低,而且通信代價(jià)高.

從基因數(shù)據(jù)選擇到GWAS統(tǒng)計(jì)值的隱私保護(hù),差分隱私[14]已經(jīng)廣泛應(yīng)用于基因數(shù)據(jù).例如,在DNA數(shù)據(jù)選擇過程中,Zhao等人[15]利用連鎖不平衡對(duì)高維單體型降維到單體型塊,并通過對(duì)單體型塊的次要等位基因計(jì)數(shù)加噪音產(chǎn)生差分隱私實(shí)驗(yàn)數(shù)據(jù)集,不但保護(hù)了患者的隱私,而且保證了 DNA數(shù)據(jù)的效用.在隱私保護(hù)數(shù)據(jù)選擇中僅僅通過對(duì)次要等位基因計(jì)數(shù)加噪音來實(shí)現(xiàn)差分隱私.由于隱私攻擊對(duì)參與 GWAS患者的隱私具有潛在的威脅,Cai等人[16]提出了差分隱私技術(shù)是一個(gè)有希望的研究方向,差分隱私通過注入隨機(jī)噪音到基因型頻率、基因型-疾病關(guān)聯(lián)性和基因型-基因型關(guān)聯(lián)性統(tǒng)計(jì)值.但并未考慮SNP的連鎖不平衡性質(zhì).假設(shè)GWAS的基因數(shù)據(jù)是不相關(guān)的,Tramèr等人[17]考慮更多合理的背景知識(shí)作為先驗(yàn)分布,提出有界先驗(yàn)差分隱私用于 GWAS中每個(gè)SNP列聯(lián)表的χ2-統(tǒng)計(jì)值達(dá)到效用與隱私的平衡.不過,同樣沒有考慮基因數(shù)據(jù)中SNP的連鎖不平衡性質(zhì).然而,在挖掘最重要的SNP的所有差分隱私方法中都具有準(zhǔn)確度或計(jì)算效率的缺點(diǎn),為此,Simmons和Berger[18]使用等位基因檢測(cè)統(tǒng)計(jì)值的輸入擾動(dòng)和自適應(yīng)邊界的方法來克服準(zhǔn)確性問題.總的來說,在GWAS中的差分隱私保護(hù)研究?jī)H僅考慮添加噪音到統(tǒng)計(jì)值,而沒有考慮 SNP的連鎖不平衡性質(zhì),并且沒有對(duì)原始基因數(shù)據(jù)進(jìn)行隱私保護(hù).

但是,基于GWAS中的統(tǒng)計(jì)值和SNP的連鎖不平衡,可以推斷出患者的隱私信息.因?yàn)镾NP連鎖不平衡是同一染色體上相互鄰近的等位基因可能同時(shí)遺傳到后代.那么從一個(gè) SNP位點(diǎn)的敏感信息可以推斷出其他SNP位點(diǎn)相關(guān)的敏感信息.例如,在SNP連鎖不平衡下,觀察到的SNP越多,基因隱私保護(hù)強(qiáng)度越低[4].現(xiàn)有的工作主要有兩方面的局限性:(1) 沒有從基因數(shù)據(jù)而僅僅是從GWAS中的統(tǒng)計(jì)值上實(shí)現(xiàn)患者的差分隱私；(2) 沒有考慮SNP連鎖不平衡下的基因數(shù)據(jù)隱私保護(hù).另外,由于基因型數(shù)據(jù)只包含數(shù)值0、1和2,如果對(duì)基因數(shù)據(jù)直接使用差分隱私機(jī)制將導(dǎo)致基因數(shù)據(jù)效用災(zāi)難,詳見第4.4節(jié)基因數(shù)據(jù)的效用分析.

為了解決此問題,本文提出基因數(shù)據(jù)和SNP連鎖不平衡的矩陣差分隱私保護(hù)模型.首先將單核苷酸多態(tài)性二倍體基因數(shù)據(jù)進(jìn)行矩陣存儲(chǔ),然后在連鎖不平衡下基于嚴(yán)格的差分隱私定義實(shí)現(xiàn)二倍體基因數(shù)據(jù)以及 SNP連鎖不平衡的不可區(qū)分性,最后運(yùn)用模余運(yùn)算進(jìn)行二倍體基因數(shù)據(jù)的置換.矩陣差分隱私保護(hù)模型不僅滿足差分隱私,而且確保一定的基因數(shù)據(jù)效用.同時(shí),矩陣差分隱私保護(hù)模型可以擴(kuò)展到基因數(shù)據(jù)的其他應(yīng)用領(lǐng)域.本文主要貢獻(xiàn)如下.

(1) 結(jié)合SNP二倍體基因數(shù)據(jù)的矩陣存儲(chǔ)、SNP連鎖不平衡下嚴(yán)格的差分隱私定義和模余運(yùn)算,提出矩陣差分隱私保護(hù)模型作為基因隱私保護(hù)的新方法.

(2) 基于拉普拉斯機(jī)制和高斯機(jī)制,在 SNP連鎖不平衡相關(guān)系數(shù)下,設(shè)計(jì)矩陣差分隱私保護(hù)模型的算法,實(shí)現(xiàn)基因數(shù)據(jù)與SNP連鎖不平衡的隱私保護(hù).

(3) 矩陣差分隱私保護(hù)模型確保基因數(shù)據(jù)效用在區(qū)間[R0,1]中,其中,R0表示當(dāng)隱私預(yù)算最小時(shí)矩陣差分隱私下噪音矩陣中模3余0元素?cái)?shù)量的百分比值.

本文第1節(jié)介紹基因背景知識(shí)以及矩陣計(jì)算、模余運(yùn)算和差分隱私的預(yù)備知識(shí).第2節(jié)提出矩陣差分隱私保護(hù)模型.第 3節(jié)對(duì)矩陣差分隱私進(jìn)行理論分析.第 4節(jié)分別對(duì)矩陣差分隱私的隱私保護(hù)和基因數(shù)據(jù)效用進(jìn)行實(shí)驗(yàn)分析.第5節(jié)對(duì)全文進(jìn)行總結(jié).

1 預(yù)備知識(shí)

首先介紹基因的背景知識(shí).然后介紹矩陣計(jì)算、模余運(yùn)算和差分隱私的預(yù)備知識(shí).

1.1 基因組

盡管人類的DNA大部分是相同的,但是產(chǎn)生的變異大約有5 000萬,其中SNP是人類最常見的DNA變異.由于每個(gè)SNP位點(diǎn)的兩個(gè)核苷酸分別從父親和母親的基因中遺傳而來,因此可能是高頻率的主要等位基因,也可能是低頻率的次要等位基因.每個(gè)SNPgi具有次要等位基因的頻率為,對(duì)于一個(gè)個(gè)體的基因型SNP的次要等位基因頻率表示為m維向量.用B表示主要等位基因,b表示次要等位基因,B,b∈{A,C,G,T},并且編碼BB為0,Bb為1,bb為2.考慮SNP序列作為個(gè)體的基因數(shù)據(jù),稱為二倍體基因型,其中,每個(gè)基因型取值屬于集合{0,1,2}.因此,單倍體基因型對(duì)應(yīng)一條染色體,而二倍體基因型對(duì)應(yīng)一組染色體.

在人類基因組序列中,每個(gè)序列可以表示為有序的SNP序列g(shù)1,g2,…,gm序列,其中,每個(gè)gi∈{0,1,2}.假設(shè)gi與gj相互連鎖不平衡,(B,b)和(D,d)分別是gi和gj的等位基因.假設(shè)(p1,1-p1)和(p2,1-p2)分別是(B,b)和(D,d)的等位基因概率.這里,等位基因頻率即是等位基因的概率.如果gi和gj相互獨(dú)立,那么個(gè)體在gi和gj的主要等位基因是B和D的概率為p1p2.然而,由于gi和gj的關(guān)聯(lián)性,因此連鎖不平衡系數(shù)為L(zhǎng)D=P(BD)-P(B)P(D),其中,在連鎖不平衡下,P(BD)等于在 SNP位點(diǎn)i和j的等位基因B和D共同出現(xiàn)在群體中的頻率,并使用作為SNP連鎖不平衡的相關(guān)系數(shù),當(dāng)rij=1時(shí),表示最強(qiáng)的SNP連鎖不平衡[4].

1.2 矩陣計(jì)算

對(duì)于兩個(gè)n×m矩陣S=(sij)n×m和T=(tij)n×m,其中,1≤i≤n,1≤j≤m.S和T之間的加運(yùn)算定義為(cij)n×m=(sij)n×m+(tij)n×m,其中,cij=sij+tij.另外,round(S)表示運(yùn)用四舍五入規(guī)則將矩陣S中的元素取整的近似運(yùn)算.

1.3 模余運(yùn)算

給定整數(shù)s、t、q和r,余數(shù)r=s-qt表示為r≡smodt(0

1.4 差分隱私

根據(jù)兩個(gè)相同的概率分布是不可區(qū)分的,對(duì)于個(gè)體數(shù)據(jù)的集合,差分隱私[14]確保一個(gè)攻擊者的能力是相同的,獨(dú)立于任何個(gè)體是否在數(shù)據(jù)集中.因此,在同樣大小的數(shù)據(jù)集之間,鄰近數(shù)據(jù)集僅只有一個(gè)不同.也就是說,兩個(gè)鄰近數(shù)據(jù)集X1和X2的漢明距離(Hamming distance)為d(X1,X2)=1.其中,差分隱私定義如下.

定義1(差分隱私).給定ε≥0,如果有任意兩個(gè)鄰近數(shù)據(jù)集X1和X2,對(duì)于擁有全背景知識(shí)的攻擊者,隨機(jī)機(jī)制M的任意輸出S?Range(M)使得 P r[M(X1) ∈S] ≤eεPr[M(X2)∈S]+δ,那么M是(ε,δ)-差分隱私.

其中,1-δ∈[0,1]是M滿足(ε,δ)-差分隱私的概率,并且,如果δ=0,那么M是ε-差分隱私.

為了實(shí)現(xiàn)差分隱私機(jī)制,需要計(jì)算查詢函數(shù)f的敏感度,查詢函數(shù)f:X→Rk的敏感度是

另外,差分隱私具有后處理(post-processing)和并行組合(parallel composition)[19]的性質(zhì).

性質(zhì)1(后處理).隨機(jī)機(jī)制M:X→R關(guān)于數(shù)據(jù)集X是(ε,δ)-差分隱私,f:R→R′是一個(gè)隨機(jī)映射,那么f?M:X→R′是(ε,δ)-差分隱私.

性質(zhì) 2(并行組合).隨機(jī)機(jī)制Mi滿足(εi,δ)-差分隱私,數(shù)據(jù)集Xi是X的子集,且，那么Mi的并行組合滿足(max{εi},δ)-差分隱私.

2 基因隱私保護(hù)模型

首先引入SNP連鎖不平衡下對(duì)基因數(shù)據(jù)的攻擊模型,接下來提出基因隱私保護(hù)模型:矩陣差分隱私.

2.1 攻擊模型

因?yàn)橥ㄟ^ SNP可以識(shí)別個(gè)體及其相關(guān)的敏感信息.假設(shè)攻擊者已經(jīng)觀察到隱藏的 SNP,并且攻擊者是honest-but-curious.攻擊者可以通過成對(duì)的SNP連鎖不平衡獲得敏感信息,例如相鄰兩個(gè)位點(diǎn)i和j的SNPgi和gj,它們之間存在SNP連鎖不平衡,如果gi與某種疾病易感性相關(guān),那么gj也與該疾病相關(guān).

2.2 矩陣差分隱私保護(hù)模型

在SNP連鎖不平衡下,由于基因數(shù)據(jù)的隱私保護(hù)需求,我們首先給出基因隱私保護(hù)模型——矩陣差分隱私,如圖1所示,該模型主要包括3部分.第1部分為編碼SNP二倍體基因數(shù)據(jù)并用矩陣存儲(chǔ).第2部分為對(duì)已編碼的SNP二倍體基因數(shù)據(jù)進(jìn)行隨機(jī)擾動(dòng),同時(shí)滿足基于SNP連鎖不平衡下的差分隱私.第3部分為使用模余運(yùn)算置換隨機(jī)擾動(dòng)的SNP基因數(shù)據(jù).其中,各個(gè)部分的主要思想如下.

在第1部分,B表示主要等位基因,b表示次要等位基因,根據(jù)等位基因的頻率,將主要等位基因B編碼為0,次要等位基因b編碼為1,并且B,b∈{A,C,G,T},編碼基因型BB為0,Bb為1,bb為2.那么對(duì)于n個(gè)個(gè)體,每個(gè)個(gè)體有m個(gè) SNP,用矩陣表示為X=(xij)n×m(1≤i≤n,1≤j≤m),且xij∈{0,1,2}表示第i個(gè)個(gè)體第j個(gè)位點(diǎn)的 SNP基因型.

第 2部分是對(duì) SNP二倍體基因數(shù)據(jù)進(jìn)行隨機(jī)擾動(dòng),并且滿足 SNP連鎖不平衡下的差分隱私.圖 2所示為SNP二倍體基因型數(shù)據(jù)隨機(jī)擾動(dòng)的主要思想,根據(jù)SNP連鎖不平衡下的差分隱私擾動(dòng)機(jī)制,將SNP二倍體基因型矩陣元素xij∈{0,1,2}分別以概率p1、p2和p3進(jìn)行隨機(jī)擾動(dòng).這里,p1、p2和p3是SNP連鎖不平衡下差分隱私隨機(jī)噪音對(duì)應(yīng)的概率.

如圖2所示,第3部分對(duì)隨機(jī)擾動(dòng)的二倍體基因型數(shù)據(jù)進(jìn)行模余運(yùn)算,使其具有SNP二倍體基因型數(shù)據(jù)的語義,并根據(jù)等位基因頻率和基因型編碼置換為相應(yīng)的基因型.

Fig.1 The genomic privacy preserving framework for SNP linkage disequilibrium圖1 SNP連鎖不平衡下的基因隱私保護(hù)模型

Fig.2 The differential privacy perturbation mechanism for SNP linkage disequilibrium圖2 SNP連鎖不平衡下的差分隱私擾動(dòng)機(jī)制

2.3 矩陣差分隱私

矩陣X=(xij)n×m表示n個(gè)個(gè)體的SNP,每個(gè)個(gè)體的DNA序列有m個(gè)SNP,其中,xij∈{0,1,2}表示個(gè)體i的SNPgj的隨機(jī)變量.特別地,Xi=(xi1,xi2,…,xim)表示個(gè)體i的SNP序列取值.

因?yàn)閤ij∈{0,1,2},所以查詢函數(shù)f的敏感度為Δf=2.

下面結(jié)合矩陣加運(yùn)算、SNP連鎖不平衡下的差分隱私定義和模余運(yùn)算,給出矩陣差分隱私的定義.

定義 2(矩陣差分隱私).給定ε≥0,任意兩個(gè)鄰近矩陣,對(duì)于具有全背景知識(shí)的攻擊者,M的任意輸出S=(sij)n×m?Range(M),使得.那么,隨機(jī)機(jī)制

另外,由于個(gè)體i的SNP序列值表示為向量Xi=(xi1,xi2,…,xim).類似地,下面我們來定義向量差分隱私.

定義3(向量差分隱私).給定ε≥0,任意兩個(gè)鄰近向量,對(duì)于具有全背景知識(shí)的攻擊者,M的任意輸出Si=(sij)1×m?Range(M),使得.那么,隨機(jī)機(jī)制

因此,向量差分隱私是矩陣差分隱私的特例.下面給出矩陣差分隱私的通用算法1.其中,概率分布π(Δfc/max可以是拉普拉斯分布和高斯分布,即噪音矩陣(yij)n×m是由拉普拉斯機(jī)制(Laplace mechanism,簡(jiǎn)稱LM)和高斯機(jī)制(Gaussian mechanism,簡(jiǎn)稱GM)[20]產(chǎn)生的.相應(yīng)的常數(shù)c分別為1和.由于SNP二倍體基因型矩陣存儲(chǔ)(xij)n×m中元素xij∈{0,1,2},這里暫且將xij看作字符型,簡(jiǎn)單地定義基因型xij的效用函數(shù)為u:xij→xij,也就是說,u(xij=0)=0,u(xij=1)=1和u(xij=2)=2,那么效用函數(shù)的敏感度為Δu=2,因此在指數(shù)機(jī)制下選取基因型值0、1和2的概率分別正比于1、eε/4和eε/2.因?yàn)镾NP基因型矩陣及其對(duì)應(yīng)的效用矩陣的元素都是0、1和2,所以通過指數(shù)機(jī)制選擇基因型值 0、1和 2的隨機(jī)性較差,那么在 SNP基因型數(shù)據(jù)的這種效用函數(shù)定義方式下,使用指數(shù)機(jī)制將導(dǎo)致基因型數(shù)據(jù)及其相關(guān)的敏感信息泄露,因此本文沒有考慮指數(shù)機(jī)制(exponential mechanism,簡(jiǎn)稱EM)[20].

算法1.在SNP連鎖不平衡下的矩陣差分隱私.

3 矩陣差分隱私的分析

下面從理論上分析矩陣差分隱私的性質(zhì).

定理1.矩陣差分隱私是差分隱私.

為了分析矩陣差分隱私的效用,因?yàn)镾= (sij)n×m?Range(M),本文使用度量矩陣差分隱私機(jī)制的效用[18].

定理 2.矩陣差分隱私的效用在[R0,1]區(qū)間,R0表示隱私預(yù)算ε最小時(shí)矩陣差分隱私下噪音矩陣中模 3余 0元素?cái)?shù)量的百分比值.

證明:首先考慮3種極端的情況.

(1) 當(dāng)噪音矩陣Y=(yij)n×m的所有元素滿足round(yij) mod 3=0時(shí),round((yij)n×m)的所有元素都模 3同余 0.因此,在(xij)n×m與(sij)n×m?Range(M)之間的所有 SNP二倍體基因型數(shù)據(jù)相同.因此,矩陣差分隱私機(jī)制的最大效用為1.

(2) 當(dāng)噪音矩陣Y=(yij)n×m的所有元素滿足round(yij) mod 3≡1時(shí),(0+1) mod 3≡1,(1+1) mod 3≡2和(2+1) mod 3≡0.因此,(xij)n×m與(sij)n×m?Range(M)之間的所有 SNP二倍體基因型取值都不相同,此時(shí)矩陣差分隱私機(jī)制的效用是0.

(3) 當(dāng)噪音矩陣Y=(yij)n×m的所有元素滿足round(yij) mod 3≡2時(shí),(0+2) mod 3≡2,(1+2) mod 3≡0和(2+2) mod 3≡1.因此,(xij)n×m與(sij)n×m?Range(M)之間的所有 SNP二倍體基因型取值也都不相同,此時(shí)矩陣差分隱私機(jī)制的效用是0.

上述證明中考慮(2)和(3)兩種極端情況,使矩陣差分隱私下基因數(shù)據(jù)的效用為 0.然而,由于噪音的隨機(jī)性,矩陣差分隱私下基因數(shù)據(jù)的最小效用是大于0的,詳見第4.4節(jié)基因數(shù)據(jù)的效用分析.下面考慮第4種情況.

(4) 在矩陣差分隱私中,由于隱私預(yù)算ε越小,鄰近基因數(shù)據(jù)矩陣的不可區(qū)分性越好,進(jìn)而矩陣差分隱私保護(hù)越強(qiáng),那么基因數(shù)據(jù)的效用達(dá)到最低.在矩陣差分隱私中基因數(shù)據(jù)的效用與模 3余 0的噪音數(shù)量的百分比值是一致的.也就是說,如果隱私預(yù)算ε最小,矩陣差分隱私產(chǎn)生模 3余 0的噪音數(shù)量百分比值為R0(1＞R0＞0),那么基因數(shù)據(jù)的最小效用為R0.反之,隱私預(yù)算ε越大,基因數(shù)據(jù)效用可達(dá)到百分比值1.

綜上,由于噪音的隨機(jī)性,矩陣差分隱私機(jī)制的效用屬于區(qū)間[R0,1]. □

定理3.考慮連鎖不平衡、矩陣加運(yùn)算和模余運(yùn)算的計(jì)算復(fù)雜度分別為O(n×m2)、O(n×m)和O(n×m).矩陣差分隱私的計(jì)算復(fù)雜度如下:(1) 當(dāng)n=m時(shí),矩陣差分隱私的計(jì)算復(fù)雜度為O(n3)；(2) 當(dāng)n＞m時(shí),矩陣差分隱私的計(jì)算復(fù)雜度為O(nm2)；(3) 當(dāng)n

證明:在矩陣差分隱私中,產(chǎn)生隨機(jī)噪音是有效的,忽略其計(jì)算復(fù)雜度,而計(jì)算連鎖不平衡、矩陣加運(yùn)算和模余運(yùn)算分別需要8n×(m2-m)、n×m和n×m次運(yùn)算,考慮3種情況.

(1) 當(dāng)n=m時(shí),矩陣差分隱私的計(jì)算復(fù)雜度為O(n3).

(2) 當(dāng)n＞m時(shí),矩陣差分隱私的計(jì)算復(fù)雜度為O(nm2).

(3) 當(dāng)n

總之,矩陣差分隱私滿足差分隱私的定義,同時(shí)具有效用屬于區(qū)間[R0,1],其中,R0是矩陣差分隱私下隱私預(yù)算最小時(shí)噪音矩陣中模3余0元素?cái)?shù)量的百分比值,并且矩陣差分隱私的計(jì)算復(fù)雜度是多項(xiàng)式時(shí)間的.

4 實(shí)驗(yàn)分析

本文在矩陣差分隱私下選擇拉普拉斯分布和高斯分布來進(jìn)行實(shí)驗(yàn)分析.首先進(jìn)行噪音分析,然后與拉普拉斯機(jī)制和高斯機(jī)制比較分析矩陣差分隱私保護(hù)模型的隱私和效用.在所有的實(shí)驗(yàn)分析中,考慮SNP二倍體基因型數(shù)據(jù)的特點(diǎn),初始化SNP連鎖不平衡的相關(guān)系數(shù)為rij=1和敏感度Δf=2.另外,分別初始化隱私預(yù)算ε=0.001和概率值δ=0.01.

4.1 數(shù)據(jù)集

國(guó)際人類基因組單體型圖計(jì)劃(Int’l Hapmap Project)的數(shù)據(jù)是公開可用的[21],本文使用2010年5月發(fā)布的階段III的165個(gè)CEU(utah residents with northern and Western European ancestry from the CEPH collection)群體的22號(hào)染色體的基因型和頻率數(shù)據(jù)集.在實(shí)驗(yàn)分析之前,基于頻率數(shù)據(jù)集預(yù)處理基因型數(shù)據(jù)集,將 SNP二倍體基因型數(shù)據(jù)編碼為0、1和2.在CEU基因型數(shù)據(jù)集中,將丟失的數(shù)據(jù)’NN’用0代替.本文分別選擇500、1 000和1 500個(gè)SNP位點(diǎn)進(jìn)行實(shí)驗(yàn)分析.

4.2 噪音分析

Fig.3 The percentage of noises matrix entries module 3 satisfying the residue to be 0 for matrix differential privacy圖3 矩陣差分隱私下噪音矩陣模3余0的元素?cái)?shù)量的百分比值

4.3 隱私分析

為了評(píng)估基因隱私保護(hù)模型的隱私,對(duì)于擁有全背景知識(shí)的攻擊者,本文定義標(biāo)準(zhǔn)化期望估計(jì)誤差作為隱私度量.因?yàn)樵豿ij在矩陣差分隱私下的隨機(jī)擾動(dòng)元素為sij,因此,定義基因數(shù)據(jù)的隱私度量為

通過比較,我們來分析矩陣差分隱私與拉普拉斯機(jī)制、高斯機(jī)制的標(biāo)準(zhǔn)化期望估計(jì)誤差.如圖 4和圖 5所示,矩陣差分隱私、拉普拉斯機(jī)制和高斯機(jī)制的標(biāo)準(zhǔn)化期望估計(jì)誤差都隨隱私預(yù)算的增大而減小.主要原因是,隱私預(yù)算越大,拉普拉斯分布和高斯分布的方差越小,矩陣差分隱私產(chǎn)生模3余0的噪音越多.因此拉普拉斯機(jī)制和高斯機(jī)制直接添加噪音到 SNP基因型數(shù)據(jù)會(huì)導(dǎo)致效用災(zāi)難,而矩陣差分隱私通過噪音模余運(yùn)算提高了SNP基因型數(shù)據(jù)的效用,見第4.4節(jié)矩陣差分隱私的效用分析.由此,矩陣差分隱私實(shí)現(xiàn)了基因數(shù)據(jù)的隱私保護(hù),不過,隱私保護(hù)強(qiáng)度顯然低于拉普拉斯機(jī)制和高斯機(jī)制.另外,由圖4和圖5可知,隨著隱私預(yù)算的增加,高斯機(jī)制的標(biāo)準(zhǔn)化期望誤差較拉普拉斯機(jī)制要大,為了更好地權(quán)衡隱私和效用,可以選擇拉普拉斯機(jī)制實(shí)現(xiàn)矩陣差分隱私.

Fig.4 The normalized expected estimation error for matrix differential privacy圖4 矩陣差分隱私下的標(biāo)準(zhǔn)化期望估計(jì)誤差

Fig.5 The normalized expected estimation error for Laplace mechanism and Gaussian mechanism圖5 拉普拉斯機(jī)制和高斯機(jī)制下的標(biāo)準(zhǔn)化期望估計(jì)誤差

因此,根據(jù)SNP連鎖不平衡下差分隱私的不可區(qū)分性,矩陣差分隱私實(shí)現(xiàn)了SNP基因型數(shù)據(jù)和SNP連鎖不平衡的隱私保護(hù).

4.4 效用分析

盡管矩陣差分隱私可以實(shí)現(xiàn)SNP基因型數(shù)據(jù)的隱私保護(hù),考慮到SNP基因型數(shù)據(jù)的分析,因此還需要分析SNP基因型數(shù)據(jù)的效用.在矩陣差分隱私中,對(duì)于原始的 SNP基因型數(shù)據(jù)(xij)n×m和擾動(dòng)后的 SNP基因型數(shù)據(jù)(sij)n×m,根據(jù)作為效用度量方法實(shí)驗(yàn)分析基因數(shù)據(jù)的效用.

如圖6所示,隨著隱私預(yù)算的增加,矩陣差分隱私保護(hù)模型下的基因數(shù)據(jù)效用遞增,并且增長(zhǎng)到100%保持不變.這是因?yàn)?隨著隱私預(yù)算增大,拉普拉斯分布和高斯分布的方差變小,矩陣差分隱私產(chǎn)生模3余0的噪音就更多.當(dāng)隱私預(yù)算較小時(shí),基于拉普拉斯機(jī)制的矩陣差分隱私可以實(shí)現(xiàn)更好的基因數(shù)據(jù)效用,以此保證較好的計(jì)算不可區(qū)分性,進(jìn)而實(shí)現(xiàn)更好的差分隱私保護(hù).例如,當(dāng)ε=7時(shí),基于拉普拉斯機(jī)制的基因數(shù)據(jù)效用可以達(dá)到80%,而基于高斯機(jī)制的基因數(shù)據(jù)效用為40%,這與圖3中拉普拉斯機(jī)制和高斯機(jī)制產(chǎn)生噪音矩陣的四舍五入近似值模3余0的噪音數(shù)量的百分比值是一致的.而圖7中隨著隱私預(yù)算的增加,基因組數(shù)據(jù)的效用保持0不變.這是因?yàn)?拉普拉斯機(jī)制和高斯機(jī)制直接添加噪音到基因數(shù)據(jù),破壞了基因數(shù)據(jù)效用,導(dǎo)致基因數(shù)據(jù)效用災(zāi)難.由此可知,矩陣差分隱私比拉普拉斯機(jī)制和高斯機(jī)制更適合于基因數(shù)據(jù)的隱私保護(hù).

Fig.6 The genome data utility for matrix differential privacy圖6 矩陣差分隱私下的基因數(shù)據(jù)效用

Fig.7 The genome data utility for Laplace mechanism and Gaussian mechanism圖7 拉普拉斯機(jī)制和高斯機(jī)制下的基因數(shù)據(jù)效用

因此,矩陣差分隱私相比于拉普拉斯機(jī)制和高斯機(jī)制更適合于基因數(shù)據(jù)的隱私保護(hù),保證了基因數(shù)據(jù)和SNP連鎖不平衡的隱私保護(hù)與基因數(shù)據(jù)效用之間的權(quán)衡.在表1中,通過比較分析,總結(jié)矩陣差分隱私與拉普拉斯機(jī)制、高斯機(jī)制的相關(guān)性質(zhì).其中,最小效用R0表示矩陣差分隱私在最小隱私預(yù)算下所有模3余0的噪音數(shù)量的百分比值.

Table 1 The comparison among matrix differential privacy,Laplace mechansim and Gaussian mechanism表1 矩陣差分隱私與拉普拉斯機(jī)制、高斯機(jī)制的比較

5 結(jié) 論

為了保護(hù)SNP連鎖不平衡下基因關(guān)聯(lián)的敏感信息,本文提出了矩陣差分隱私保護(hù)模型.該模型滿足差分隱私,同時(shí)保證基因數(shù)據(jù)效用在[R0,1]區(qū)間,其中,R0是矩陣差分隱私在隱私預(yù)算最小時(shí)噪音矩陣中模3余0的噪音數(shù)量的百分比值,并且矩陣差分隱私是多項(xiàng)式時(shí)間計(jì)算有效的.

對(duì)于基因數(shù)據(jù),基因隱私保護(hù)模型在連鎖不平衡下保證隱私是可行的.通過結(jié)合矩陣加運(yùn)算、SNP連鎖不平衡下差分隱私的定義和模余運(yùn)算,提出了向量差分隱私和矩陣差分隱私,并且向量差分隱私是矩陣差分隱私的特例.根據(jù)矩陣差分隱私的性質(zhì),為了疾病標(biāo)記發(fā)現(xiàn),基因隱私保護(hù)模型可以用于 DNA數(shù)據(jù)集的差分隱私選擇[15]；在 GWAS中,矩陣差分隱私也可以對(duì)基于隱私編輯距離相似患者查詢提供隱私保護(hù)[12]；矩陣差分隱私阻止從GWAS統(tǒng)計(jì)值中識(shí)別特定的個(gè)體[16]；并且,矩陣差分隱私可以實(shí)現(xiàn)隱私保護(hù)罕見疾病變異分析[8]；矩陣差分隱私在基因組串搜索中是有效的隱私保護(hù)方法[11].更進(jìn)一步說,在矩陣差分隱私下可以實(shí)現(xiàn)宏基因組分析[13].因此,矩陣差分隱私可以推廣到基因數(shù)據(jù)收集、搜索和序列配對(duì)等應(yīng)用的隱私保護(hù)中.

在矩陣差分隱私中,可以通過行劃分、列劃分或者其他快速矩陣計(jì)算方法[22]降低其計(jì)算復(fù)雜度,進(jìn)而提高計(jì)算效率.另外,考慮高階的SNP連鎖不平衡,Samani等人[23]表明了對(duì)隱藏SNP的個(gè)體基因數(shù)據(jù)具有更強(qiáng)的推斷攻擊.Tramèr等人[17]考慮有界先驗(yàn)知識(shí)的差分隱私,并應(yīng)用于GWAS.通過孟德爾定律、基因變異之間的統(tǒng)計(jì)關(guān)系和基因與表型之間的統(tǒng)計(jì)關(guān)系,在個(gè)體的基因組或表型被觀察到的情況下,Humbert等人[4]詳述了重構(gòu)攻擊推斷該個(gè)體的親戚的基因組.相比較考慮攻擊者的背景知識(shí),本文僅考慮了SNP連鎖不平衡下基因隱私保護(hù).在下一步的工作中,研究SNP連鎖不平衡下具有先驗(yàn)知識(shí)的基因隱私保護(hù)模型,除了考慮成對(duì)SNP連鎖不平衡外,還需要考慮高階的SNP連鎖不平衡,并考慮攻擊者更多的先驗(yàn)知識(shí),包括可利用的基因數(shù)據(jù)、個(gè)體的血緣關(guān)系以及重組規(guī)則等.