隨機游走模型識別蛋白質網絡復合物算法

林志杰， 任 遠

(上海電機學院 電子信息學院， 上海 200240)

隨機游走模型識別蛋白質網絡復合物算法

林志杰， 任 遠

(上海電機學院 電子信息學院， 上海 200240)

識別出蛋白質復合物是理解蛋白質相互作用的重要方法。針對蛋白質網絡中存在假陰性和假陽性問題，通過隨機游走模型，有針對性對假陰性和假陽性數據進行有效篩選，定義HP-complex圖模型來識別具有生物意義的蛋白質復合物；利用GO本體計算蛋白質復合物之間的語義相似性，最終確定蛋白質復合物。實驗證明，提出的基于隨機游走模型的蛋白質復合物識別算法對輸入參數不敏感，算法能夠識別出有效的蛋白質復合物。

蛋白質復合物; 蛋白質網絡; 隨機游走; GO本體

當今生物信息發展迅猛，已經開發出很多生物學方法，如小規模(低通量)方法、co_IP大規模(高通量)方法、酵母雙雜交、串聯親和純化法等。蛋白質的識別方法眾多，但是在目前發現的生物蛋白質中，以人類蛋白質為例，還有近80%的蛋白質未被發現，其他生物蛋白質已經被研究、發現的更是微乎其微。

蛋白質網絡越大，需要檢測的蛋白質對數量也越多。若采用低通量檢測方法檢測蛋白質之間的相互作用，則耗費的時間、人力、物力資源也越大。但是，與低通量檢測方法相比，采用高通量方法來識別蛋白質相互作用的網絡數據更容易出現錯誤，其可靠性相對較低。這些錯誤分為兩種[1]： 假陽性(False Positive， FP)和假陰性(False Negative, FN)。假陽性是指實驗檢測出兩個蛋白質間存在而在真實的蛋白質網絡中并不存在的相互作用；假陰性是指實驗沒有檢測出來而真實的蛋白質網絡中卻存在的相互作用。文獻[2]中用實驗證明在用高通量實驗檢測出來的數據集中，這兩種錯誤出現的概率相差很大，其中絕大部分(高達92.5%)的錯誤是假陰性。由此可見，應用不同的試驗方法得到蛋白質相互作用數據的質量差異性較大，即便是應用相同的試驗方法，不同條件、不同的實驗人員得到的相互作用數據也不盡相同，所獲得的數據噪聲較多，存在大量的假陰性、假陽性數據。因此，非常有必要設計具有針對性、能更有效應對假陽性、假陰性數據的計算方法，來糾正數據集中的大部分假陰性、假陽性的蛋白質相互作用。

目前，主流的蛋白質復合物識別算法，主要通過識別蛋白質網絡中的全聯通圖或極大團的方法來識別蛋白質復合物，或定義新穎的圖模型結構[3]，如HP-complex識別，但是由于這些方法能夠識別的蛋白質相互作用不全，而且已經構建的蛋白質相互作用網絡中還存在著假陰性和假陽性的相互作用，故僅通過挖掘全聯通圖來識別蛋白質復合物就存在著很大的局限性。

另外，單純地依據蛋白質-蛋白質相互作用(Protein-Protein Interaction, PPI)網絡的拓撲結構特征來進行模塊識別，把網絡中的稠密子圖(Dense Subgraph, DS)作為要找尋的蛋白質復合物或功能模塊[4]，這些方法也存在一個共同的缺點[5-15]： 由于蛋白質模塊中的所有蛋白質在生物系統中共同完成某種生物功能，而這些模塊并非與PPI網絡中的稠密子圖做到一一對應，故單純地依據拓撲結構特征來進行模塊識別，會影響到后期蛋白質功能預測的精度及可信度。因此，如何在蛋白質網絡拓撲結構特征的基礎上，確定性地衡量網絡中的稠密子圖的功能意義是一個急需解決的問題。

為了解決蛋白質數據集中包含假陰性和假陽性噪聲數據的問題，以及利用圖模型尋找蛋白質復合物結構固定的局限性，本文研究了一個基于隨機游走模型的蛋白質復合物識別算法(Find Protein Complexes Based on Random Walk with Restart, RWSPFinder)，借助于隨機游走算法來預測蛋白質網絡上那些真正存在的相互作用的數據，從而去除那些假陰性或假陽性的噪聲數據；然后定義HP-complex圖模型來識別具有生物意義的蛋白質復合物；最后，根據GO本體計算蛋白質復合物之間的語義相似性，最終確定所識別的蛋白質復合物。算法對輸入參數不敏感，實驗驗證了提出算法的有效性。

1 蛋白質復合物識別

1.1隨機游走模型

Random Walk是隨機過程(Stochastic Process)的一個重要研究內容，是一種不規則的運動形式，通常描述的是最簡單的一維Random Walk過程。如考慮在數軸原點處有一只螞蟻，它自當前位置x處從t時刻出發，在下一個時刻(t+1)以1/2向前走一步，該點為

X_{t+1}=X_{t}+1

或以1/2向后退一步，該點為

X_{t+1}=X_{t}-1

這樣該螞蟻每個時刻到達的點序列就構成一個一維隨機游走過程。本質上，Random Walk是一種隨機化的方法，在實際生活中，如醉漢行走的軌跡、花粉的布朗運動、證券的漲跌等都與Random Walk有密不可分的關系。Random Walk已被成功地應用到數學、物理、化學、生物、經濟等各領域。

1.2HP-complex圖模型

給定物種的蛋白質互作網絡可以視為網絡圖G=(V,E)，其中，V為蛋白質結點；E為蛋白質相互作用邊的集合，從所有的邊的集合中去掉網絡中自連接邊和重復邊。為從蛋白質互作網絡或圖G中發現定義的蛋白質復合物，從而為從蛋白質網絡中識別蛋白質復合物做準備，本文定義以下概念。

定義1HP-vertices結點 給定蛋白質互作網絡G=(V,E)，其中，V為蛋白質互作網絡的頂點；E為蛋白質互作網絡的邊；H-index為一個圖模型，用H表示。利用HP-vertices結點代表H-index結點，定義為

其中，d(v)為網絡頂點v的度；h為蛋白數。

由HP-vertices結點可擴展至概念HP-neighbors。

定義2HP-neighbors HP-neighbors定義為HP-vertices蛋白質集的一階鄰居的集合。

定義3HP*-graph圖 蛋白質互作網絡G的子圖HP*-graph由HP-vertices和其HP-neighbors組成，除去了一階鄰HP-neighbors之間的邊。

對于一個蛋白質互作網絡，HP*-graph從一個很大的原始蛋白質互作網絡里分離出來，有可能是一個非連通子圖。因此，從非連通子圖HP*-graph中分離出所有的子圖、最終得到的蛋白質互作網絡的所有子圖為要識別的蛋白質復合物。

定義4HP-complex復合物 如果HP*-graph是非連通的，HP-complex定義為HP*-graph的所有子圖，故HP*-graph中分離的子圖都是要找的蛋白質復合物。

2 蛋白質復合物相似性計算

2.1GO的結構

基因本體GO有3個主要用途[16]： ① 指定可控制的結構化詞匯庫(即本體)，用來描述分子生物學的重點領域，包括基因產物特性和生物序列，為雜亂無章的生物概念和詞匯定義統一的概念稱謂、定義和概念之間的關系；② 應用基因本體GO來注釋生物數據庫中的序列、基因以及基因產物；③ 應用基因本體GO提供一個公共資源，讓人們方便使用GO本體，注釋數據集和GO軟件工具。基因本體論GO的定義法則使得目前很多合作的數據庫的生物信息查詢具有很好的一致性，而基因本體論中的定義語言具有多重結構，故其能在各種程度上支持生物信息查詢。

2.2基于隨機游走的蛋白質復合物算法

本文研究的RWSPFinder算法經過2次蛋白質相互作用數據的假陽性過濾： 第1次是對整個加權的蛋白質互作網絡進行重啟型的隨機游走，重構蛋白質互作網絡；然后，對重構的蛋白質互作網絡進行初始的蛋白質復合物識別。第2次是在找到的初始蛋白質復合物內部執行基于基因本體GO語義相似性的蛋白質相互作用假陽性過濾。

RWSPFinder算法的輸入、輸出偽代碼如下：

1. Input： PPIG(V,E,W); Gene Ontology tool; G-sesame; Rank threshold of Protein node; Similarity thresholdPs

2. Output： the Protein Complexes Set PC

3. Initializep0for Random Walk and the PC=Null that means the set of Protein Complexes is Null

4. Random Walk with Restart on Weighted PPI until pt to stable state

5. Obtaining the important proteins according to the threshold Pr from original PPI; Constructing the new PPI network

6. Executing the Algorithm HPCMiner on new PPI network to mining the initial Protein Complexes Set

若2個蛋白質之間的相似性越大，表示它們之間發生或具有相互作用的可能性越大；反之，則表示它們之間發生或具有相互作用的可能性也越小。本文通過設定GO語義相似性閾值，衡量蛋白質復合物內部相互作用的存在合理性。如果蛋白質之間的語義相似度大于指定閾值，則認為蛋白質之間相互作用存在合理，便保留在蛋白質復合物的內部；反之，則認為蛋白質之間不會發生相互作用，即被認定為假陽性過濾出蛋白質復合物。

3 實驗結果與分析

本文利用Graphweb工具，它是一個公共的基于圖分析數據的生物網絡Web服務器，也是一個生物網絡圖數據分析工具；該生物工具可以分析包括基因、蛋白質和基因表達微陣列數據等有向和無向生物網絡、加權網絡、無權網絡生物數據集[17]。實驗中，將4個生物蛋白質相互作用數據集進行處理，得到GraphWeb可以識別的規定的數據格式；然后，利用該實驗工具，分別上傳4個生物蛋白質互作網絡數據集，包括Human、Mouse、Rat和Yeast，得到每個蛋白質互作網絡的結點(Nodes)、邊(Edges)、邊密度(Edge Density, ED)和結點的平均度密度(Average Node Degree, AveD)信息，來了解和認識這些生物網絡的特征。

目前，在生物信息學中蛋白質復合物或蛋白質模塊識別已經成為生物領域的研究熱點和難點問題。關于識別出的復合物結果的評價標準也有很多，具有代表意義的評價標準有F-measure、共位置值、GO語義相似性、功能顯著性(富集分析)[18]。其中，功能顯著性是在GO語義豐度基礎上提出的一種新的用來衡量蛋白質復合物或模塊集的標準[19]。本文主要采用F-measure以及功能顯著性即GO富集分析的方法來評測本文找到的蛋白質復合物具有的生物學意義。

本文提出的RWSPFinder算法對4個蛋白質互作網絡數據集Yeast、Human、Mouse、Rat進行蛋白質復合物識別，最終得到蛋白質網絡的蛋白質復合物數量分別是377、1646、344、65個。

為了清晰地表達蛋白質復合物的識別結果，用RWSPFinder算法識別出的蛋白質網絡的復合物數量分為4組，當蛋白質復合物中包含的蛋白質復合物數Pn≥100時，該蛋白質復合物為A組；當50≤Pn<100時，該蛋白質復合物為B組；當30≤Pn<50時，該蛋白質復合物為C組；當2≤Pn<30時，該蛋白質復合物為D組。統計結果如表1所示。

表1 在4個蛋白質網絡上RWSPFinder識別的蛋白質復合物的信息Tab.1 Protein complex identified by the algorithm for protein-protein interaction network on four PPIs

由表1可見，酵母蛋白質網絡中僅有幾個很大的簇，約有96.02%的蛋白質復合物包含的蛋白質個數小于30，表明通過RWSPFinder算法得到的蛋白質復合物的大小在2～30的正常范圍內。在Human數據集中，所有尋找到的蛋白質復合物中包含的蛋白質有97.93%都小于30個；在Mouse數據集上，所有尋找到的蛋白質復合物中包含的蛋白質有98.84%都小于30個。而在Rat數據上，該比率竟然幾乎達到100%。

實驗結果表明，基于隨機游走模型以及GO本體過濾假陽性數據的蛋白質復合物識別方法是非常有效的，能夠找到具有生物意義的蛋白質復合物。

4 結 語

本文研究了一種新的蛋白質復合物識別算法。該算法致力于提高當前蛋白質網絡數據質量，去掉由于高通量生物實驗獲得的蛋白質相互作用數據集存在的假陰性、假陽性數據，從而提高了蛋白質復合物識別的準確性和有效性。該方法利用真實的蛋白質相互作用數據集進行實驗驗證，通過識別到的蛋白質復合物的實驗結果表明，基于隨機游走模型的蛋白質復合物識別算法能夠去掉蛋白質網絡上的假陽性、假陰性的相互作用數據，是一個非常實用和有效的蛋白質復合物識別模型。

[1] Ovaska K,Laakso M,Hautaniemi S.Fast gene ontology based clustering for microarray experiments[J].BioData Mining,2008(1): 11.

[2] Du Zhidian,Li Lin,Chen Chinfu,et al.G-SESAME： Web tools for Go-term-based gene similarity analysis and knowledge discovery[J].Nucleic Acids Research,2009,37: W345-W349.

[3] Gibbons F D,Roth F P.Judging the quality of gene expression-based clustering methods using gene annotation[J].Genome Research,2002,12(10)： 1574-1581.

[4] Yu Liang,Gao Lin,Kong Chuiliang.Identification of core-attachment complexes based on mining maximal frequent patterns in proteinprotein interaction networks.[C]∥2010 IEEE International Conference on Bioinformatics and Biomedicine Workshops. HongKong: IEEE,2010: 29-34.

[5] Wang Jianxin,Lin Binbin,Li Min,et al.Identifying protein complexes from interaction networks based on clique percolation and distance restriction[J].BMC Genomics,2010,11(suppl2): s10.

[6] Zheng Guangyong,Wang Haibo,Wei Chaochun,et al.iGepros： An integrated gene and protein annotation server for biological nature exploration[J]. BMC Bioinformatics,2011,12(Suppl14)： S6.

[7] Lacruz R S，Brookes S J，Wen Xin，et al.Adaptor protein complex 2-mediated,clathrin-dependent endocytosis,and related gene activities,are a prominent feature during maturation stage amelogen[J]. Journal of Bone and Mineral Research，2013,28(3): 672-687.

[8] Cousins S L,Innocent N,Stephenson F A.Netol associates with the NMDA receptor/amyloid precursor protein complex[J].Journal of Neurochemistry,2013,126(5): 554-564.

[9] Piwowara M,Banacha M,Koniecznyb L.Irena Roterman Hydrophobic core formation in protein complex of cathepsin[J].Journal of Biomolecular Structure and Dynamics,2014,32(7): 623-634.

[10] OlzhausenJ,Moritz T,Neetz T,et al.Molecular characterization of the heteromeric coenzyme asynthesizing protein complex(CoA-SPC) in the yeast Saccharomyces cerevisiae[J]. FEMS Yeast Research,2013，13(6)： 565-573.

[11] Lee N P,Mruk D D,Conway A M,et al.Zyxin,axin,and Wiskott-Aldrich syndrome protein are adaptors that link the cadherin/catenin protein complex to the cytoskeleton at adherens junctions in the seminiferous epithelium of the rat testis[J]. Journal of Andrology,2004,25(2): 200-215.

[12] Alegrel E,Rebmann V,Lemaoult J,et al. In vivo identification of an HLA-G complex as ubiquitinated protein circulating in exosomes[J]. European Journal of Immunology,2013,43(7): 1933-1939.

[13] Foerster S,Kacprowski T,Dhople M V,et al.Characterization of the EGFR interactome reveals associated protein complex networks and intracellular receptor dynamics[J].PROTEOMICS,2013,13(21): 3131-3144.

[14] Whitworth K,Bradford M K,Camara N， et al.Targeted disruption of an EH-domain protein endocytic complex,Pan1-End3[J].Traffic,2014,15(1): 43-59.

[15] Brenner D A.Fra,Fra away： The complex role of activator protein 1 in liver injury[J].Hepatology,2014,59(1): 19-20.

[16] Ashburner M,Ball C A,Blake J A,et al.Gene ontology： tool for the unification of biology[J].Nature Genet,2000,25： 25-29.

[17] Reimand J,Tooming L,Peterson H,et al.GraphWeb： mining heterogeneous biological networks for gene modules with functional significance[J].Nucleic Acids Research,2008,36： W452-W459.

[18] King A D,Przulj N,Jurisica I. Protein complex prediction via cost-based clustering[J]. Bioinformatics,2004,20(17)： 3013-3020.

[19] Altaf-UI-Amin M,Shinbo Y,Mihara K,et al.Development and implementation of an algorithm for detection of protein complexes in large interaction networks[J]. BMC Bioinformatics,2006,7： 207.

Algorithm of Protein Complex Identification Using Random Walk Model

LINZhijie，RENYuan

(School of Electronic Information Engineering, Shanghai Dianji University,Shanghai 200240, China)

Protein complex identification is important in understanding the protein-protein interaction. This paper solves the problem of false positive and false negative in protein networks. A random walk model is used for effective screening false positive and false negative in the filtered data. With relatively clean protein networks, the definition of HP-complex graph model is given to identify protein complexes with biological meaning and semantic. GO ontology is used between calculated protein complex similarities, and the protein complexes are ultimately determined. Experiments show that the proposed algorithm for is insensitive to the input parameters. The algorithm can effectively identify protein complex.

protein complex; protein-protein interaction network; random walk; gene ontology

2014 - 10 - 08

林志杰(1980-)，女，講師，博士，主要研究方向為數據挖掘，E-mail: linzj@sdu.edu.cn

2095 - 0020(2014)06 -0347 - 05

TP 301.6

A