融合多種拓撲信息的生物網絡比對算法

劉 曉，陳 璟，2

1(江南大學 人工智能與計算機學院，江蘇 無錫 214122) 2(江南大學 江蘇省模式識別與計算智能工程實驗室，江蘇 無錫 214122)

1 引 言

隨著計算機技術的迅猛發展，對復雜網絡的研究越來越受到人們的重視[1].其中對生物網絡的研究，可以揭示不同物種間的進化關系.生物網絡比對是分析不同生物間進化關系的重要手段，它可以幫助理解物種間的進化關系，有助于發現保守功能組件和功能預測[2].

根據網絡比對范圍分，有局部比對和全局比對，局部比對的目標是在參與比對的網絡中找到高度保守的連通子圖，通常比對上的區域會比較小.全局比對力圖尋找一種映射關系，使得網絡中盡可能多的結點被比對上，同時使比對的總體相似性最大.全局比對通常會產生一個較大的比對子圖，但比對質量次優.從參與比對的網絡個數來分，有成對比對和多比對.成對比對是指對兩個網絡進行比對，多比對則是指對兩個及兩個以上的網絡進行比對.根據結點間的映射關系，網絡比對又可分為一對一比對，一對多比對及多對多比對，一對一是指小網絡中的一個結點只能和大網絡中的唯一一個結點進行比對，一對多指小網絡中的一個結點可以和大網絡中的多個結點進行比對，多對多是指小網絡中的一個結點可以和大網絡中的多個結點進行比對，同時大網絡中的一個結點也可以和小網絡中的多個結點進行比對.本文算法為全局的，成對的，一對一網絡比對算法.

IsoRank[3]是成對全局生物網絡領域出現最早的算法，它主要使用了類似于谷歌的頁面排序算法進行結點間的相似性計算.PrimAlign[4]在IsoRank[3]所使用的類似頁面排序算法的基礎上加入了半馬爾可夫鏈進行目標函數計算.度標簽相似性的提出給了學者們研究網絡拓撲結構的一種新思路.GRAAL家族的系列算法主要使用了度標簽相似性來計算結點間的相似性得分，其中GRAAL[5]采用了貪心算法作為搜索算法，HGRAAL[6]使用了匈牙利算法作為搜索算法，MI-GRAAL[7]則使用了節點相似性和網絡拓撲結構相似性度量的組合來作為得分函數從而產生比對結果.GoT-WAVE[8]算法借鑒了度標簽相似性的思想，提出了使用標簽軌道轉移的方法進行網絡比對.鄰域相似性是結點拓撲相似性的一種重要度量方法.SPINAL[9]算法通過借助結點的一級鄰居信息來進行結點間的相似性函數計算.CLMNA[10]則提出了一種多鄰域的學習方法來發掘結點間的相似性.HubAlign[11]提出了結點的importance概念，認為在網絡中重要程度相似的結點更容易被比對上.此外近些年，模塊化的思想也被引入到了模塊比對中來，其中IBNAL[12]將每個團看作一個模塊進行比對，同時為了提高效率，引入了基于團的索引的概念.ModuleAlign[13]則根據模塊化結果計算結點間的相似性得分，接著使用動態匈牙利算法進行搜索從而獲得比對結果，PINALOG[14]則使用模塊化結果來尋找種子對，并使用種子擴展方法進行搜索，AligNet[15]算法則使用了類似分治的策略分別對兩個網絡中的模塊進行子比對，然后再合并子比對結果得到最后的比對.AligNet可以產生高生物功能質量的比對，但由于其對網絡結點拓撲信息挖掘不夠充分，導致其拓撲質量的提高受限，本文提出了一種新的算法ECAlign，在保證AligNet生物功能質量不降低的前提下，同時將其拓撲質量提高了13%左右，ECAlign主要貢獻如下:

1)首次提出了相關值的概念，可以捕捉PPI網絡的結構信息，及衡量結點間的相似性.

2)為了更充分地挖掘不同網絡結點間的相似性信息，提出了一種基于特征向量中心性的拓撲得分計算方法，并將其應用于模塊內比對階段得分函數的構造.

3)考慮到網絡的模塊化性質，引入了保守邊，以便能最大限度的獲取不同網絡模塊間的邊保守性.

2 ECAlign方法

2.1 問題定義

兩個PPI網絡全局比對，即對輸入的兩個網絡G1=(V1，E1)，G2=(V2，E2)進行比對，從而找到一種映射關系F，使得公式(1)成立.

(1)

其中F(u)指通過映射關系F與G1網絡中的結點u相匹配的G2中的結點，S(u，F(u))為結點對(u，F(u))之間的相似性得分.

比對算法之間的差異主要是得分函數與搜索算法的不同.得分函數用于評價結點之間的相似性，通常由拓撲與序列相似性組成，由于搜索算法的需求不同，得分函數可以有多個;搜索算法則根據得分函數搜索能使得公式(1)達到最大值的比對關系.類似于多目標優化問題，生物網絡比對問題是對拓撲與生物功能的優化，其中一個目標的優化往往會導致另一個目標的劣化[16]，因此尋求拓撲與生物功能的平衡是生物網絡比對算法的努力方向.

2.2 相關值

文獻[17]曾指出，網絡結點之間的連接會基于一些相似的性質，即結點與結點之間有某種共性才相連.另外，模塊劃分是針對同一個網絡中的結點進行研究的，而在PPI網絡構建時曾提到如果兩個蛋白質之間存在相互作用，則對應于網絡中連接兩個蛋白質的一條邊.由此可推，網絡結點之間的邊隱含了蛋白質間的功能相關性信息，即同一網絡中結點的相似性信息被編碼在PPI網絡的拓撲結構中.根據上述推測，定義如下關系:

強相關.若一對結點之間存在直接相互作用關系，那么稱該對結點為強相關結點.對于網絡G，其強相關結點集表示為Θ.

弱相關.對于結點(u，v)?Θ，?w∈V,其中V為結點集合，使得(u，w)∈Θ∧(w，v)∈Θ，則稱(u，v)為弱相關結點.另外若存在弱相關結點(ε，f)，且滿足(u，ε)∈Θ∧(f，v)∈Θ，也可稱(u，v)為弱相關結點.對于網絡G，其弱相關結點集表示為Φ.{(u，w)，(w，v)}稱為(u，v)的一條傳遞路徑，一對弱相關結點可以包含多種傳遞路徑，包含最少強相關結點對的傳播路徑為最小傳播路徑.

相關.強相關結點與弱相關結點統稱為相關結點，用Ψ表示，則Ψ=Θ∪Φ.

不相關.除ψ之外的其他任意結點對統稱為不相關結點，用N表示.

(2)

2.3 基于特征向量中心性的拓撲向量

為了更充分地挖掘不同網絡結點間的拓撲相似性信息，本文從結點比對的角度出發，提出了一種用以表征結點拓撲屬性的向量元組H=(x，y，z):

1)x(u)表示結點u的度，即u的鄰居數;

2)y(u)表示結點u的特征向量中心性，用以衡量結點在網絡中的中心性地位.網絡中處于中心地位的結點在拓撲結構和功能上都很重要，它們的變異速度往往更慢，因此也更保守，也就是說，它們更有可能被比對上[10];

3)z(u)表示結點u鄰居的平均特征向量中心性.待比對結點的鄰居結點也會向其提供相似性信息，如果一對結點的鄰居結點重要性是相似的，那么這對結點也是相似的.

其中對于圖G，其結點特征向量中心性的求解等同于對公式(3)進行特征值及特征向量的求解，其中Q為G的鄰接矩陣:

Qx=λx

(3)

計算方式如下:

1)計算鄰接矩陣Q的特征分解;

2)選擇x中有最大特征值的特征向量m;

3)第i個節點的特征向量中心性等于特征向量m中的第i元素.

本文通過計算不同網絡節點間H的歐式距離來衡量兩個結點的拓撲相似性，距離越小，相似性越高.對于網絡G1=(V1，E1)，G2=(V2，E2)，結點s∈V1，t∈V2的拓撲相似得分T(s，t)具體計算方式如公式(4)所示:

(4)

2.4 保守邊

模塊是指同一網絡中具有相似功能的蛋白質結點集合.參與比對的兩個模塊中結點較小者稱為源模塊，另一個則稱為目標模塊.源模塊與目標模塊分別來自不同的網絡.如果源模塊的兩個結點存在一條邊，且經這兩個結點映射到目標模塊后，對應被映射的兩個結點之間也存在一條邊，則稱源模塊中的這條邊為保守邊.如圖1所示，模塊A中的5個節點分別比對到模塊B中的6個節點，虛線表示節點間的映射關系，圖中加粗的邊即為保守邊.例如模塊A的結點a與b之間存在一條邊，結點a和b分別比對到模塊B中結點1和2，而結點1與2之間也存在一條邊，則ab這條邊就被認為是保守的，則圖1中存在ab、bd、cd這3條保守邊.

圖1 保守邊

對于模塊M1=(V1′，E1′)，M2=(V2′，E2′)，邊保守得分為公式(5):

(5)

其中M12為兩個模塊的結點比對映射關系集合，N(vi)指結點vi的鄰居集合，A為已經比對上的結點集合.

2.5 算法描述

對于網絡G1=(V1，E1)，G2=(V2，E2)，使用ECAlign算法對其進行比對的基本步驟如下:

Step 1.根據相關值矩陣，分別對G1，G2進行模塊劃分，得到模塊集合CG1，CG2.

Step 2.計算模塊中結點的拓撲度量距離，并結合序列相似性將CG1中的模塊分別與CG2中的模塊兩兩進行模塊內比對.

Step 3.計算兩兩模塊間的局部邊保守得分，并根據模塊內比對結果對CG1，CG2進行模塊間比對.

Step 4.對模塊間比對結果進行處理，得到1-1局部比對結果.

Step 5.去除已比對結點，重復Step 2～Step 4，直到至少有一個模塊內的結點全部比對上并且所有模塊間的權重均為0時停止，得到網絡G1，G2的最終比對結果.

ECAlign的偽代碼見算法1，其算法流程圖見圖2.

圖2 ECAlign算法流程

算法1.ECAlign算法

輸入:來自兩個物種的網絡G1=(V1，E1)和G2=(V2，E2)，序列相似性值blast;

輸出:比對結果A;

Begin

1.for allu∈V1 do

for allv∈V1 do

根據公式(2)計算結點對(u，v)的相關值;

同理計算G2中結點的相關值;

2.根據相關值分別對G1進行模塊化得到M1，對G2進行模塊化得到M2;

3.for allm1∈M1 do

for allm2∈M2 do

將m1，m2的中心結點u，v比對上(u，v)在步驟2中產生;

找出u，v的鄰居集N(u)，N(v);

for allp∈N(u)do

for allq∈N(v)do

根據公式(4)計算(p，q)的拓撲得分T(p，q);

總相似性Fn(p，q)=T(p，q)+blast(p，q);

根據Fn將N(u)N(v)使用匈牙利算法進行比對;

將p，q移除并尋找下一對Fn值最小的已比對結點，將該節點對代替(u，v)并重復本次循環，直到所有結點對擴展完;

4.模塊比對;

5.子比對合并;

6.重復步驟1-5，直到所有模塊相似性為0或小網絡中結點全被比對完;

End

算法1中步驟4，5與ECAlign相同，本文不再詳細贅述.

給定網絡G1=(V1，E1)，G2=(V2，E2)，ECAlign總的時間復雜度約為O(k2n).其中k為算法迭代的次數，n為兩個網絡中結點的最大值.

3 實驗及分析

3.1 實驗數據集及評價指標

為測試ECAlign的比對效果，本文選取了被廣泛使用的IsoBase[18]數據集的最新版本，SPINAL[8]，AligNet[15]等算法均使用該數據集進行實驗評估.本文將IsoBase中的M.musculus(MUS)，C.elegans(CEL)，D.melanogaster(DME)，S.cerevisiae(SCE)4個物種分別進行兩兩組合，共得到6個物種對，用以實驗評估.4個物種所對應的PPI網絡結點數目與邊數見表1.

表1 PPI網絡信息

目前已經提出了一些比對質量的評估方法，這些方法分為兩類，拓撲一致性和生物一致性.拓撲一致性用來評估比對區域的拓撲相似性.生物一致性用來評估蛋白質對的功能相似性，本文使用EC和AFC來分別作為比對結果的拓撲與生物評價指標，具體定義如下:

令G1=(V1，E1)，G2=(V2，E2)，且|V1|≤|V2|.設u1，v1∈V1，F為獲得最終結果的一種映射函數F:G1->G2，F(u1)，F(v1)∈V2，則EC(Edge Correctness)為在F映射下保守邊的比例.

(6)

功能一致性定義如下:

(7)

(8)

其中GO(u)指結點u所包含的GO術語[19]，NFS(Nodes Functional Score)通過計算一對結點對之間共享GO術語的比例來表示其功能相似性.AFC(Average Functional Coherence)則為所有比對結點相似性的平均值.

拓撲質量的評估方式:首先根據獲得的比對結果計算結果中所包含的保守邊.其次計算網絡G1中比對上的結點所包含的邊數，保守邊與該邊數的比值即為比對結果的拓撲質量得分.拓撲質量得分主要評估了算法在邊保守方面的能力.

生物質量的評估方式:對于每一對比對上的結點，計算它們所擁有的共享GO術語數，每個GO術語代表蛋白質所擁有的一種生物功能，共享GO術語越多，代表蛋白質越相似.共享GO術語數與兩個蛋白質所擁有的GO術語種類數的比值記為兩個蛋白質的結點功能得分.所有已比對蛋白質對的結點功能得分均值即為整個比對結果的生物質量得分.生物質量得分主要評估算法獲得功能高度相似的蛋白對的能力.

3.2 實驗結果與評估

3.2.1 ECAlign與AligNet比較

因ECAlign是在AligNet的基礎上提出的，故將其與AligNet進行比較，結果見表2，指標得分最好的采用加粗表示.就拓撲質量EC而言，除在SCE-DME上保持與AligNet相同的拓撲得分外，ECAlign在其他物種對上的得分均高于AligNet;同時ECAlign不但在大部分物種對上獲得了與AligNet相同的生物功能質量，且在MUS-DME與CEL-SCE兩個物種對上的AFC得分均超過了AligNet.因此ECAlign成功做到在保證AligNet生物功能不降低的前提下，提高了其拓撲比對質量.

表2 ECAlign與AligNet得分

3.2.2 ECAlign與其他算法

本文將ECAlign與其它主流網絡比對算法AligNet，SPINAL，ModuleAlign進行比較，其中ECAlign，AligNet，ModuleAlign均使用了模塊化思想進行網絡比對，而SPINAL是一種可以獲得高生物質量的比對算法.圖3、圖4給出了4種算法的EC，AFC得分.

圖3 比對算法的EC得分

圖4 比對算法的AFC得分

由圖3可知，在物種對MUS-CEL，MUS-SCE，MUS-DME上，ECAlign的EC得分最高，尤其在MUS-SCE上，AligNet的比對質量較ModuleAlign低，但通過改進得到的ECALign獲得了比ModuleAlign更高質量的比對;ECAlign在其他物種對上的表現僅次于ModuleAlign，傾向于對結點數目差距較大的網絡產生好的比對結果，但ModuleAlign在不同物種對上表現的穩定性相比其他算法較差，比對質量好壞不一.

由圖4可知，ECAlign的AFC得分僅次于SPINAL，但實際上與SPINAL差距很小.綜合來看ECAlign，AligNet，與SPINAL的AFC得分在大部分物種對上的差距都很小，基本保持在0.02左右，因此3種算法都可以產生高生物功能質量的比對結果，而ModuleAlign在所有物種對上的表現都是最差的.

3.2.3 不同算法的綜合表現

為綜合評估算法在拓撲與生物功能上的表現，本文使用Ulign[20]中的trade-off作為評估度量，其值為算法的拓撲得分與生物功能得分的幾何平均值，由于EC與AFC值范圍存在差異，本文分別將每種方法在不同物種對上的EC、AFC平均排名代替trade-off中的拓撲與生物得分，最后得到的trade-off為算法的綜合排名，見表3.可知，ModuleAlign綜合表現最差，主要因為其在生物功能方面表現最差且拓撲表現不穩定.AligNet無論在拓撲還是生物質量方面都沒有并特別突出的表現，當綜合比較時，其劣勢得到了放大，因此排名較差.SPINAL表現呈現兩極化，拓撲表現最差但生物功能質量最好，生物質量對拓撲質量的彌補使其綜合表現次優.ECAlign綜合排名最高，也即其綜合表現最好，得益于其高拓撲質量與生物質量的共同作用.

表3 比對算法的trade-off排名

4 結 論

生物網絡比對有助于幫助發現保守的功能成分和實現功能預測，本文提出的生物網絡比對算法ECAlign，通過在各階段得分函數中融入不同的拓撲信息，從而獲得了高拓撲質量的比對結果，同時其生物功能質量也有所提高，其綜合表現也是最佳的.

當源網絡與目標網絡結點數相差太大時，會導致很多目標網絡結點無法被比對，從而無法獲得這些結點的功能相關信息，下一步的工作重點是尋找一種能最大范圍覆蓋目標網絡的比對算法，從而使其蛋白質功能盡可能被挖掘.