張 景，吳紅梅，牛 耘

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

基于Minimum Cuts的蛋白質(zhì)交互識別

張 景，吳紅梅，牛 耘

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

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

關(guān)系相似性;Minimum Cuts;支持向量機;蛋白質(zhì)交互

0 引 言

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

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

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

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

1 基于關(guān)系相似性的PPI識別

1.1 關(guān)系相似性

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

蛋白質(zhì)對交互關(guān)系的文本表達中存在相似性，表現(xiàn)在描述交互關(guān)系的句子在表達上是相似的，例如：

(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.

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

1.2 基于關(guān)系相似性的PPI識別描述

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

1.2.1 關(guān)系描述

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

1.2.2 關(guān)系表示

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

1.2.3 關(guān)系相似性計算

(1)

根據(jù)目標蛋白質(zhì)對與已知交互關(guān)系蛋白質(zhì)對的相似度，選擇合適的分類算法進行PPI識別。

2 基于Minimum Cuts的PPI識別

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

2.1 Minimum Cuts算法描述

首先，對目標分類問題建立無向圖G=(V,E)，源點s和匯點t表示C1和C2兩個目標類。圖中的節(jié)點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之間的關(guān)系，邊E(vi,s)的權(quán)重表示實例xi為C1類的概率大小，E(vi,t)的權(quán)重表示實例xi為C2類的概率大小。E(vi,vj)表示實例xi與xt之間是相似的，其權(quán)重表示兩實例之間的相似度，相似度越大權(quán)重越大，相似度越小權(quán)重越小。例如，圖1是一個Minimum Cuts分類器示意圖，s和t分別表示C1和C2類，Y表示訓練數(shù)據(jù)中屬于C1的實例，N表示訓練集中屬于C2的實例，M表示待標記的實例。虛線經(jīng)過的邊就是圖1的最小割，并將M與Y分為C1。

圖1 Minimum Cuts分類器

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

(2)

2.2 基于關(guān)系相似性的PPI識別與Minimum Cuts的聯(lián)系

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

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

因此，在關(guān)系相似性框架下，構(gòu)建Minimum Cuts分類模型，實現(xiàn)PPI識別。

2.3 構(gòu)建Minimum Cuts分類器

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

2.3.1 實例點與s、t之間邊的權(quán)重計算

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

將訓練集中有交互關(guān)系的點與s之間邊的權(quán)值設(shè)為100，與t之間邊的權(quán)值設(shè)為0.01。無交互關(guān)系的點與s之間的邊的權(quán)值設(shè)為0.01，與t之間的邊權(quán)值設(shè)為100。

2.3.2 實例點之間邊的權(quán)重計算

實例點之間的邊表示兩個蛋白質(zhì)對關(guān)系之間是相似的，兩個蛋白質(zhì)對關(guān)系相似度值越大，邊權(quán)重越大。根據(jù)表示蛋白質(zhì)對關(guān)系的特征向量，采用余弦距離計算任意兩個蛋白質(zhì)對之間的相似度，余弦值越大權(quán)重越大，兩個蛋白質(zhì)對越相似，相應(yīng)的實例點之間邊的權(quán)重也越大。

3 實 驗

3.1 實驗數(shù)據(jù)

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

3.2 實驗設(shè)置

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

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

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

3.3 實驗結(jié)果及分析

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

表1 基于監(jiān)督學習Minimum Cuts的識別結(jié)果 %

表2 基于SVM分類器的識別結(jié)果 %

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

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

圖2 有交互關(guān)系的蛋白質(zhì)識別結(jié)果的F值變化趨勢對比

圖3 無交互關(guān)系的蛋白質(zhì)識別結(jié)果的F值變化趨勢對比

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

4 結(jié)束語

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

[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] 楊志豪,洪 莉,林鴻飛,等.基于支持向量機的生物醫(yī)學文獻蛋白質(zhì)關(guān)系抽取[J].智能系統(tǒng)學報,2008,3(4):361-369.

[8] 崔寶今,林鴻飛,張 霄.基于半監(jiān)督學習的蛋白質(zhì)關(guān)系抽取研究[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 網(wǎng)絡(luò)出版時間：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