一種基于遺傳算法的PPI網(wǎng)絡(luò)全局比對(duì)算法

陳 悅，陳 璟，2

1(江南大學(xué) 人工智能與計(jì)算機(jī)學(xué)院，江蘇 無(wú)錫 214122) 2(江南大學(xué) 江蘇省模式識(shí)別與計(jì)算智能工程實(shí)驗(yàn)室，江蘇 無(wú)錫 214122)

1 引 言

隨著高通量篩選技術(shù)和計(jì)算機(jī)技術(shù)的發(fā)展，人們可獲得的PPI(protein-protein interaction，PPI)數(shù)據(jù)[1]與日俱增，對(duì)這些數(shù)據(jù)進(jìn)行有效的分析有助于對(duì)同源蛋白質(zhì)、蛋白質(zhì)功能模塊和蛋白質(zhì)功能預(yù)測(cè)等的研究.網(wǎng)絡(luò)比對(duì)是研究PPI網(wǎng)絡(luò)數(shù)據(jù)的一個(gè)重要方法，它通過(guò)匹配不同PPI網(wǎng)絡(luò)的節(jié)點(diǎn)，在源網(wǎng)絡(luò)和目標(biāo)網(wǎng)絡(luò)的節(jié)點(diǎn)之間形成一種映射關(guān)系.

目前已經(jīng)提出的成對(duì)網(wǎng)絡(luò)全局比對(duì)的經(jīng)典算法，大體可分為兩類：2步算法和基于目標(biāo)函數(shù)的搜索算法.2步算法的第1步是計(jì)算兩個(gè)輸入網(wǎng)絡(luò)的節(jié)點(diǎn)相似性，第2步是根據(jù)第1步計(jì)算的相似性得分將網(wǎng)絡(luò)比對(duì)問(wèn)題轉(zhuǎn)化為最大權(quán)重的二部圖匹配問(wèn)題.基于目標(biāo)函數(shù)的搜索算法首先提出一個(gè)目標(biāo)函數(shù)，然后利用啟發(fā)式搜索方法去優(yōu)化目標(biāo)函數(shù).

IsoRank[2]算法是全局比對(duì)算法中的先驅(qū)，首先使用PageRank算法基于節(jié)點(diǎn)拓?fù)湎嗨菩院托蛄邢嗨菩杂?jì)算兩個(gè)網(wǎng)絡(luò)任意節(jié)點(diǎn)對(duì)之間的相似度，然后使用貪心算法匹配相似性高的節(jié)點(diǎn)對(duì)得到比對(duì)結(jié)果.GRAAL[3]算法首次提出用度標(biāo)簽相似性作為節(jié)點(diǎn)的拓?fù)湎嗨菩灾笜?biāo).PROPER[4]算法假設(shè)蛋白質(zhì)序列的高相似度代表著功能的高相似度，因此，PROPER首先匹配序列相似度高的節(jié)點(diǎn)對(duì)，然后在該結(jié)果的基礎(chǔ)上逐步完善比對(duì)結(jié)果.SPINAL[5]算法基于局部鄰域匹配構(gòu)建初始相似性矩陣并由此得到粗粒度的比對(duì)結(jié)果，繼而使用種子擴(kuò)展和局部搜索的方法得到細(xì)粒度結(jié)果.PSONA算法[6]提出一種基于permutation的粒子群優(yōu)化算法來(lái)搜索生物網(wǎng)絡(luò)的最優(yōu)比對(duì).MeAlign算法[7]將遺傳算法和局部搜索算法相結(jié)合來(lái)尋找最優(yōu)比對(duì)結(jié)果.MAGNA[8]算法隨機(jī)產(chǎn)生初始種群并利用遺傳算法迭代得到最優(yōu)比對(duì)結(jié)果，MAGNA++[9]是MAGNA的一個(gè)擴(kuò)展，選取拓?fù)渲笜?biāo)作為目標(biāo)函數(shù)，相較MAGNA取得了更好的拓?fù)涮匦?，并提供了圖形界面.MAGNA++的比對(duì)結(jié)果隨著種群大小和迭代次數(shù)的增加而變好，但其目標(biāo)函數(shù)收斂慢，且MAGNA++使用拓?fù)渲笜?biāo)作為目標(biāo)函數(shù)，導(dǎo)致其比對(duì)結(jié)果生物質(zhì)量低.

為在比對(duì)結(jié)果的拓?fù)涮匦院蜕锾匦陨先〉镁獾母咧笜?biāo)，本文提出一種新的網(wǎng)絡(luò)比對(duì)算法NABG，主要貢獻(xiàn)如下：

1)基于節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要性得分計(jì)算節(jié)點(diǎn)對(duì)的拓?fù)湎嗨菩裕沟镁W(wǎng)絡(luò)中較為重要的節(jié)點(diǎn)更可能被比對(duì)上；

2)提出一種結(jié)合節(jié)點(diǎn)對(duì)相似性得分和邊的保守性的目標(biāo)函數(shù)，在迭代比對(duì)結(jié)果的過(guò)程中同時(shí)優(yōu)化節(jié)點(diǎn)和邊；

3)改進(jìn)遺傳算法的初始化、選擇和交叉的過(guò)程，減少后代種群對(duì)初始種群的依賴，加快種群的收斂速度.

2 算法介紹

2.1 問(wèn)題定義

在分析PPI網(wǎng)絡(luò)數(shù)據(jù)時(shí)，通常會(huì)將其抽象成圖模型[10]：將蛋白質(zhì)抽象為網(wǎng)絡(luò)節(jié)點(diǎn)，蛋白質(zhì)間的相互作用關(guān)系抽象為邊.兩個(gè)PPI網(wǎng)絡(luò)分別用無(wú)向圖G1= (V1，E1) 和G2= (V2，E2)表示，其中V1、V2表示網(wǎng)絡(luò)中的節(jié)點(diǎn)集合且|V1|≤|V2|，E1、E2表示網(wǎng)絡(luò)中的邊集合.成對(duì)PPI網(wǎng)絡(luò)一對(duì)一映射的全局比對(duì)即在兩個(gè)網(wǎng)絡(luò)之間找到一種映射關(guān)系f，使得G1網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)u唯一地比對(duì)到G2網(wǎng)絡(luò)中的某一節(jié)點(diǎn)v，即v=f(u).

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

網(wǎng)絡(luò)中通常會(huì)包含一些拓?fù)浣Y(jié)構(gòu)重要性高的節(jié)點(diǎn)，比如瓶頸節(jié)點(diǎn)和樞紐節(jié)點(diǎn).節(jié)點(diǎn)的結(jié)構(gòu)重要性一般用去掉該點(diǎn)后引起網(wǎng)絡(luò)結(jié)構(gòu)上的變化程度來(lái)衡量.在生物分子網(wǎng)絡(luò)中，一個(gè)蛋白質(zhì)節(jié)點(diǎn)在功能上的重要性也可以通過(guò)去掉該節(jié)點(diǎn)后引起的網(wǎng)絡(luò)功能或者有機(jī)體適應(yīng)度上的變化程度來(lái)衡量.在生物的生存或者繁殖過(guò)程中不可或缺的蛋白質(zhì)/基因被稱為必須蛋白質(zhì)/基因，而拓?fù)渲匾愿叩墓?jié)點(diǎn)更可能成為必須蛋白質(zhì)[11].在PPI網(wǎng)絡(luò)中，一個(gè)節(jié)點(diǎn)的功能重要性被認(rèn)為與其在網(wǎng)絡(luò)中的拓?fù)浣Y(jié)構(gòu)重要性有關(guān)[11].

必須蛋白質(zhì)節(jié)點(diǎn)在拓?fù)浣Y(jié)構(gòu)和功能上重要性高，這些節(jié)點(diǎn)變異的速度較慢，通常會(huì)更具有保守性.因此，NABG采用最小度啟發(fā)式算法[12]計(jì)算網(wǎng)絡(luò)中節(jié)點(diǎn)和邊的重要性得分NIS(u)，EIS(u，ui)，并基于此計(jì)算節(jié)點(diǎn)對(duì)的拓?fù)湎嗨菩缘梅諸(u，v).

為充分挖掘網(wǎng)絡(luò)節(jié)點(diǎn)的拓?fù)湫畔?，本文在?jì)算節(jié)點(diǎn)對(duì)拓?fù)湎嗨菩缘梅謺r(shí)同時(shí)考慮節(jié)點(diǎn)與其相鄰邊的重要性得分：

(1)

公式(1)中，節(jié)點(diǎn)u，v分別是網(wǎng)絡(luò)G1、G2中的節(jié)點(diǎn)，N(u)表示節(jié)點(diǎn)u的鄰居節(jié)點(diǎn)集合，Max(V)表示網(wǎng)絡(luò)中NIS(u)+∑ui∈N(u)EIS(u，ui)的最大值.

節(jié)點(diǎn)和邊的重要性得分NIS(u)，EIS(u，ui)計(jì)算方式如下：

NIS(u)的初始值設(shè)置為0，若在網(wǎng)絡(luò)中存在邊(u，ui)，則EIS(u，ui)的初始值設(shè)置為1，否則設(shè)置為0.從度為1 的節(jié)點(diǎn)開始，到度為10的節(jié)點(diǎn)結(jié)束，刪除當(dāng)前度最小的節(jié)點(diǎn)u，并更新其相鄰節(jié)點(diǎn)和邊的權(quán)重，如公式(2)、公式(3)所示:

當(dāng)|N(u)|=1時(shí)：

?ui∈N(u)，NIS(ui)=NIS(ui)+EIS(u，ui)

(2)

當(dāng)|N(u)|>1時(shí)：

(3)

2.3 網(wǎng)絡(luò)間節(jié)點(diǎn)對(duì)相似性

蛋白質(zhì)的序列信息是獲取生物信息的一個(gè)重要來(lái)源，而網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和蛋白質(zhì)序列可能成為獲取生物信息的互補(bǔ)信息[13]，因此NABG在節(jié)點(diǎn)對(duì)的相似性得分S(u，v)中同時(shí)引入節(jié)點(diǎn)對(duì)的拓?fù)湎嗨菩缘梅諸(u，v)和生物相似性得分B(u，v)：

S(u，v)=αB(u，v)+(1-α)T(u，v)

(4)

其中α(0<α<1)控制節(jié)點(diǎn)對(duì)拓?fù)湎嗨菩缘梅趾托蛄邢嗨菩缘梅值臋?quán)重，B(u，v)表示節(jié)點(diǎn)對(duì)(u，v)的歸一化bit-score值，即從輸入的序列相似性文件中讀取相應(yīng)數(shù)值并進(jìn)行歸一化處理.

2.4 目標(biāo)函數(shù)

NABG提出一種新的目標(biāo)函數(shù)：由節(jié)點(diǎn)對(duì)的相似性得分和邊正確性[13](Edge Correctness，EC)得分構(gòu)成，同時(shí)優(yōu)化節(jié)點(diǎn)對(duì)相似性和邊的保守性，達(dá)到優(yōu)化比對(duì)結(jié)果的拓?fù)涮匦院蜕锾匦缘哪康?

源網(wǎng)絡(luò)的邊與目標(biāo)網(wǎng)絡(luò)的邊比對(duì)上，稱為保守邊.EC是保守邊與源網(wǎng)絡(luò)邊數(shù)的比例.

(5)

(6)

其中，|E1|表示G1網(wǎng)絡(luò)中邊的個(gè)數(shù)，|f(E1)|表示保守邊的個(gè)數(shù).A表示一個(gè)比對(duì)結(jié)果，F(xiàn)(A)表示比對(duì)結(jié)果A的目標(biāo)函數(shù)得分，S(u，v)表示節(jié)點(diǎn)對(duì)(u，v)的序列相似性得分.

2.5 遺傳算法應(yīng)用

本文受MAGNA++算法啟發(fā)，將比對(duì)結(jié)果類比為種群個(gè)體，將比對(duì)結(jié)果的優(yōu)化過(guò)程類比為種群進(jìn)化過(guò)程.設(shè)置種群大小為p，則種群集合為{A0，A1，...，Ap-1}.

2.5.1 種群初始化

1)初始化A0： 將兩個(gè)網(wǎng)絡(luò)中的任意節(jié)點(diǎn)對(duì)按照相似性得分S從大到小排列，優(yōu)先比對(duì)相似性得分高的節(jié)點(diǎn)對(duì)，直到G1網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)都被唯一地比對(duì)上.

2)初始化{A1，A2，...，Ap-1}： 隨機(jī)產(chǎn)生p-1個(gè)比對(duì)結(jié)果.

2.5.2 種群適應(yīng)度評(píng)估

NABG將網(wǎng)絡(luò)比對(duì)的目標(biāo)函數(shù)類比為種群個(gè)體的適應(yīng)度函數(shù)，并依據(jù)適應(yīng)度值為種群個(gè)體排序.

2.5.3 選擇、交叉

保留上一代種群p/2個(gè)較優(yōu)的個(gè)體作為下一代樣本，并選擇上一代種群的第i(0≤i

NABG使用Saraph[8]提出的交叉函數(shù)產(chǎn)生后代個(gè)體.該交叉算子利用Knuths正則分解和循環(huán)分解算法利用兩個(gè)父代個(gè)體交叉產(chǎn)生一個(gè)子代個(gè)體，保證子代個(gè)體可以繼承兩個(gè)父代個(gè)體幾乎各一半的特性.

2.6 算法流程

算法1.NABG算法

輸入：源網(wǎng)絡(luò)G1、目標(biāo)網(wǎng)絡(luò)G2，序列相似性文件，種群大小p，迭代次數(shù)閾值n_gen

輸出：比對(duì)結(jié)果A

Begin

1.使用公式(2)、公式(3)計(jì)算節(jié)點(diǎn)和邊重要性得分NIS、EIS；

2.使用公式(1)、公式(4)計(jì)算節(jié)點(diǎn)對(duì)相似性得分S(u，v)；

3.根據(jù)步驟2的節(jié)點(diǎn)對(duì)相似性得分初始化種群{A0，A1，...，Ap-1}；

4.使用公式(6)計(jì)算種群個(gè)體適應(yīng)度值F(A)并排序；

5.選擇、交叉產(chǎn)生下一代；

6.重復(fù)步驟4、步驟5直到目標(biāo)函數(shù)收斂或者迭代次數(shù)達(dá)到最大閾值.

End

NABG算法流程如圖1所示.

圖1 NABG算法流程圖Fig.1 Flow chart of NABG algorithm

3 實(shí)驗(yàn)結(jié)果和分析

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

本文在真實(shí)網(wǎng)絡(luò)數(shù)據(jù)和合成網(wǎng)絡(luò)數(shù)據(jù)上分別進(jìn)行了3組實(shí)驗(yàn).真實(shí)網(wǎng)絡(luò)數(shù)據(jù)是來(lái)自Isobase[14]數(shù)據(jù)庫(kù)的3種真核生物的網(wǎng)絡(luò)數(shù)據(jù)：秀麗隱桿線蟲(Caenorhabditis Elegans，CE)、黑腹果蠅(Drosophila Melanogaster，DM)和釀酒酵母(Saccharomyces Cerevisiae，SC).合成網(wǎng)絡(luò)數(shù)據(jù)來(lái)自NAPAbench[15]數(shù)據(jù)庫(kù).幾種生物網(wǎng)絡(luò)的節(jié)點(diǎn)和邊信息見表1、表2.

表1 真實(shí)網(wǎng)絡(luò)數(shù)據(jù)Table 1 Real network data

表2 合成網(wǎng)絡(luò)數(shù)據(jù)Table 2 Synthesis network data

3.2 評(píng)價(jià)指標(biāo)

3.2.1 拓?fù)渲笜?biāo)

1)邊正確性EC

邊正確性是保守邊與源網(wǎng)絡(luò)邊數(shù)的比例.EC無(wú)法懲罰稀疏網(wǎng)絡(luò)到密集網(wǎng)絡(luò)的比對(duì).

2)誘導(dǎo)保守子結(jié)構(gòu)得分ICS

誘導(dǎo)保守子結(jié)構(gòu)(Induced Conserved Structure，ICS)得分計(jì)算保守邊和誘導(dǎo)邊的比例，誘導(dǎo)邊是源網(wǎng)絡(luò)中比對(duì)上的節(jié)點(diǎn)形成的集合在目標(biāo)網(wǎng)絡(luò)中所含有的邊的數(shù)量.ICS無(wú)法懲罰稠密網(wǎng)絡(luò)到稀疏網(wǎng)絡(luò)的比對(duì).

(7)

其中，G2(f(V1))表示G2中比對(duì)上的所有節(jié)點(diǎn)，|E(G2(f(V1)))|表示G2的誘導(dǎo)子網(wǎng)絡(luò)的邊數(shù).

3)對(duì)稱子結(jié)構(gòu)得分S3

對(duì)稱子結(jié)構(gòu)得分(Symmetric Substructure Score，S3)是EC和ICS的結(jié)合，既能懲罰稀疏網(wǎng)絡(luò)到密集網(wǎng)絡(luò)的比對(duì)，又能懲罰稠密網(wǎng)絡(luò)到稀疏網(wǎng)絡(luò)的比對(duì).

(8)

3.2.2 生物指標(biāo)

生物網(wǎng)絡(luò)比對(duì)的目的是尋找具有生物學(xué)意義的比對(duì)結(jié)果，在某種程度上，比對(duì)結(jié)果是否具有生物功能一致性相較拓?fù)浔Ｊ匦愿鼮橹匾?

1)平均歸一化熵MNE

平均歸一化熵(Mean Normalized Entropy，MNE)是歸一化熵(Normalized Entropy，NE)的平均值.MNE的值越小，表示比對(duì)結(jié)果的生物一致性越高，比對(duì)質(zhì)量越好.

(9)

其中，d是節(jié)點(diǎn)對(duì)中蛋白質(zhì)被注釋的GO注釋數(shù)量，pi是被GOi注釋的蛋白質(zhì)與所有被注釋的蛋白的比例.

2)特異性Specificity

成對(duì)網(wǎng)絡(luò)比對(duì)中，特異性(Specificity)是指被同種類型的GO項(xiàng)注釋的蛋白質(zhì)對(duì)占所有比對(duì)上的被注釋的蛋白質(zhì)對(duì)的百分比.

3)GO一致性GOC

基因同源一致性(Gene Ontology Consistency，GOC)是基于比對(duì)節(jié)點(diǎn)的GO一致性來(lái)衡量比對(duì)結(jié)果生物特性的常用方法.

(10)

其中，GO(i)表示節(jié)點(diǎn)i被注釋的GO項(xiàng)集合，ai表示與節(jié)點(diǎn)i比對(duì)上的節(jié)點(diǎn).

3.3 實(shí)驗(yàn)結(jié)果及分析

NABG使用參數(shù)α(0<α<1)平衡節(jié)點(diǎn)對(duì)的拓?fù)渑c生物相似性得分.如圖2所示，在CG網(wǎng)絡(luò)上對(duì)比不同的α取值產(chǎn)生的比對(duì)結(jié)果.當(dāng)α>0.4時(shí)，生物指標(biāo)MNE和Specificity趨向收斂，變化不大；α=0.5時(shí)拓?fù)渲笜?biāo)EC、ICS和S3取得最優(yōu)值，因此本文在后續(xù)實(shí)驗(yàn)過(guò)程中參數(shù)α取0.5.

圖2 參數(shù)α實(shí)驗(yàn)Fig.2 Experiments on α

為衡量NABG算法比對(duì)結(jié)果的質(zhì)量，本文使用真實(shí)網(wǎng)絡(luò)CE-DM，CE-SC，DM-SC和合成網(wǎng)絡(luò)CG、DMC、DMR各3組實(shí)驗(yàn)數(shù)據(jù)進(jìn)行實(shí)驗(yàn)并分別與MAGNA++、PROPER和SPINAL算法的比對(duì)結(jié)果比較分析.NABG算法中α=0.5，p=5000，n_gen=3000，MAGNA++、PROPER和SPINAL算法的參數(shù)設(shè)置參照原文.

3.3.1 與MAGNA++結(jié)果比較分析

NABG與MAGNA++都是基于遺傳算法的成對(duì)生物網(wǎng)絡(luò)比對(duì)算法，且NABG在迭代過(guò)程中使用了MAGNA算法的交叉算子，因此本文首先與MAGNA++算法進(jìn)行對(duì)比實(shí)驗(yàn).MAGNA++算法的比對(duì)結(jié)果隨著物種數(shù)目以及迭代次數(shù)的增加而變好，本文以CG合成網(wǎng)絡(luò)為例，將NABG(p=5000)分別與MAGNA++初始物種p為5000和p取默認(rèn)參數(shù)15000時(shí)產(chǎn)生的比對(duì)結(jié)果比較分析.

圖3 NABG與MAGNA++拓?fù)渲笜?biāo)得分Fig.3 Score of NABG and MAGNA++ on topological metrics

在拓?fù)渲笜?biāo)上，分別依據(jù)EC、ICS、S3指標(biāo)對(duì)比各算法在迭代了n(n=0，500，100，1500，2000)次后產(chǎn)生的比對(duì)結(jié)果，如圖3所示.在生物指標(biāo)上，分別依據(jù)MEN和Specificity指標(biāo)對(duì)比實(shí)驗(yàn)結(jié)果，如圖4、圖5所示.

實(shí)驗(yàn)表明，NABG和MAGNA++算法比對(duì)結(jié)果的拓?fù)滟|(zhì)量和生物質(zhì)量隨著迭代次數(shù)的增加而提高，并且NABG算法的收斂速度快于MAGNA++.在各項(xiàng)拓?fù)渲笜?biāo)以及生物指標(biāo)中，NABG(p=5000)的比對(duì)結(jié)果明顯優(yōu)于MAGNA++(p=5000)和MAGNA++(p=15000)的比對(duì)結(jié)果.

3.3.2 合成網(wǎng)絡(luò)實(shí)驗(yàn)比對(duì)結(jié)果分析

4種算法在合成網(wǎng)絡(luò)上的比對(duì)結(jié)果如表3所示，分別依據(jù)EC、ICS、S3、MNE、Specificity 5項(xiàng)指標(biāo)對(duì)比4種算法.表3中指標(biāo)最高的數(shù)值用黑體標(biāo)出，次高的數(shù)值用下劃線標(biāo)出.從表3中可以看出，MAGNA++算法和PROPER算法在各項(xiàng)指標(biāo)中表現(xiàn)最差.在拓?fù)浜蜕镏笜?biāo)上，NABG的結(jié)果在各組實(shí)驗(yàn)中均取得較好的結(jié)果，與SPINAL不相上下.

表3 在合成網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果Table 3 Experiments on synthesis networks

3.3.3 真實(shí)網(wǎng)絡(luò)實(shí)驗(yàn)比對(duì)結(jié)果分析

在真實(shí)網(wǎng)絡(luò)上，分別依據(jù)EC、ICS、S3、GOC這4項(xiàng)指標(biāo)對(duì)比4種算法，各項(xiàng)指標(biāo)對(duì)比結(jié)果如表4所示.表4中指標(biāo)高的數(shù)值用黑體標(biāo)出，次高的數(shù)值用下劃線標(biāo)出.在CE-DM，CE-SC，DM-SC 3對(duì)物種的實(shí)驗(yàn)結(jié)果中，MAGNA++算法的表現(xiàn)最差，SPINAL算法的拓?fù)渲笜?biāo)較好而生物指標(biāo)很差，PROPER算法生物指標(biāo)較好而拓?fù)渲笜?biāo)較差.NABG算法的生物指標(biāo)優(yōu)于PROPER算法，并且拓?fù)渲笜?biāo)與SPINAL算法較為接近.

表4 在真實(shí)網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果Table 4 Experiments on real networks

3.3.4 比對(duì)結(jié)果生物學(xué)意義分析

當(dāng)一個(gè)節(jié)點(diǎn)對(duì)不存在公共的GO注釋項(xiàng)時(shí)，這個(gè)節(jié)點(diǎn)對(duì)被認(rèn)為不具有功能相似性[16].節(jié)點(diǎn)對(duì)被注釋的公共GO項(xiàng)越多，比對(duì)越具有生物學(xué)意義[16，17].為了進(jìn)一步分析各算法比對(duì)結(jié)果的生物學(xué)意義，本文比較了各算法產(chǎn)生的比對(duì)結(jié)果中包含c(c>0)個(gè)公共GO注釋的節(jié)點(diǎn)對(duì)數(shù)目，如圖6所示.在CE-SC和DM-SC兩組實(shí)驗(yàn)中，NABG產(chǎn)生的具有生物學(xué)意義的節(jié)點(diǎn)對(duì)明顯多于其它3種算法，在CE-DM實(shí)驗(yàn)中，NABG比對(duì)結(jié)果優(yōu)于MAGNA++和SPINAL，節(jié)點(diǎn)對(duì)數(shù)目在c=4時(shí)少于PROPER.實(shí)驗(yàn)表明，NABG算法產(chǎn)生的比對(duì)結(jié)果相較其他算法更具生物學(xué)意義.

圖6 公共GO注釋項(xiàng)Fig.6 Common GO terms

綜合合成網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)的實(shí)驗(yàn)結(jié)果來(lái)看，4種比對(duì)算法中，MAGNA++算法表現(xiàn)最差；SPINAL算法在合成網(wǎng)絡(luò)中表現(xiàn)最優(yōu)，但在真實(shí)網(wǎng)絡(luò)中，其生物質(zhì)量較差；PROPER算法在合成網(wǎng)絡(luò)中不占優(yōu)勢(shì)，在真實(shí)網(wǎng)絡(luò)中生物質(zhì)量提升但拓?fù)滟|(zhì)量較差；NABG算法在合成網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)的實(shí)驗(yàn)中，其比對(duì)結(jié)果的拓?fù)渲笜?biāo)和生物指標(biāo)均能保持均衡的高指標(biāo)且更具有生物學(xué)意義.

4 結(jié)束語(yǔ)

本文提出一種新的成對(duì)PPI網(wǎng)絡(luò)全局比對(duì)算法NABG，針對(duì)PPI網(wǎng)絡(luò)比對(duì)結(jié)果難以同時(shí)取得好的拓?fù)涮匦院蜕锾匦赃@一問(wèn)題，在計(jì)算節(jié)點(diǎn)對(duì)的相似性得分時(shí)，基于節(jié)點(diǎn)和邊的重要性得分計(jì)算節(jié)點(diǎn)對(duì)的拓?fù)湎嗨菩?，引入生物序列信息，使得在拓?fù)浣Y(jié)構(gòu)和功能上重要的節(jié)點(diǎn)更可能被比對(duì)上.NABG算法利用節(jié)點(diǎn)對(duì)的拓?fù)浜蜕镄畔⒊跏蓟N群；在種群優(yōu)化過(guò)程中，利用包含節(jié)點(diǎn)相似性和邊保守性的目標(biāo)函數(shù)優(yōu)化比對(duì)結(jié)果.實(shí)驗(yàn)表明，NABG可以在拓?fù)渲笜?biāo)和生物指標(biāo)上取得均衡的高指標(biāo)，且比對(duì)結(jié)果具有生物學(xué)意義.