基于局部優化與二分圖匹配的PPI網絡比對算法

祝 家 燁

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

0 引 言

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

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

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

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

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

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

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

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

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

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

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

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

1 問題定義與算法設計

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

1.1 相關概念及問題定義

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

由定義1可知本文中PPI網絡是一個無權無向圖。下面給出全局網絡比對的定義。

定義2兩個PPI網絡G1(V1,E1)，G2(V2,E2)的全局網絡比對(不失一般性，|V1|≤|V2|)是一個從點集V1到點集V2的單射f:V1→V2。在全局網絡比對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為源網絡，G2為目標網絡。

本文簡稱全局網絡比對為比對。

定義3一個比對f的比對集合為set(f)={(v,f(v)):v∈V1,f(v)∈V2}。對于V1中的一個點v，如果f(v)∈V2，即v是已經被匹配的點，則稱點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可知，比對集合與比對是一一對應的，一個比對對應一個比對集合，而一個比對集合，也代表了一個比對。為了構造一個比對，只要構造出對應的比對集合即可。

定義4在比對f下，對于一條源網絡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中的邊在比對后被保留下來的數量。

定義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}。

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

EC指標：

(1)

ICS指標：

(2)

S3指標：

(3)

TWEC指標：

(4)

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

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

1.2 LOBM算法設計

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

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

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

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

算法1基于二分圖匹配的局部優化算法

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

2：輸出：調整后的比對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的一次調整過程。α是一個控制算法迭代輪數的參數。迭代輪數越多，算法運行時間越久。

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

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

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

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

定義6當前的比對為f。ADJf((u,v))表示對當前比對進行調整。有兩種情況，第一種(u,v)?set(f)，則調整操作將匹配點對(u,v)加入比對集合f，第二種(u,v)∈set(f)，則調整操作將匹配點對(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的鄰居點構成的集合。

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

2 實驗分析

實驗所用的數據均來自Isobase數據庫[16]。Isobase數據庫是被普遍使用的生物PPI網絡數據庫。本文挑選了四種生物的PPI網絡數據，每種生物的PPI網絡結構信息見表1。所有的網絡數據都經過預處理，每個PPI網絡去除了自環、重邊以及獨立的節點。

表1 Isobase數據庫關于四種生物的PPI網絡數據

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

2.1 實驗環境與方法

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

表2 實驗運行環境

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

2.2 參數α、β的影響

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

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

2.2.1 參數β的影響

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

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

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

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

2.2.2 參數α的影響

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

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

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

2.3 不同算法之間的比較

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

表3 四種比對算法的命令行參數

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

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

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

(5)

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

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

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

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

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

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

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

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

3 結 語

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

[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.