夏金芳，陳 璟，2

1(江南大學(xué) 人工智能與計(jì)算機(jī)學(xué)院，江蘇 無(wú)錫 214122) 2(江南大學(xué) 物聯(lián)網(wǎng)技術(shù)應(yīng)用教育部工程研究中心，江蘇 無(wú)錫 214122)

1 引 言

隨著高通量技術(shù)的發(fā)展，可用的生物數(shù)據(jù)顯著增加，人們將其建模成蛋白質(zhì)相互作用(protein-protein interaction，PPI)網(wǎng)絡(luò)、基因調(diào)控網(wǎng)絡(luò)、代謝網(wǎng)絡(luò)和疾病網(wǎng)絡(luò)，并對(duì)其展開(kāi)深入的研究與分析.網(wǎng)絡(luò)比對(duì)是一種常用的比較分析網(wǎng)絡(luò)的方法，通過(guò)對(duì)這些網(wǎng)絡(luò)的分析可以獲得更多新穎的見(jiàn)解，例如識(shí)別可能具有重要功能的進(jìn)化保守復(fù)合物；重構(gòu)物種的進(jìn)化動(dòng)力學(xué)；推斷系統(tǒng)發(fā)育樹(shù)；預(yù)測(cè)未知蛋白質(zhì)的功能；驗(yàn)證已知功能的蛋白質(zhì)；分析網(wǎng)絡(luò)之間的差異等.網(wǎng)絡(luò)比對(duì)與子圖同構(gòu)問(wèn)題有關(guān)，后者力求找到一種映射關(guān)系使得一個(gè)網(wǎng)絡(luò)是另一個(gè)網(wǎng)絡(luò)的精確子圖，這是一個(gè)NP-hard問(wèn)題[1].而網(wǎng)絡(luò)比對(duì)并不要求是精確子圖，它只需要找到一種最佳的映射關(guān)系，用以發(fā)現(xiàn)給定網(wǎng)絡(luò)之間具有相似拓?fù)浠蚬δ軈^(qū)域的節(jié)點(diǎn)[2].同時(shí)，由于蛋白質(zhì)是細(xì)胞生命中最活躍的參與者，因此當(dāng)前的網(wǎng)絡(luò)比對(duì)廣泛應(yīng)用于PPI網(wǎng)絡(luò)，用以挖掘更多的生物學(xué)知識(shí).

目前，研究者們提出了很多比對(duì)算法[3，4].根據(jù)映射關(guān)系可以分為局部比對(duì)和全局比對(duì)，也可根據(jù)比對(duì)網(wǎng)絡(luò)的數(shù)量分為兩個(gè)網(wǎng)絡(luò)的比對(duì)和多個(gè)網(wǎng)絡(luò)的比對(duì).局部比對(duì)的目標(biāo)是發(fā)現(xiàn)小的、保守的區(qū)域，但它往往犧牲了網(wǎng)絡(luò)的整體相似性，而全局網(wǎng)絡(luò)比對(duì)與之相反，它旨在找到使網(wǎng)絡(luò)整體相似性最大化的保守區(qū)域[5].近年來(lái)，多網(wǎng)絡(luò)比對(duì)受到更多的關(guān)注，雖然它與兩個(gè)網(wǎng)絡(luò)比對(duì)相比，其復(fù)雜度更高，但可以捕獲更多的網(wǎng)絡(luò)保守區(qū)域.IsoRankN[6]、SMETANA[7]、CSRW[8]、NetCoffee[9]、NetCoffee2[10]、BEAMS[11]、Fuse[12]等都是全局多網(wǎng)絡(luò)比對(duì)算法，其中，NetCoffee是一對(duì)一的多網(wǎng)絡(luò)比對(duì)，其它算法則是多對(duì)多的多網(wǎng)絡(luò)比對(duì).IsoRankN將迭代譜聚類融入到IsoRank，并擴(kuò)展到多個(gè)網(wǎng)絡(luò)比對(duì).SMETANA基于半馬爾可夫隨機(jī)游走模型實(shí)現(xiàn)網(wǎng)絡(luò)比對(duì)，CSRW在SMETANA的基礎(chǔ)上使用上下文相關(guān)的隨機(jī)游走模型完成比對(duì).NetCoffee使用類似于T-Coffee的方法，將多網(wǎng)絡(luò)構(gòu)造成一組加權(quán)二分圖，并使用模擬退火算法來(lái)最大化相似性得分.WebNetCoffee[13]為NetCoffee提供了一個(gè)友好的用戶界面.Netcoffee2改進(jìn)了NetCoffee的相似性函數(shù)，彌補(bǔ)了NetCoffee只能比對(duì)兩個(gè)網(wǎng)絡(luò)的局限性，并且在運(yùn)行速度方面也有所改進(jìn).BEAMS采用backbone提取和合并方法進(jìn)行比對(duì).Fuse通過(guò)非負(fù)矩陣三因式分解(Non-negative Matrix Tri-Factorization，NMTF)方法計(jì)算蛋白質(zhì)相似性得分，然后使用最大權(quán)重k分圖匹配算法進(jìn)行比對(duì).

上述算法中，SMETANA在計(jì)算有效性、比對(duì)準(zhǔn)確性方面表現(xiàn)優(yōu)異.它通過(guò)網(wǎng)絡(luò)內(nèi)和網(wǎng)絡(luò)間的概率一致性轉(zhuǎn)移，考慮了網(wǎng)絡(luò)的局部和全局相似性，增強(qiáng)了節(jié)點(diǎn)比對(duì)概率，然后根據(jù)轉(zhuǎn)移后的概率得分貪心地比對(duì)節(jié)點(diǎn).但是，由于蛋白質(zhì)序列相似性得分高低不能直接確定兩個(gè)蛋白質(zhì)功能是否相同，于是本文提出ConAlign算法，在SMETANA算法的基礎(chǔ)上進(jìn)行三點(diǎn)改進(jìn)，以增強(qiáng)節(jié)點(diǎn)對(duì)的相似性并增加算法使用的簡(jiǎn)易性.

1)使用低維向量表示節(jié)點(diǎn)的穩(wěn)態(tài)轉(zhuǎn)移概率，通過(guò)節(jié)點(diǎn)對(duì)之間的穩(wěn)態(tài)概率轉(zhuǎn)移差異對(duì)序列相似性進(jìn)行懲罰；

2)使用網(wǎng)絡(luò)度相似性作為網(wǎng)絡(luò)間的整體拓?fù)湎嗨菩裕?/p>

3)改進(jìn)網(wǎng)絡(luò)比對(duì)約束條件，刪除指定參數(shù)nmax.

實(shí)驗(yàn)表明，ConAlign算法更高效且保證了拓?fù)渑c生物功能的一致性.

2 方 法

2.1 問(wèn)題定義

PPI網(wǎng)絡(luò)可以通過(guò)網(wǎng)絡(luò)圖的形式表示，本文將PPI網(wǎng)絡(luò)建模為無(wú)權(quán)無(wú)向圖，其中節(jié)點(diǎn)代表蛋白質(zhì)，邊代表蛋白質(zhì)之間的相互作用.假設(shè)給定兩個(gè)網(wǎng)絡(luò)G1(V1,E1)和G2(V2,E2)，其中V1和V2分別是兩個(gè)網(wǎng)絡(luò)的節(jié)點(diǎn)集合，E1和E2分別是兩個(gè)網(wǎng)絡(luò)的邊集合.兩個(gè)網(wǎng)絡(luò)比對(duì)是尋找一種映射關(guān)系f，如式(1)所示，將G1的節(jié)點(diǎn)比對(duì)到G2的節(jié)點(diǎn)，使得比對(duì)的得分函數(shù)最大，通常得分函數(shù)可以是兩個(gè)網(wǎng)絡(luò)中所有比對(duì)上的節(jié)點(diǎn)對(duì)的相似性之和.

f(u)={v|u∈V1,v∈V2}

(1)

多網(wǎng)絡(luò)比對(duì)將兩個(gè)網(wǎng)絡(luò)擴(kuò)展到多個(gè)網(wǎng)絡(luò)進(jìn)行比對(duì).假設(shè)給定N個(gè)網(wǎng)絡(luò)G=(G1,G2,…,GN)待比對(duì)，Gi=(Vi,Ei),1≤i≤N表示G中第i個(gè)網(wǎng)絡(luò)，其中Vi和Ei分別是Gi網(wǎng)絡(luò)的節(jié)點(diǎn)和邊的集合.本文使用SMETANA中的最大預(yù)期準(zhǔn)確性(Maximum Expected Accuracy，MEA)作為比對(duì)的得分函數(shù).預(yù)期準(zhǔn)確性(Expected Accuracy，EA)是通過(guò)比對(duì)簇中節(jié)點(diǎn)比對(duì)的后驗(yàn)概率來(lái)估算節(jié)點(diǎn)正確比對(duì)的概率，如公式(2)所示.

(2)

式(2)中EA(A)表示比對(duì)A的預(yù)期準(zhǔn)確性，A表示比對(duì)集合，P(ui～vj|G)表示網(wǎng)絡(luò)G中ui比對(duì)到vj的后驗(yàn)概率.

2.2 網(wǎng)絡(luò)節(jié)點(diǎn)拓?fù)湎嗨菩?/h3>

Connor等人[14]曾指出，如BLAST產(chǎn)生的bit-score等序列相似性值并不能準(zhǔn)確度量蛋白質(zhì)的功能相似性程度，因此本文通過(guò)網(wǎng)絡(luò)節(jié)點(diǎn)的拓?fù)湎嗨菩詮浹a(bǔ)序列相似性是有必要的.

SMETANA中使用半馬爾可夫隨機(jī)游走計(jì)算節(jié)點(diǎn)對(duì)的全局對(duì)應(yīng)得分，無(wú)法體現(xiàn)拓?fù)渑c生物一致性高的節(jié)點(diǎn)對(duì)，ConAlign使用網(wǎng)絡(luò)節(jié)點(diǎn)拓?fù)洳町愋宰鳛閼土P項(xiàng)，更好地突出拓?fù)渑c生物一致的節(jié)點(diǎn)對(duì).ConAlign首先用低維向量π(Gi)表示Gi網(wǎng)絡(luò)中節(jié)點(diǎn)的穩(wěn)態(tài)轉(zhuǎn)移概率，然后使用(ui,vj)節(jié)點(diǎn)對(duì)的穩(wěn)態(tài)轉(zhuǎn)移概率的相似性作為其拓?fù)湎嗨菩訲(ui,vj).節(jié)點(diǎn)相似性TS(ui,vj)在拓?fù)湎嗨菩缘幕A(chǔ)上融合序列相似性.

(3)

(4)

式(3)中π(ui)表示節(jié)點(diǎn)ui簡(jiǎn)單隨機(jī)游走的穩(wěn)態(tài)分布，式(4)中S(ui,vj)是節(jié)點(diǎn)ui和vj的序列相似性，當(dāng)π(ui)=π(vj)時(shí)，直接使用序列相似性作為網(wǎng)絡(luò)節(jié)點(diǎn)的相似性.

(5)

式中S-T(ui′,vj)表示帶歸一化的節(jié)點(diǎn)對(duì)得分.

2.3 網(wǎng)絡(luò)整體拓?fù)湎嗨菩?/h3>

SMETANA在網(wǎng)絡(luò)間概率一致性轉(zhuǎn)移時(shí)，使用兩個(gè)網(wǎng)絡(luò)比對(duì)的后驗(yàn)概率作為網(wǎng)絡(luò)的整體相似性，該整體相似性受前期相似性計(jì)算的影響較大，且兩個(gè)網(wǎng)絡(luò)比對(duì)也需要一定時(shí)間.為了防止假陽(yáng)性，并加快算法效率，ConAlign通過(guò)網(wǎng)絡(luò)整體拓?fù)湎嗨菩赃M(jìn)行網(wǎng)絡(luò)間概率一致性轉(zhuǎn)移.

D(Gi)表示Gi網(wǎng)絡(luò)中所有節(jié)點(diǎn)的度的集合，D(Gi)={deg(u)|u∈Vi}，(deg(u)表示u節(jié)點(diǎn)的度，N(u)表示u節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的集合，deg(u)=|N(u)|.)由于網(wǎng)絡(luò)規(guī)模不同，為表現(xiàn)出網(wǎng)絡(luò)節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要性，對(duì)網(wǎng)絡(luò)中所有節(jié)點(diǎn)的度通過(guò)式(6)歸一化.

(6)

對(duì)于Gi=(Vi,Ei)和Gj=(Vj,Ej)兩個(gè)網(wǎng)絡(luò)，假設(shè)Vi={u1,u2,…,um}，Vj={v1,v2,…,vn}，若m≠n，則通過(guò)添加度為0的節(jié)點(diǎn)，使得m=n.Gi與Gj之間的距離Dis(Gi,Gj)和相似性Sim(Gi,Gj)的計(jì)算分別如式(7)和式(8)所示.

Dis(Gi,Gj)=‖ND(Gi)-ND(Gj)‖F(xiàn)

(7)

(8)

2.4 網(wǎng)絡(luò)構(gòu)建約束條件

SMETANA比對(duì)構(gòu)建過(guò)程中的約束條件之一：任何比對(duì)簇中來(lái)自同一個(gè)網(wǎng)絡(luò)的節(jié)點(diǎn)不能超過(guò)nmax，由于nmax參數(shù)的選擇沒(méi)有統(tǒng)一的標(biāo)準(zhǔn)，且選擇范圍廣，故ConAlign中對(duì)此約束進(jìn)行改進(jìn).改進(jìn)后的比對(duì)構(gòu)建首先對(duì)通過(guò)概率一致性轉(zhuǎn)移的估計(jì)概率P降序排列，然后按P值從大到小的順序依次分3種情況進(jìn)行比對(duì).

1)如果當(dāng)前節(jié)點(diǎn)對(duì)(ui,vj)都未被比對(duì)上，則產(chǎn)生一個(gè)新簇，并將這個(gè)新簇放入比對(duì)集合中；

2)如果當(dāng)前節(jié)點(diǎn)對(duì)(ui,vj)有且僅有一個(gè)節(jié)點(diǎn)被比對(duì)上，假設(shè)ui已經(jīng)被比對(duì)在簇Cl中，另一個(gè)節(jié)點(diǎn)vj沒(méi)有被比對(duì)上.判斷vj能否加入到簇Cl中的流程如圖1所示：輸入P(ui～vj)，首先判斷P(ui～vj)是否滿足公式(9)：大于等于簇Cl中來(lái)自i網(wǎng)絡(luò)和j網(wǎng)絡(luò)的節(jié)點(diǎn)對(duì)之間的最大值，若滿足，則將vj加入簇Cl中，否則，使用公式(10)計(jì)算未比對(duì)節(jié)點(diǎn)vj屬于該簇Cl的概率，式中k是簇Cl中和vj來(lái)自同一個(gè)網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)，β是一個(gè)懲罰因子，若滿足條件，則將vj加入簇Cl中，否則丟棄vj.

圖1 比對(duì)約束的流程圖Fig.1 Flow chart of alignment constraints

(9)

(10)

3)如果當(dāng)前節(jié)點(diǎn)對(duì)(ui,vj)都已經(jīng)被比對(duì)上，但未被比對(duì)在同一個(gè)簇中，則嘗試將這兩個(gè)簇合并，若合并后的簇中來(lái)自不同網(wǎng)絡(luò)的節(jié)點(diǎn)至多一個(gè)，則將這兩個(gè)簇合并，否則，不合并這兩個(gè)簇.

2.5 算法描述

定義 1.若一個(gè)節(jié)點(diǎn)與其它網(wǎng)絡(luò)中的任一節(jié)點(diǎn)都沒(méi)有序列相似性，則認(rèn)為這個(gè)節(jié)點(diǎn)是非同源節(jié)點(diǎn).

算法1.ConAlign算法

輸入：PPI網(wǎng)絡(luò)G=(G1,G2,…,GN)，網(wǎng)絡(luò)間所有蛋白質(zhì)對(duì)的序列相似性；

輸出：比對(duì)的簇結(jié)果；

Begin

1.網(wǎng)絡(luò)初始化，去除非同源節(jié)點(diǎn)；

2.使用公式(4)網(wǎng)絡(luò)節(jié)點(diǎn)的拓?fù)湎嗨菩匀诤闲蛄邢嗨菩杂?jì)算節(jié)

點(diǎn)相似性；

3.網(wǎng)絡(luò)內(nèi)部概率一致性轉(zhuǎn)移;

4.網(wǎng)絡(luò)間概率一致性轉(zhuǎn)移，其中網(wǎng)絡(luò)間的相似性使用公式(8)；

5.如2.4進(jìn)行網(wǎng)絡(luò)構(gòu)建；

End

ConAlign算法的復(fù)雜度約為O(N3z|Vmax|)，其中，N是要比對(duì)的網(wǎng)絡(luò)個(gè)數(shù)，z表示兩個(gè)網(wǎng)絡(luò)相似性的非零元素最多的個(gè)數(shù)，Vmax表示最大網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù).

3 實(shí)驗(yàn)及分析

3.1 實(shí)驗(yàn)數(shù)據(jù)集

本文分別在合成網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)上測(cè)試了ConAlign算法.合成網(wǎng)絡(luò)是NAPAbench[15]中的PPI網(wǎng)絡(luò)，這三個(gè)合成網(wǎng)絡(luò)分別對(duì)晶體生長(zhǎng)(crystal growth，CG)、復(fù)制-突變-互補(bǔ)(duplication-mutation-complementation，DMC)、帶有隨機(jī)突變的復(fù)制(duplication with random mutation，DMR)這三種類型的8-way網(wǎng)絡(luò)進(jìn)行了建模.CG中8個(gè)網(wǎng)絡(luò)均由1000個(gè)節(jié)點(diǎn)和3985條邊組成；DMC中8個(gè)網(wǎng)絡(luò)的節(jié)點(diǎn)均是1000，邊的數(shù)量分別是1919、1853、1923、1840、1867、1848、1818、1867；DMR中8個(gè)網(wǎng)絡(luò)的節(jié)點(diǎn)均是1000，邊的數(shù)量分別是2031、2092、1967、1977、1959、1998、2030、2056.5個(gè)真實(shí)網(wǎng)絡(luò)分別是蠕蟲(chóng)(Caenorhabditis Elegans，CE)、蠅類(Drosophila Melanogaster，DM)、人類(Homo Sapiens，HS)、老鼠(Mus Musculus，MM)和酵母(Saccharomyces Cerevisiae，SC).真實(shí)網(wǎng)絡(luò)的所有數(shù)據(jù)從IsoBase[16]數(shù)據(jù)庫(kù)獲得，網(wǎng)絡(luò)的節(jié)點(diǎn)和邊信息如表1所示.生物相似性使用BLAST++工具計(jì)算得出蛋白質(zhì)之間的序列相似性得分.

表1 真實(shí)網(wǎng)絡(luò)信息Table 1 Network information of five real networks

3.2 實(shí)驗(yàn)結(jié)果與評(píng)估

目前已存在多種評(píng)估多網(wǎng)絡(luò)比對(duì)的質(zhì)量的方法，如簇和蛋白質(zhì)的覆蓋量、拓?fù)浜蜕飳W(xué)度量指標(biāo)等.

簇覆蓋量(Cluster coverage)表示簇的數(shù)量，即通過(guò)比對(duì)產(chǎn)生的簇的數(shù)量.蛋白質(zhì)覆蓋量(Protein coverage)表示比對(duì)上的蛋白質(zhì)的數(shù)量，即所有簇中蛋白質(zhì)的總數(shù).簇的k覆蓋量是指包含來(lái)自k個(gè)物種的蛋白質(zhì)的簇的數(shù)量.

為了進(jìn)一步度量比對(duì)結(jié)果，可以從拓?fù)浣嵌榷攘勘葘?duì)結(jié)果，例如簇相互作用質(zhì)量(Cluster Interaction Quality，CIQ)[11].也可以從生物學(xué)角度度量比對(duì)結(jié)果簇中蛋白質(zhì)的功能相似性，例如平均歸一化熵(Mean Normalized Entropy，MNE)[17]，敏感性(Sensitivity，Sen)[11].

CIQ是對(duì)所有簇中節(jié)點(diǎn)對(duì)之間的一種保守相互作用度量[11].

(11)

式(11)中，EClm,Cln是簇Clm和簇Cln之間邊的數(shù)量，cs(m,n)的定義如公式(12)：

(12)

式(12)中，sm,n′是簇Clm和簇Cln中邊的網(wǎng)絡(luò)的數(shù)量，sm,n是簇Clm和簇Cln中存在共享節(jié)點(diǎn)的網(wǎng)絡(luò)的數(shù)量.

MNE是一種一致性度量.歸一化熵(Normalized Entropy, NE)：

(13)

式(13)中其中d是簇Cl中不同基因本體(Gene Ontology,GO)[18]注釋的數(shù)量，pi是簇Cl中有GOi注釋的蛋白質(zhì)的比例.MNE是所有注釋簇的平均歸一化熵，其值越小，表明簇結(jié)果越一致.

Sen是在所有GO類別里，最接近簇中與比對(duì)節(jié)點(diǎn)中被GO類別注釋的蛋白質(zhì)數(shù)量的比例的平均值.對(duì)于給定的GO類別，其最接近的簇是指包含最多被該GO類別注釋的蛋白質(zhì)數(shù)量的簇[11].

實(shí)驗(yàn)將本文算法ConAlign與IsoRankN、BEAMS和SMETANAE進(jìn)行對(duì)比.ConAlign算法中α=0.9,β=0.8，與SMETANA原文保持一致，其它三種算法采用原文算法默認(rèn)參數(shù)，IsoRankN：α=0.6；BEAMS在合成網(wǎng)絡(luò)上α=0.5,β=0.2；在真實(shí)網(wǎng)絡(luò)上α=0.5,β=0.4；SMETANA：α=0.9,β=0.8,nmax=10.

3.2.1 合成網(wǎng)絡(luò)實(shí)驗(yàn)

圖2是本文算法ConAlign及另三種主流算法IsoRankN、BEAMS、SMETANA在NAPAbench合成網(wǎng)絡(luò)上的簇覆蓋量.雖然BEAMS在三個(gè)合成網(wǎng)絡(luò)上的簇覆蓋量最多，但許多簇是由2或3個(gè)物種的蛋白質(zhì)組成.當(dāng)產(chǎn)生的簇包含來(lái)自所有物種的節(jié)點(diǎn)時(shí)，才有可能提供所有網(wǎng)絡(luò)蛋白質(zhì)之間的同源信息.ConAlign產(chǎn)生的k=8的簇覆蓋量在DMC網(wǎng)絡(luò)上與BEAMS相近，在CG和DMR網(wǎng)絡(luò)上比BEAMS多.同時(shí)，在這三個(gè)合成網(wǎng)絡(luò)中，ConAlign產(chǎn)生的k=8的簇占總的簇覆蓋量的比例均高于BEAMS.這表明ConAlign產(chǎn)生的簇更具有研究?jī)r(jià)值.圖3是8-way合成網(wǎng)絡(luò)的蛋白質(zhì)覆蓋量，ConAlign產(chǎn)生的蛋白質(zhì)覆蓋量在合成網(wǎng)絡(luò)上表現(xiàn)良好，大多數(shù)蛋白質(zhì)均被比對(duì)上，即識(shí)別出了最多的同源物.

圖2 不同算法在合成網(wǎng)絡(luò)上的簇覆蓋量Fig.2 Cluster coverage of different algorithms on synthetic networks

圖3 不同算法在合成網(wǎng)絡(luò)上的蛋白質(zhì)覆蓋量Fig.3 Protein coverage of different algorithms on synthetic networks

CG、DMC、DMR這三個(gè)合成網(wǎng)絡(luò)比對(duì)結(jié)果的拓?fù)浜蜕镄阅艿姆治龇謩e如表2～表4所示.總體上，ConAlign在拓?fù)渲笜?biāo)CIQ和生物指標(biāo)MNE、Sen上的表現(xiàn)優(yōu)異.雖然IsoRankN在CG網(wǎng)絡(luò)上Sen值最高，但其CIQ值和MNE值均是最差的.對(duì)其余情況而言，ConAlign均表現(xiàn)最佳，尤其是在DMR網(wǎng)絡(luò)上，ConAlign與次優(yōu)的SMETANA相比，其CIQ提高了4%、MNE優(yōu)化了2.6%、Sen提高了10.9%.這表明ConAlign通過(guò)拓?fù)湎嗨菩詫?duì)序列相似性的增強(qiáng)是有效的.

表2 不同算法在CG網(wǎng)絡(luò)中的表現(xiàn)Table 2 Performance of different algorithms on CG networks

表3 不同算法在DMC網(wǎng)絡(luò)中的表現(xiàn)Table 3 Performance of different algorithms on DMC networks

本算法在所有合成網(wǎng)絡(luò)上的CIQ值都最高，表明比對(duì)結(jié)果中保守相互作用多，且在大部分情況下，比對(duì)結(jié)果的MNE值較低且Sen值較高，表明ConAlign產(chǎn)生的比對(duì)結(jié)果更具有功能相關(guān)性.

表4 不同算法在DMR網(wǎng)絡(luò)中的表現(xiàn)Table 4 Performance of different algorithms on DMR networks

3.2.2 真實(shí)網(wǎng)絡(luò)實(shí)驗(yàn)

為了進(jìn)一步評(píng)估本算法，本文將四種算法在真實(shí)網(wǎng)絡(luò)上也進(jìn)行了實(shí)驗(yàn).如圖4和圖5所示，不同算法在真實(shí)網(wǎng)絡(luò)上的簇覆蓋量和蛋白質(zhì)覆蓋量與在合成網(wǎng)絡(luò)上呈現(xiàn)的趨勢(shì)近似，簇覆蓋量之間的差異主要體現(xiàn)在k=2和k=3，但它們不能像k=5的簇一樣提供所有物種間蛋白質(zhì)之間的關(guān)系.ConAlign產(chǎn)生最多的蛋白質(zhì)覆蓋量，也就是說(shuō)比對(duì)上的蛋白質(zhì)是最多的.

圖4 不同算法在真實(shí)網(wǎng)絡(luò)中產(chǎn)生的簇覆蓋量Fig.4 Cluster coverage of different algorithms on real networks

圖5 不同算法在真實(shí)網(wǎng)絡(luò)中產(chǎn)生的蛋白質(zhì)覆蓋量Fig.5 Protein coverage of different algorithms on real networks

表5 不同算法在真實(shí)網(wǎng)絡(luò)上的表現(xiàn)Table 5 Performance of different algorithms on real networks

真實(shí)網(wǎng)絡(luò)比對(duì)結(jié)果的拓?fù)浜蜕镄阅芊治鋈绫?所示，雖然BEAMS產(chǎn)生的比對(duì)結(jié)果有最小的MNE值，但是ConAlign產(chǎn)生的結(jié)果有著高的CIQ值和Sen值，且其MNE值僅次于BEAMS.

圖6是真實(shí)網(wǎng)絡(luò)中不同算法分別對(duì)CIQ、Sen、MNE的效果從好到壞降序排列，將同種算法用直線相連.交叉的直線表示該算法在一個(gè)度量指標(biāo)上表現(xiàn)良好，但在另一個(gè)度量指標(biāo)上表現(xiàn)不佳.由圖6可知，BEAMS在生物方面的MNE表現(xiàn)優(yōu)異，但其在拓?fù)浞矫姹憩F(xiàn)沒(méi)有SMETANA和ConAlign好，而ConAlign是未交叉的直線中排名最好的，其產(chǎn)生的結(jié)果在拓?fù)浜蜕锓矫孢_(dá)到了平衡，具有拓?fù)渑c生物功能一致性.

圖6 不同算法在真實(shí)網(wǎng)絡(luò)中度量指標(biāo)的關(guān)系Fig.6 Relationship of indicators between different algorithms on real networks

在真實(shí)網(wǎng)絡(luò)中，ConAlign在生物指標(biāo)MNE上的表現(xiàn)未達(dá)到最佳，可能的原因有兩點(diǎn)：一是，ConAlign為了防止假陽(yáng)性，采用網(wǎng)絡(luò)整體拓?fù)湎嗨菩宰鳛榫W(wǎng)絡(luò)的相似性，并沒(méi)有融入序列相似性.雖然，在計(jì)算網(wǎng)絡(luò)間整體相似性時(shí)犧牲了序列相似性，但是，運(yùn)行速度得到了提升，如表6所示，ConAlign在合成網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)上運(yùn)行的時(shí)間比其它三個(gè)算法都短，而B(niǎo)EAMS的運(yùn)行時(shí)間是最長(zhǎng)的.二是，目前的蛋白質(zhì)的功能注釋可能不完善，因此，很難完全可靠評(píng)估預(yù)測(cè)比對(duì)的生物性能.

表6 不同算法在不同網(wǎng)絡(luò)上的運(yùn)行時(shí)間Table 6 Runtimes of different algorithms on different networks

ConAlign算法在合成網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果表明，其比對(duì)結(jié)果在拓?fù)渲笜?biāo)和生物指標(biāo)這兩方面達(dá)到了整體最優(yōu)，體現(xiàn)了拓?fù)渑c生物功能一致性.

4 結(jié) 論

本文提出了一種全局多對(duì)多的多網(wǎng)絡(luò)比對(duì)算法ConAlign，該算法在SMETANA算法的基礎(chǔ)上進(jìn)行了改進(jìn)，首先，使用節(jié)點(diǎn)對(duì)拓?fù)湎嗨菩匝a(bǔ)充序列相似性，并結(jié)合網(wǎng)絡(luò)整體拓?fù)湎嗨菩赃M(jìn)行網(wǎng)絡(luò)間概率一致性轉(zhuǎn)移.其次，通過(guò)修改比對(duì)約束條件，刪除了難以確定的參數(shù).本算法分別在合成網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)上進(jìn)行實(shí)驗(yàn)，并與IsoRankN、BEAMS、SMETANA算法進(jìn)行比較.實(shí)驗(yàn)表明，ConAlign是一種運(yùn)行速度快，參數(shù)少，蛋白質(zhì)覆蓋量高且具有拓?fù)渑c生物功能一致性的比對(duì)算法.

為了保證生物網(wǎng)絡(luò)比對(duì)具有高的生物相似性，本算法是在序列相似性的基礎(chǔ)上完成.由于序列相似性數(shù)據(jù)的不完整性，在接下來(lái)的工作中，將嘗試僅用拓?fù)湎嗨菩詠?lái)完成網(wǎng)絡(luò)比對(duì).