祝 家 燁

(復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院上海市智能信息處理重點(diǎn)實(shí)驗(yàn)室 上海 200433)

0 引 言

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

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

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

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

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

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

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

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

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

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

衡量一個(gè)比對(duì)算法的好壞，有一些常見的衡量指標(biāo)如EC指標(biāo)、ICS指標(biāo)、S3指標(biāo)、TWEC指標(biāo)等[16]。

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

1 問題定義與算法設(shè)計(jì)

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

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

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

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

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

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

本文簡(jiǎn)稱全局網(wǎng)絡(luò)比對(duì)為比對(duì)。

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

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

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

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

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

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

EC指標(biāo)：

(1)

ICS指標(biāo)：

(2)

S3指標(biāo)：

(3)

TWEC指標(biāo)：

(4)

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

問題1對(duì)于兩個(gè)PPI網(wǎng)絡(luò)G1(V1,E1),G2(V2,E2)，以及一個(gè)比對(duì)衡量標(biāo)準(zhǔn)Q，要求一個(gè)全局比對(duì)f，使得在比對(duì)f下，Q的指標(biāo)最大化。

1.2 LOBM算法設(shè)計(jì)

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

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

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

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

算法1基于二分圖匹配的局部?jī)?yōu)化算法

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

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

3：fp←f

4：T←0

5：WhileT<α

6:T←T+1

7：oldfp←fp

8:ds←從set(fp)中隨機(jī)挑選的β*|set(fp)|個(gè)匹配點(diǎn)對(duì)

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是當(dāng)前的迭代輪次。

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

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

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

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

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

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

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

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

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

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

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

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

2.1 實(shí)驗(yàn)環(huán)境與方法

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

表2 實(shí)驗(yàn)運(yùn)行環(huán)境

實(shí)驗(yàn)中用到的比對(duì)衡量標(biāo)準(zhǔn)，CE指標(biāo)為首要衡量指標(biāo)，因?yàn)樗荓OBM算法的目標(biāo)。其次，EC、ICS、S3和TWEC這四個(gè)指標(biāo)是被正式認(rèn)可的指標(biāo)，也需要進(jìn)行比較。

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

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

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

2.2.1 參數(shù)β的影響

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

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

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

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

2.2.2 參數(shù)α的影響

實(shí)驗(yàn)使用β=35來運(yùn)行LOBM算法，并且記錄每輪迭代后當(dāng)前比對(duì)的CE指標(biāo)與前一次CE指標(biāo)的差值。

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

圖2 LOBM每輪迭代時(shí)的比對(duì)指標(biāo)(ΔCE)

2.3 不同算法之間的比較

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

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

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

圖3 LOBM與四種比對(duì)算法的CE值標(biāo)比較

圖4為L(zhǎng)OBM與四種比對(duì)算法在CE指標(biāo)上的提高程度，即：

(5)

圖4 LOBM對(duì)四種比對(duì)算法的CE值標(biāo)提高程度

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

2.4 EC、ICS、S3、TWEC指標(biāo)的比較

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

圖5 LOBM在四項(xiàng)指標(biāo)上對(duì)已有比對(duì)算法的提高程度

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

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

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

3 結(jié) 語

本文著眼于PPI網(wǎng)絡(luò)比對(duì)問題，設(shè)計(jì)并實(shí)現(xiàn)了一種能夠提高既有比對(duì)算法結(jié)果的局部調(diào)優(yōu)算法LOBM。通過最大化CE指標(biāo)，LOBM能夠不斷調(diào)整PPI網(wǎng)絡(luò)比對(duì)，大幅提高各項(xiàng)指標(biāo)。LOBM可以與任何已有的比對(duì)算法相結(jié)合，是一種比較通用的比對(duì)優(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.