基于局部優(yōu)化與二分圖匹配的PPI網(wǎng)絡比對算法

祝 家 燁

(復旦大學計算機科學技術(shù)學院上海市智能信息處理重點實驗室 上海 200433)

0 引 言

生物學研究的一個重要目標，就是理解生命細胞中各個組成部分的功能以及它們之間的聯(lián)系。其中，蛋白質(zhì)是具有極其重要意義的生物結(jié)構(gòu)，它有助于理解細胞作用的機理。

不同的蛋白質(zhì)之間，往往會發(fā)生相互作用，來完成某種生物功能。發(fā)現(xiàn)并理解蛋白質(zhì)之間的相互作用PPIs(protein-protein interactions)，是生物學領(lǐng)域內(nèi)的重要課題之一。伴隨著這一課題，學者們設計了許多生物學實驗[1-5]，這些實驗的目的，便是發(fā)現(xiàn)蛋白質(zhì)之間的相互作用結(jié)構(gòu)。而后，學者們又提出了蛋白質(zhì)相互作用網(wǎng)絡這一圖論模型，對蛋白質(zhì)之間的相互作用進行建模分析。通過比對不同生物的PPI 網(wǎng)絡，可以將一種生物的蛋白質(zhì)知識體系結(jié)構(gòu)，借鑒于另一種生物。

PPI 網(wǎng)絡比對，是將兩個不同物種的PPI 網(wǎng)絡進行點對匹配的過程，匹配的目的在于找到兩個PPI 網(wǎng)絡中相似度較高的一些區(qū)域。因此，PPI 網(wǎng)絡比對的好壞，會影響蛋白質(zhì)分析的結(jié)果。

PPI網(wǎng)絡比對分為局部比對和全局比對，本文的研究重點在于后者。

PPI網(wǎng)絡比對涉及到的一個子問題，即圖論中的子圖同構(gòu)問題，被證明是NP完全問題，因此，所有PPI網(wǎng)絡比對算法，都是啟發(fā)式的算法。尋找一個好的比對算法，顯得尤為重要。

到現(xiàn)在為止，已經(jīng)有許多全局比對算法被提出，經(jīng)典的算法如IsoRank算法[6]，它是全局比對算法中的先驅(qū)，其兩步走的策略為之后所有的全局比對算法所借鑒，具有開拓性的意義。IsoRank算法首先衡量兩個PPI網(wǎng)絡任意點對之間的相似度，然后利用這一指標，來指導PPI網(wǎng)絡之間的比對。相似度的衡量基于節(jié)點網(wǎng)絡結(jié)構(gòu)的相似性以及節(jié)點所代表的蛋白質(zhì)的序列相似性。而指導比對的過程，則是一個貪心的啟發(fā)式策略。

GRAAL系列算法[7-11]也是經(jīng)典的全局比對算法。不同于IsoRank算法的是，其利用了小圖度數(shù)這一指標，來衡量兩個PPI網(wǎng)絡的任意節(jié)點對間的相似度，并使用多種啟發(fā)式策略，來對PPI網(wǎng)絡進行比對。L-GRAAL算法[9]是該系列算法中最近被提出的。L-GRAAL算法的貢獻在于，它把網(wǎng)絡比對的問題建模成一個整數(shù)規(guī)劃問題，并且加以解決。

SPINAL算法[12]，也定義了兩個節(jié)點間的相似度，不過在衡量相似度的過程中，它利用了二分圖匹配模型來進行優(yōu)化。并且，SPINAL算法進行網(wǎng)絡比對的過程，也利用了這一模型。

MAGNA算法[13]則是一種基于遺傳算法[15]的PPI網(wǎng)絡比對算法。

PROPER算法[14]大膽做出了一個假設，即蛋白質(zhì)序列的高相似度，代表著功能的高相似度。因此，PROPER優(yōu)先挑選出具有高序列相似度的點對進行匹配，將其作為基礎(chǔ)比對結(jié)果，然后在該結(jié)果上，逐步完善PPI網(wǎng)絡之間的比對結(jié)果。

衡量一個比對算法的好壞，有一些常見的衡量指標如EC指標、ICS指標、S3指標、TWEC指標等[16]。

本文的工作，LOBM，基于這些已有比對算法的結(jié)果，嘗試用一種局部優(yōu)化的策略，來調(diào)整這些已有算法的比對結(jié)果，進一步提高各項指標。而局部優(yōu)化的過程，利用了圖論中的二分圖匹配模型。最后，本文對真實數(shù)據(jù)進行了實驗測試，結(jié)果顯示，LOBM相比既有的比對算法在效果上有明顯的提高。

1 問題定義與算法設計

本節(jié)先給出相關(guān)概念及問題的形式化定義，然后介紹本文的算法LOBM。

1.1 相關(guān)概念及問題定義

定義1圖G=(V,E)為一個PPI網(wǎng)絡，其中V是點集，其中每個點v∈V代表一種蛋白質(zhì)，E是一個V×V的邊集，一條邊(u,v)∈E代表蛋白質(zhì)u和v具有相互作用。

由定義1可知本文中PPI網(wǎng)絡是一個無權(quán)無向圖。下面給出全局網(wǎng)絡比對的定義。

定義2兩個PPI網(wǎng)絡G1(V1,E1)，G2(V2,E2)的全局網(wǎng)絡比對(不失一般性，|V1|≤|V2|)是一個從點集V1到點集V2的單射f:V1→V2。在全局網(wǎng)絡比對f下，令v1∈V1為圖G1中的一個點，f(v1)∈V2，稱為v1在G2中對應的匹配點，同理v1也是f(v1)對應的匹配點。稱(v1,f(v1))為一對匹配點對。

f(V1)={f(v)∈V2:v∈V1}是G1中所有點在G2中的匹配點組成的集合，稱為G2在f下的匹配點集。稱G1為源網(wǎng)絡，G2為目標網(wǎng)絡。

本文簡稱全局網(wǎng)絡比對為比對。

定義3一個比對f的比對集合為set(f)={(v,f(v)):v∈V1,f(v)∈V2}。對于V1中的一個點v，如果f(v)∈V2，即v是已經(jīng)被匹配的點，則稱點v屬于比對集合set(f)，用v∈set(f)來表示，對于V2中的點也是同理。如果一個點對(v1,v2),v1∈V1,v2∈V2是一個匹配點對(f(v1)=v2)，則(v1,v2)∈set(f)，否則(v1,v2)?set(f)。

由定義3可知，比對集合與比對是一一對應的，一個比對對應一個比對集合，而一個比對集合，也代表了一個比對。為了構(gòu)造一個比對，只要構(gòu)造出對應的比對集合即可。

定義4在比對f下，對于一條源網(wǎng)絡G1中的邊(u,v)∈E1，如果有(f(u),f(v))∈E2，則稱邊(u,v)在f下是被保留的邊，簡稱保留邊。并且稱其在G2中對應的邊(f(u),f(v))為映射邊。則f(E1)={(f(u),f(v))∈E2:(u,v)∈E1}稱為E1在G2中的映射邊集合。

由定義4可知，映射邊和保留邊是一一對應的，兩個集合的大小相同。f(E1)的大小就是E1中的邊在比對后被保留下來的數(shù)量。

定義5對于一個圖G(V,E)，有一個點集V的子集X?V，令G[X]為圖G中點集X的導出子圖，即G[X]=(X,E(G[X]))，其中邊集為E(G[X])={ (u,v):u∈X,v∈X,(u,v)∈E}。

如何衡量一個比對的好壞，是網(wǎng)絡比對中一個重要的問題。到目前為止，有許多不同的網(wǎng)絡比對衡量指標，常見的有：

EC指標：

(1)

ICS指標：

(2)

S3指標：

(3)

TWEC指標：

(4)

基于PPI網(wǎng)絡比對的概念以及比對衡量指標，下面給出網(wǎng)絡比對的問題定義。

問題1對于兩個PPI網(wǎng)絡G1(V1,E1),G2(V2,E2)，以及一個比對衡量標準Q，要求一個全局比對f，使得在比對f下，Q的指標最大化。

1.2 LOBM算法設計

根據(jù)四個衡量指標的定義公式：式(1)-式(4)，分子都是|f(E1)|，根據(jù)定義4，其意義為源網(wǎng)絡的保留邊集合的大小。為了敘述方便，本文定義該值為一個新的網(wǎng)絡比對衡量指標，稱為CE(conserved edges)指標。CE指標最大化，便是LOBM算法的目標。

LOBM算法可以結(jié)合已有的比對算法，通過局部優(yōu)化的方法，來改進已有算法的比對結(jié)果。其大致思路為：對一個已有的比對結(jié)果f，每一輪迭代，算法嘗試去調(diào)整比對f，使得調(diào)整后的比對f的CE指標獲得提高，通過一定的迭代輪數(shù)以后，最后得到的f，其CE指標一定會好于一開始的比對結(jié)果。

每一輪迭代，LOBM會隨機刪去一部分匹配點對，然后利用二分圖最大匹配的模型，構(gòu)造一個新的匹配點對集合，并且加入到比對集合中形成一個新的比對結(jié)果。如果刪去的匹配點對過多，則會導致調(diào)整時間變長，從而影響一輪迭代的時間，反之，如果刪去的匹配點對過少，可能會導致單次調(diào)整的效果變差。因此，LOBM算法設置了一個參數(shù)β來控制每輪迭代刪去的匹配點對個數(shù)。

理論上，LOBM可以無限迭代下去，且比對的效果不會變差。但是，比對的效果不會無限提高，整個LOBM算法肯定會有一個收斂的過程。同時，考慮到運行時間的因素，應當控制LOBM的迭代輪數(shù)，使其做到既可以產(chǎn)生較好的比對結(jié)果，又能有較快的運行時間。因此，LOBM算法設置了一個參數(shù)α來進行迭代輪數(shù)的控制。算法1給出了整個LOBM算法的偽代碼。

算法1基于二分圖匹配的局部優(yōu)化算法

1：輸入：兩個PPI網(wǎng)絡G1、G2，比對f，參數(shù)α、β，設置兩個參數(shù)的意義可見算法設計部分。

2：輸出：調(diào)整后的比對fp

3：fp←f

4：T←0

5：WhileT<α

6:T←T+1

7：oldfp←fp

8:ds←從set(fp)中隨機挑選的β*|set(fp)|個匹配點對

9： ?(u,v)∈ds,fp←ADJfp((u,v))

10：bg←WBG({V1set(fp)}, {V2set(fp)},{Ffp(u,v)})

11：M←MaximumWMatching(bg)

12： ?(u,v)∈M,fp←ADJfp((u,v))

13： IfCE(fp)

14:fp←oldfp

15： EndIf

16：EndWhile

算法1的第3和第4行是初始化過程，T是當前的迭代輪次。

第5行到最后，是整個算法的一輪迭代，是對f的一次調(diào)整過程。α是一個控制算法迭代輪數(shù)的參數(shù)。迭代輪數(shù)越多，算法運行時間越久。

第8行到第9行，算法從當前比對集合中隨機挑選出若干匹配點對，然后將這些匹配點對從比對集合中刪除，操作ADJfp((u,v))參見定義5。刪除的匹配點對的數(shù)量，由參數(shù)β控制。

第10行，算法利用兩個PPI網(wǎng)絡中沒有得到匹配的點，構(gòu)造出一個帶權(quán)二分圖WBG。其中二分圖的左邊頂點集合由V1中沒有得到匹配的點構(gòu)成，右邊頂點集合由V2中沒有得到匹配的點構(gòu)成。而WBG中任意點對(u,v)的權(quán)重則由函數(shù)Ffp(u,v)的值確定，參見定義6。

第11行到第12行，計算得到WBG的最大權(quán)重匹配集合，匹配集合中的每一個匹配點對，都被當成新的匹配點對加入到當前的比對集合中。

第13行到第14行，算法比較調(diào)整前后的比對的CE指標，如果指標提高，則保留調(diào)整結(jié)果，否則，開始新一輪的迭代。

定義6當前的比對為f。ADJf((u,v))表示對當前比對進行調(diào)整。有兩種情況，第一種(u,v)?set(f)，則調(diào)整操作將匹配點對(u,v)加入比對集合f，第二種(u,v)∈set(f)，則調(diào)整操作將匹配點對(u,v)從比對集合中刪除。

定義7當前的比對為f，則Ff(i,j)=|{ (u,v):u∈N(i),v∈N(j),(u,v)∈set(f)}|稱為點對(i,j)在已有比對f下的貢獻值。其中N(i)表示點i的鄰居點構(gòu)成的集合。

根據(jù)定義7，匹配點對的貢獻值，其本質(zhì)就是比對f在增加了這一匹配點對后，保留邊數(shù)目的增加值。匹配點對(u,v)的貢獻值越高，其加入到比對集合set(f)中形成的比對結(jié)果傾向于擁有更高的CE指標。二分圖最大權(quán)重匹配模型，保證了每次挑選出來的匹配點對集合，擁有最大的貢獻值總量。

2 實驗分析

實驗所用的數(shù)據(jù)均來自Isobase數(shù)據(jù)庫[16]。Isobase數(shù)據(jù)庫是被普遍使用的生物PPI網(wǎng)絡數(shù)據(jù)庫。本文挑選了四種生物的PPI網(wǎng)絡數(shù)據(jù)，每種生物的PPI網(wǎng)絡結(jié)構(gòu)信息見表1。所有的網(wǎng)絡數(shù)據(jù)都經(jīng)過預處理，每個PPI網(wǎng)絡去除了自環(huán)、重邊以及獨立的節(jié)點。

表1 Isobase數(shù)據(jù)庫關(guān)于四種生物的PPI網(wǎng)絡數(shù)據(jù)

為了敘述方便，用簡寫來替代物種名稱，C.elegans簡寫為ce，D.melanogaster簡寫為dm，H.sapiens簡寫為hs，S.cerevisiae簡寫為sc。

2.1 實驗環(huán)境與方法

本文使用全局網(wǎng)絡比對算法中的IsoRank[6]，SPINAL[12]，L-GRAAL[9]和PROPER[14]算法來和LOBM進行比較，四種算法的介紹可參見本文引言部分。每一種算法產(chǎn)生的網(wǎng)絡比對，將采用不同的比對衡量標準來進行比較。LOBM算法全部代碼由Java構(gòu)成，并且運行在Linux Ubuntu環(huán)境下，詳細的環(huán)境參數(shù)見表2。

表2 實驗運行環(huán)境

實驗中用到的比對衡量標準，CE指標為首要衡量指標，因為它是LOBM算法的目標。其次，EC、ICS、S3和TWEC這四個指標是被正式認可的指標，也需要進行比較。

2.2 參數(shù)α、β的影響

正如前文所述，α、β作為LOBM算法的重要參數(shù)，會影響LOBM算法的調(diào)整效果與運行時間，本文通過實驗來說明兩個參數(shù)對它們的影響。并且，本文采用了效果較好的一組參數(shù)作為之后實驗的默認參數(shù)。

為了敘述方便，用生物名稱1-生物名稱2表示對生物1和生物2的PPI網(wǎng)絡進行比對，例如ce-dm就是將生物ce的PPI網(wǎng)絡與生物dm的PPI網(wǎng)絡進行比對，以此類推。

2.2.1 參數(shù)β的影響

參數(shù)β會影響LOBM算法運行的時間與調(diào)整的效果。然而，同樣的時間下，肯定是選擇具有更好調(diào)整效果的β。為此，參數(shù)α被設定為一個很大的值，目的是讓LOBM算法可以無限迭代。實驗在不同β值的情況下，讓LOBM算法運行一段時間后，計算比對的CE指標。由于LOBM在長時間運行后可能會收斂，CE指標不發(fā)生變化，因此，采用短的運行時間，更利于觀測β值對調(diào)整效果的影響。

圖1是不同運行時間下，LOBM算法在不同β值的情況下，在ce-dm實驗中優(yōu)化IsoRank算法的調(diào)整結(jié)果。β(實際值)代表每輪迭代時刪除的匹配點對的數(shù)目(而不是比例)。圓點曲線表示β從0.1變化到0.6時，LOBM算法的運行結(jié)果。該曲線表明，在同樣的運行時間下，CE指標呈逐漸下降趨勢，意味著LOBM不適合β過大的情況。

圖1 LOBM在不同β值時運行10、20、30、40、50、60 s的結(jié)果

三角形曲線表示β從5到45變化時，LOBM算法的運行結(jié)果。該曲線表明，在同樣的運行時間下，CE指標沒有明顯的變化趨勢，意味著較小的β對于LOBM算法的調(diào)整效果比較穩(wěn)定，而且，這種情況下β稍微大點的效果會比較好。最后，本文采用β=35作為LOBM算法的默認參數(shù)。

2.2.2 參數(shù)α的影響

實驗使用β=35來運行LOBM算法，并且記錄每輪迭代后當前比對的CE指標與前一次CE指標的差值。

圖2是LOBM算法在實驗組ce-dm上優(yōu)化IsoRank算法的實驗結(jié)果。實驗表明，在迭代2 000輪以后，CE指標的差值基本只在0、1、2浮動，偶爾會變成3。并且，隨著迭代輪數(shù)的增加，CE指標提高的機會越來越少(圖中空隙越來越大)。大概在14 000輪迭代之后，CE指標趨于收斂。最后，本文采用α=14 000作為之后實驗的默認參數(shù)。

圖2 LOBM每輪迭代時的比對指標(ΔCE)

2.3 不同算法之間的比較

本文主要使用四種比對算法與LOBM進行比較，可以參見實驗環(huán)境與方法部分。四種比對算法的詳細參數(shù)見表3。PPI網(wǎng)絡比對實驗共有6組，分別是ce-dm、ce-hs、cs-sc、dm-hs、dm-sc、hs-sc。每組實驗都先用四種比對算法，求得初始比對f，然后以f為基礎(chǔ)，運行LOBM算法，得到新的比對。

表3 四種比對算法的命令行參數(shù)

圖3為LOBM與四種比對算法的比較結(jié)果。實驗表明，四種比對算法的比對結(jié)果各有好壞，IsoRank算法的結(jié)果最差，L-GRAAL算法的最好，SPINAL算法和PROPER算法的結(jié)果則沒有明顯的差距。而LOBM都能在它們已有的結(jié)果上優(yōu)化它們，提高CE指標。

圖3 LOBM與四種比對算法的CE值標比較

圖4為LOBM與四種比對算法在CE指標上的提高程度，即：

(5)

圖4 LOBM對四種比對算法的CE值標提高程度

可以看到LOBM對IsoRank算法的結(jié)果有明顯的提高，對SPINAL算法和PROPER算法能夠達到40%～60%，而對L-GRAAL算法，則稍差一點，為20%～40%。從中可以看到LOBM算法的優(yōu)勢。

2.4 EC、ICS、S3、TWEC指標的比較

圖5是LOBM算法與四種比對算法在其他指標下的結(jié)果比較(指標提高程度)。

圖5 LOBM在四項指標上對已有比對算法的提高程度

實驗表明，LOBM對IsoRank算法的結(jié)果依舊有非常明顯的提高。除了IsoRank以外的三種比對算法的結(jié)果，在多數(shù)情況下也都有不錯的提高，比較之下，LOBM對SPINAL算法和PROPER算法的提高相差不大，對L-GRAAL算法的提高則相對較低。值得一提的便是提高呈負效果的情況。

根據(jù)ICS和S3的定義式(2)、式(3)，ICS指標與目標網(wǎng)絡有關(guān)，S3指標則與兩個網(wǎng)絡都有關(guān)。由于CE指標衡量的是源網(wǎng)絡中被保留的邊數(shù)，因此，CE指標的提高不一定代表著ICS指標和S3指標的提高。實驗結(jié)果也反應了這個情況：前三組實驗中，LOBM對SPINAL、PROPER以及L-GRAAL算法在ICS指標上的提高效果為負值，且出現(xiàn)了5次。而S3則相對較好，只出現(xiàn)了2次。后三組試實驗中，情況則比較樂觀。

理論上看，LOBM算法的目的是最大化CE指標，CE指標越大，意味著源網(wǎng)絡有更多的邊成為了保留邊，因此對于EC這個只考慮源網(wǎng)絡結(jié)構(gòu)的指標，LOBM能產(chǎn)生很好的提高效果。而ICS是只考慮目標網(wǎng)絡結(jié)構(gòu)的指標，著重衡量目標網(wǎng)絡中被匹配邊的稀疏程度，在目標網(wǎng)絡是稠密網(wǎng)絡的情況下，以最大化CE指標為目的的LOBM算法則顯得時好時壞。剩下的S3和TWEC指標，同時考慮了源網(wǎng)絡和目標網(wǎng)絡，LOBM對它們的提高效果，敏感程度不如ICS來得高，這一點從實驗結(jié)果中也能得到證明。

3 結(jié) 語

本文著眼于PPI網(wǎng)絡比對問題，設計并實現(xiàn)了一種能夠提高既有比對算法結(jié)果的局部調(diào)優(yōu)算法LOBM。通過最大化CE指標，LOBM能夠不斷調(diào)整PPI網(wǎng)絡比對，大幅提高各項指標。LOBM可以與任何已有的比對算法相結(jié)合，是一種比較通用的比對優(yōu)化框架。

[1] Ito T, Chiba T, Ozawa R, et al. A comprehensive two-hybrid analysis to explore the yeast protein interactome[J]. Proceedings of the National Academy of Sciences, 2001, 98(8):4569-4574.

[2] Krogan N J, Cagney G, Yu H, et al. Global landscape of protein complexes in the yeast Saccharomyces cerevisiae[J]. Nature, 2006, 440(7084):637-643.

[3] Han J D J, Bertin N, Hao T, et al. Evidence for dynamically organized modularity in the yeast protein-protein interaction network[J]. Nature, 2004,430(6995):88-93.

[4] Nabieva E, Jim K, Agarwal A, et al. Whole-proteome prediction of protein function via graph-theoretic analysis of interaction maps[J]. Bioinformatics, 2005, 21(suppl 1):i302-i310.

[5] Yook S H, Oltvai Z N, Barabási A L. Functional and topological characterization of protein interaction networks[J]. Proteomics, 2004, 4(4):928-942.

[6] Singh R, Xu J, Berger B. Global alignment of multiple protein interaction networks with application to functional orthology detection[J]. Proceedings of the National Academy of Sciences, 2008, 105(35): 12763-12768.

[8] Kuchaiev O, Pr?ulj N. Integrative network alignment reveals large regions of global network similarity in yeast and human[J]. Bioinformatics, 2011, 27(10):1390-1396.

[9] Malod-Dognin N, Pr?ulj N. L-GRAAL: Lagrangian graphlet-based network aligner[J]. Bioinformatics, 2015, 31(13):2182-2189.

[14] Kazemi E, Hassani H, Grossglauser M, et al. PROPER: global protein interaction network alignment through percolation matching[J]. BMC bioinformatics, 2016,17(1):527.

[15] Back T. Evolutionary algorithms in theory and practice: evolution strategies, evolutionary programming, genetic algorithms[M]. Oxford university press, 1996.

[16] D?pmann C. Survey on the Graph Alignment Problem and a Benchmark of Suitable Algorithms[D]. Institut für Informatik, 2013.

[17] Park D, Singh R, Baym M, et al. IsoBase: a database of functionally related proteins across PPI networks[J]. Nucleic acids research, 2011, 39(suppl 1):D295-D300.