基于Minimum Cuts的蛋白質交互識別

張 景，吳紅梅，牛 耘

(南京航空航天大學 計算機科學與技術學院，江蘇 南京 210016)

基于Minimum Cuts的蛋白質交互識別

張 景，吳紅梅，牛 耘

(南京航空航天大學 計算機科學與技術學院，江蘇 南京 210016)

蛋白質交互信息對生物、醫藥研究有著重要意義，是生物醫學領域一項重要的研究內容。對基于大規模語料庫的蛋白質交互識別,直接利用已有的PPI數據庫，能顯著降低人工標注的代價。為此，在大規模語料庫的基礎上，提出了基于Minimum Cuts的蛋白質交互識別方法。在關系相似性框架下,Minimum Cuts分類器不僅采用SVM算法對單個蛋白質對進行初步分類預測，還利用蛋白質對之間的相似性約束判斷結果，使分類結果更加準確。實驗結果表明，利用Minimum Cuts分類器進行PPI的識別結果優于SVM分類器的識別結果。當訓練數據為20%時，Minimum Cuts分類器的識別結果優于訓練數據為80%時的SVM分類器的識別結果。

關系相似性;Minimum Cuts;支持向量機;蛋白質交互

0 引 言

蛋白質是組成細胞最重要的成分，通過交互作用執行著細胞內多數重要的分子過程，如DNA復制。活體細胞內幾乎所有的生化反應都與蛋白質交互(Protein-Protein Interaction,PPI)作用有關。所以，蛋白質交互作用已成為生物學研究的重要內容，是解決大量醫學難題的關鍵信息[1-3]。隨著生物醫學的發展，越來越多的蛋白質交互關系被發現，大量PPI信息隱藏在醫學文獻文本數據庫PubMed中[4]。手工從文獻提取PPI信息的方式已難以滿足生物醫學研究的需求。為了幫助生物醫學領域的專家從文獻中獲取有效的信息，基于自然語言處理的蛋白質交互識別已經成為一項重要的研究內容。

目前，常用的文本PPI識別的技術主要包括：基于共現的方法[5]、基于規則的方法[6]和基于機器學習的方法[7-8]?；诠铂F的方法[9]根據兩個蛋白質共現次數來判斷這兩個蛋白質之間是否存在交互關系?；谝巹t的方法[10-11]通過構建一些能夠刻畫蛋白質交互關系的規則，通過文本匹配的方式來尋找對應的交互關系。

機器學習的方法主要包括兩大類：基于特征的方法和基于核函數的方法?；谔卣鞯姆椒ㄖ饕捎弥С窒蛄繖C(SVM)，從標注有交互關系的蛋白質對的句子中抽取單詞、短語和依賴關系等作為特征建立模型，進而判斷蛋白質對是否存在交互關系[12-13]?；诤撕瘮档姆椒ㄉ钊胙芯烤渥咏Y構，通過設計核函數衡量不同蛋白質對間的相似度，然后采用支持核函數的分類器進行PPI關系識別。Haussler[14]針對離散結構提出了卷積核；Lodhi等[15]將特征空間特定長度詞語子序列的內積作為核函數的計算方式，提出了字符串核；Bunescu等[16]提出了最短依賴路徑核，將句子以樹的形式表示，用兩個實體之間的最短路徑表示實體之間的關系。目前的機器學習方法主要以單個句子為研究對象。這些方法能較好地從句子層面對PPI關系進行描述及判斷，但是對于語法復雜和交互關系描述間接的句子，僅依賴單個句子中的信息往往難以進行準確判斷。針對這些問題，文獻[17]直接以現有的PPI數據庫為訓練數據，提出了一種新的基于文本相似性來比較識別蛋白質交互的方法。

然而，這些監督的學習方法的有效性依賴于足夠大且高質量地標注了蛋白質交互信息的文本集合，構造這樣的訓練集仍需要耗費大量的人力資源。為此，提出了一種新的基于關系相似性的識別方法，充分利用大規模語料庫資源和已有的標注信息進行PPI識別。與上述方法不同，在關系相似性框架下，構建蛋白質對的相似性網絡，利用Minimum Cuts算法進行蛋白質交互識別。與SVM相比，利用更少的訓練數據取得了更高的精度。

1 基于關系相似性的PPI識別

1.1 關系相似性

在PPI識別工作中，蛋白質之間的交互就是兩個蛋白質之間的關系。例如，兩個蛋白質protein1和protein2交互，它們的關系可表示為“R(protein1，protein2)”，R表示交互關系。

蛋白質對交互關系的文本表達中存在相似性，表現在描述交互關系的句子在表達上是相似的，例如：

(1)SPB association of Plo1 is the earliest fission yeast mitotic event recorded to date.

(2)All proteins of this family have Cdk-binding and anion-binding sites, but only mammalian Cks1 binds to Skp2 and promotes the association of Skp2 with p27 phosphorylated on Thr-187.

(3)A low concentration of GerE activated cotB transcription by final sigma(K) RNA polymerase.

(4)The SpoIIE phosphatase indirectly activates sigmaF by dephosphorylating a protein (SpoIIAA-P) in the pathway that controls the activity of the transcription factor.

句中黑體的單詞表示蛋白質名稱。在第1、2句，存在交互關系的蛋白質對(SPB,Plo1)和(Skp2,p27)的關系都為“association of”。第3、4句中，有交互關系的蛋白質對(GerE,cotB)和(SpoIIE, sigmaF)的關系為“activated(GerE,cotB)”和“activates(SpoIIE,sigmaF)”，而activated、activates它們的詞根都為activate。因此，可以通過比較目標蛋白質對關系與已知關系的蛋白質對的相似性來判斷兩個蛋白質之間的關系。

1.2 基于關系相似性的PPI識別描述

基于關系相似性的PPI識別主要分成三個模塊：收集關系描述、關系表示、關系相似性計算。

1.2.1 關系描述

對于目標蛋白質對，首先利用PubMed數據庫提供的接口收集同時包含目標蛋白質對中兩個蛋白質的所有句子，將這個句子集合作為目標蛋白質對的簽名檔。每個簽名檔都較完整地描述了目標蛋白質對中兩個蛋白質之間的關系。

1.2.2 關系表示

以一元詞作為特征，采用向量空間模型表示蛋白質對(protein1，protein2)的關系，向量的每一維對應一個特征單詞。將簽名檔中所有的句子去除停止詞、單字符單詞和數字，選擇至少在25篇簽名檔中出現的單詞作為特征。最終得到了4 867個特征，用這些特征單詞表示蛋白質對。采用二值權重(0/1)表示特征權重，即特征單詞出現時權值為1，不出現權值為0。

1.2.3 關系相似性計算

(1)

根據目標蛋白質對與已知交互關系蛋白質對的相似度，選擇合適的分類算法進行PPI識別。

2 基于Minimum Cuts的PPI識別

目前只存在少量可用于監督學習的標注數據集，因而如何有效利用已有的標注數據至關重要。鑒于此，直接以現有PPI數據庫為訓練數據，提出了基于Minimum Cuts的PPI識別方法?；贛inimum Cuts的分類方法可綜合兩方面對PPI關系進行判斷：對單個目標蛋白質對關系進行初步判斷；利用蛋白質對之間的相似性約束判斷結果。

2.1 Minimum Cuts算法描述

首先，對目標分類問題建立無向圖G=(V,E)，源點s和匯點t表示C1和C2兩個目標類。圖中的節點v1,v2,…,vn表示訓練集和測試集中所有的實例x1,x2,…,xn。圖G中的邊可分E=E(vi,s)∪E(vi,t)∪E(vi,vj)，其中E(vi,s)與E(vi,t)表示任意實例點vi與目標類C1、C2之間的關系，邊E(vi,s)的權重表示實例xi為C1類的概率大小，E(vi,t)的權重表示實例xi為C2類的概率大小。E(vi,vj)表示實例xi與xt之間是相似的，其權重表示兩實例之間的相似度，相似度越大權重越大，相似度越小權重越小。例如，圖1是一個Minimum Cuts分類器示意圖，s和t分別表示C1和C2類，Y表示訓練數據中屬于C1的實例，N表示訓練集中屬于C2的實例，M表示待標記的實例。虛線經過的邊就是圖1的最小割，并將M與Y分為C1。

圖1 Minimum Cuts分類器

基于Minimum Cuts的分類算法，通過求解無向圖的割Cut(S,T)將權值小的邊移除，實現實例數據的分類。其中Cut(S,T)將V劃分為S和T=V-S兩部分，源點s∈S，匯點t∈T。weight(u,v)表示割邊的權重，所有割邊的權重和為W(S,T)。圖G的最小割，就是使得W(S,T)取最小值時的Cut(S,T)。

(2)

2.2 基于關系相似性的PPI識別與Minimum Cuts的聯系

基于Minimum Cuts的分類器可以通過無向圖中邊的權值表示實例間的相似度大小。在求無向圖的最小割時，將權值較小的邊移除，即將相似度小的實例分開，完成了實例分類。

基于關系相似性的PPI識別通過比較目標蛋白質對與已知關系的蛋白質對的相似性來判斷目標蛋白質對的交互作用，將相似度大的關系分為一類。這和Minimum Cuts分類算法的核心思想一致。并且PPI識別的目標類為兩個(有交互關系和無交互關系)，符合Minimum Cuts模型。

因此，在關系相似性框架下，構建Minimum Cuts分類模型，實現PPI識別。

2.3 構建Minimum Cuts分類器

為了建立Minimum Cuts分類器進行PPI識別，建立了無向圖表示蛋白質對與目標類(有交互關系、無交互關系)以及蛋白質對與蛋白質對之間的關系。最終通過求解圖的最小割，將蛋白質對進行分類，實現PPI識別。

2.3.1 實例點與s、t之間邊的權重計算

在交互關系識別問題中，以圖1為例，其中s和t分別表示兩個目標類，即存在交互關系和不存在交互關系。Y表示訓練集中屬于有交互關系的一個蛋白質對，N表示訓練集中不存在交互關系的一個蛋白質對，M表示待標記的蛋白質對。Y、M和N與s、t之間的邊，表示實例與目標類(有交互關系、無交互關系)之間的關系。邊的權值表示一個實例為有交互關系、無交互關系的概率值大小。采用SVM算法預測蛋白質對是有交互關系和無交互關系，得到概率值作為相應邊的權重。

將訓練集中有交互關系的點與s之間邊的權值設為100，與t之間邊的權值設為0.01。無交互關系的點與s之間的邊的權值設為0.01，與t之間的邊權值設為100。

2.3.2 實例點之間邊的權重計算

實例點之間的邊表示兩個蛋白質對關系之間是相似的，兩個蛋白質對關系相似度值越大，邊權重越大。根據表示蛋白質對關系的特征向量，采用余弦距離計算任意兩個蛋白質對之間的相似度，余弦值越大權重越大，兩個蛋白質對越相似，相應的實例點之間邊的權重也越大。

3 實 驗

3.1 實驗數據

實驗中，將有交互關系的蛋白質對作為正類，無交互關系的蛋白質對作為負類。正類蛋白質對來自生物醫學專家手工收集信息建立的PPI數據庫HPRD，共1 420對。而對于負類，根據HPRD中包含的蛋白質采用隨機組合的方法產生負類蛋白質對(刪除HPRD已包含的蛋白質對)，最后只保留被PubMed數據庫中文獻記載的蛋白質對作為無交互蛋白質對的訓練集，共有1 353對。因此，實驗數據集中共包含2 773對蛋白質對。

3.2 實驗設置

SVM已被證實為一種非常有效的分類算法，是基于機器學習的蛋白質交互關系識別所采用的重要分類模型。實驗部分共包括兩個部分：基于SVM的PPI識別和基于Minimum Cuts的PPI識別。

在基于Minimum Cuts的PPI識別中，首先計算實例點對與s、t之間邊的權重，即蛋白質對為有交互關系或無交互關系的概率值大小，然后計算實例點之間邊的權重。采用SVM算法獲得無向圖中未標記蛋白質對的分類概率(LIBSVM[18])。在采用余弦距離計算相似度時，當兩個蛋白質對間的相似度值小于0.2時，認為兩個蛋白質對不相似，在構建無向圖時兩個點之間不設邊。

實驗中，采用五折交叉驗證的方法進行驗證，將全部數據分為五份，每次以其中一份作為測試數據。對同一份測試數據，分別選擇了總數的5%、10%、20%、40%、60%和80%的蛋白質對作為訓練數據進行實驗。然后，將五組測試數據的識別結果的平均值作為一次識別的結果。

3.3 實驗結果及分析

表1為基于監督學習的Minimum Cuts的PPI識別結果。表2為SVM分類器的PPI識別結果。表中的第一列序號1,2,…,6依次對應訓練數據為5%，10%，20%，40%，60%和80%的分組。圖2、圖3是對比采用Minimum Cuts分類器與SVM分類器，正類蛋白質對和負類蛋白質對識別結果的F值的變化。

表1 基于監督學習Minimum Cuts的識別結果 %

表2 基于SVM分類器的識別結果 %

表1和表2的實驗結果說明，對于兩種分類器，當訓練數據較少時，正類蛋白質對識別結果的召回率較低。隨著訓練數據的增多，正類蛋白質對的召回率逐漸提高。對SVM分類器，準確率隨訓練數據增加變化不大，而Minimum Cuts分類器的正、負類的F值及準確率隨訓練數據增加都有明顯提高。說明Minimum Cuts有效利用了蛋白質對簽名檔相似性進行分類。

負類蛋白質對精確度也逐漸提高，整體的識別準確率也明顯提升。實驗結果表明，Minimum Cuts分類器的整體識別結果比SVM分類器要好。當訓練數據達到80%時，Minimum Cuts分類器識別的正類F值為76.90%，負類F值為76.13%，整體準確率為75.56%，相對SVM分類器識別的正類F值提高了3.12%，負類F值提高了4.24%，整體準確率提高了3.65%。

圖2 有交互關系的蛋白質識別結果的F值變化趨勢對比

圖3 無交互關系的蛋白質識別結果的F值變化趨勢對比

從圖2、圖3中可以看出，采用不同比例的訓練數據，基于Minimum Cuts分類器的PPI識別，它的正、負類蛋白質對識別結果的F值都優于SVM分類器。當訓練數據為20%時，Minimum Cuts分類器的識別結果優于訓練數據為80%時的SVM分類器的識別結果。實驗結果表明，Minimum Cuts分類器能更有效地利用標注數據進行PPI識別。

4 結束語

為充分利用已有的PPI數據庫實現蛋白質交互識別，降低人工標注的代價，在大規模語料庫的基礎上，提出了關系相似性框架下基于Minimum Cuts的PPI識別方法。通過構建無向圖，不僅對目標蛋白對是否存在交互關系進行了初步判斷，還表示了蛋白質對與蛋白質對之間的相似性。通過蛋白質對之間的相似性約束判斷結果，用較少的訓練數據取得了優于SVM的精度，有效緩解了PPI識別問題中標注數據缺乏帶來的困擾。

[1] Prasad T S K,Goel R,Kandasamy K,et al.Human protein reference database-2009 update[J].Nucleic Acids Research,2009,37:767-772.

[2] Kerrien S, Alam-Faruque Y, Aranda B,et al.IntAct-open source resource for molecular interaction data[J].Nucleic Acids Research,2007,35:561-565.

[3] Ceol A,Aryamontri A C,Licata L,et al.MINT,the molecular interaction database:2009 update[J].Nucleic Acids Research,2010,38:532-539.

[4] U.S.National Library of Medicine.PubMed[EB/OL].2000.http://www.ncbi.nlm.nih.gov/pubmed/.

[5] Bunescu R,Mooney R,Ramani A,et al.Integrating co-occurrence statistics with information extraction for robust retrieval of protein interactions from Medline[C]//Proceedings of the workshop on linking natural language processing and biology:towards deeper biological literature analysis.[s.l.]:Association for Computational Linguistics,2006:49-56.

[6] Koike A,Kobayashi Y,Takagi T.Kinase pathway database:an integrated protein-kinase and NLP-based protein-interaction resource[J].Genome Research,2003,13(6a):1231-1243.

[7] 楊志豪,洪 莉,林鴻飛,等.基于支持向量機的生物醫學文獻蛋白質關系抽取[J].智能系統學報,2008,3(4):361-369.

[8] 崔寶今,林鴻飛,張 霄.基于半監督學習的蛋白質關系抽取研究[J].山東大學學報:工學版,2009,39(3):16-21.

[9] Grimes G R,Wen T Q,Mewissen M,et al.PDQ Wizard:automated prioritization and characterization of gene and protein lists using biomedical literature[J].Bioinformatics,2006,22(16):2055-2057.

[10] Fundel K,Küffner R,Zimmer R.RelEx-relation extraction using dependency parse trees[J].Bioinformatics,2007,23(3):365-371.

[11] Temkin J M,Gilder M R.Extraction of protein interaction information from unstructured text using a context-free grammar[J].Bioinformatics,2003,19(16):2046-2053.

[12] Qian W,Fu C,Cheng H.Semi-supervised method for extraction of protein-protein interactions using hybrid model[C]//Proceedings of the 2013 third international conference on intelligent system design and engineering applications.[s.l.]:IEEE Computer Society,2013:1268-1271.

[13] Niu Y,Otasek D,Jurisica I.Evaluation of linguistic features useful in extraction of interactions from PubMed;application to annotating known,high-throughput and predicted interactions in I2D[J].Bioinformatics,2010,26(1):111-119.

[14] Haussler D.Convolution kernels on discrete structures[R].Santa Cruz:University of California at Santa Cruz,1999.

[15] Lodhi H,Saunders C,Shawe-Taylor J,et al.Text classification using string kernels[J].Journal of Machine Learning Research,2002,2(3):419-444.

[16] Bunescu R C,Mooney R J.A shortest path dependency kernel for relation extraction[C]//Proceedings of the conference on human language technology and empirical methods in natural language processing.[s.l.]:Association for Computational Linguistics,2005:724-731.

[17] Niu Yun,Wang Yuwei.Protein-protein interaction identification using a hybrid model[J].Artificial Intelligence in Medicine,2015,64(3):185-193.

[18] Chang C C,Lin C J.LIBSVM:a library for support vector machines[J].ACM Transactions on Intelligent Systems and Technology,2011,2(3):1-27.

Identification of Protein-protein Interaction with Minimum Cuts

ZHANG Jing，WU Hong-mei，NIU Yun

(School of Computer Science and Technology,Nanjing University of Aeronautics and Astronautics,Nanjing 210016,China)

Protein-Protein Interaction (PPI) information is significant for biological and medical research,and is an important content in biomedicine field.The recognition of PPI with large-scale corpus can significantly reduce the cost of manual annotation by directly using the existing PPI database.Therefore,a method for PPI with Minimum Cuts based on the large-scale corpus has been proposed.Based on the framework of relational similarity,Minimum Cuts classifier not only uses SVM to predict the classification initially of a single protein,but also makes use of the similarity between the protein pairs to determine the results which are more accurate.The experimental results show that the Minimum Cuts classifier is better than the SVM classifier for the recognition of PPI.When the training data is 20%,the recognition results of the Minimum Cuts classifier gets better performance than that of an SVM classifier trained with 80%.

relational similarity;Minimum Cuts;SVM;protein-protein interaction

2016-07-20

2016-10-26 網絡出版時間：2017-04-28

國家自然科學基金資助項目(61202132)

張 景(1991-)，女，碩士研究生，研究方向為自然語言處理；牛 耘，博士，副教授，研究方向為自然語言處理。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170428.1703.074.html

TP391

A

1673-629X(2017)06-0017-05

10.3969/j.issn.1673-629X.2017.06.004