基于正負樣例的蛋白質功能預測

傅廣垣　余國先　王　峻　郭茂祖

1(西南大學計算機與信息科學學院　重慶　400715)2　　　(哈爾濱工業大學計算機科學與技術學院　哈爾濱　150001)

?

基于正負樣例的蛋白質功能預測

傅廣垣1余國先1王峻1郭茂祖2

1(西南大學計算機與信息科學學院重慶400715)2(哈爾濱工業大學計算機科學與技術學院哈爾濱150001)

(gxyu@swu.edu.cn)

蛋白質功能預測是后基因組時代生物信息學的核心問題之一.蛋白質功能標記數據庫通常僅提供蛋白質具有某個功能(正樣例)的信息,極少提供蛋白質不具有某個功能(負樣例)的信息.當前的蛋白質功能預測方法通常僅利用蛋白質正樣例,極少關注量少但富含信息的蛋白質負樣例.為此,提出一種基于正負樣例的蛋白質功能預測方法(protein function prediction using positive and negative examples, ProPN).ProPN首先通過構造一個有向符號混合圖描述已知的蛋白質與功能標記的正負關聯信息、蛋白質之間的互作信息和功能標記間的關聯關系,再通過符號混合圖上的標簽傳播算法預測蛋白質功能.在酵母菌、老鼠和人類蛋白質數據集上的實驗表明,ProPN不僅在預測已知部分功能標記蛋白質的負樣例任務上優于現有算法,在預測功能標記完全未知蛋白質的功能任務上也獲得了較其他相關方法更高的精度.

蛋白質功能預測;正樣例;負樣例;符號混合圖;標簽傳播

實驗發現蛋白質之間通過互作完成具體的生物學功能,這些互作的蛋白質構成互作網絡[2-3].基于蛋白質互作網(protein-protein interaction network, PPI)的功能預測方法將每個蛋白質看作一個網絡節點,節點之間的邊則描述蛋白質間的互作關系.Schwikowski等人[2]發現互作的蛋白質之間通常共享相同的功能,進而提出一種基于互作鄰居投票的功能預測方法.Chua等人[4]綜合利用蛋白質的直接互作和間接互作刻畫互作網絡的全局結構,提出一種功能相似性度量方法重新計算蛋白質之間的互作強度,再基于互作鄰居加權投票預測蛋白質功能.Deng等人[5]假設一個蛋白質的功能取決于與它直接互作的蛋白質,而與其他蛋白質無關,進而提出一類基于隨機Markov場的功能預測方法.Mostafavi等人[6]整合多源蛋白質互作網絡為一個復合網絡,再基于復合網絡預測蛋白質功能.

一個蛋白質通常參與到多個不同的生命過程中,具有多個功能,因而一個蛋白質通常標注有多個功能標記,上述方法均把功能預測問題當作二分類任務來處理,忽略了標記間的相關性.多標記學習能夠利用標記間的關聯性進而提高多標記對象的分類精度,近幾年被廣泛應用于蛋白質功能預測中[7-10].蛋白質的功能標記與基因本體有著密切的聯系.基因本體(gene pntology, GO)[11]作為基因及其產物(如蛋白質)功能標注的通用標準已被廣泛采用,它通過一個有向無環圖描述功能標記間的層次結構關系,圖中每個節點對應一種標記.標記間存在一個稱為True Path Rule規則,當已知蛋白質標注有某個功能時,該蛋白質也標注有該功能標記的祖先節點對應的功能,而當蛋白質不應該標注有某個功能時,蛋白質也不會標注該功能標記所有子孫節點的功能.由蛋白質功能標記間的層次結構關系和True Path Rule可知標記之間存在一定的關聯信息,Pandey等人[12]證實標記間的關聯性可以提高蛋白質功能預測的精度.Zhang等人[7]利用Jaccard系數計算成對功能標記間的關聯關系,再把這種關聯關系結合到一種半監督分類框架中[13],提出一種基于高斯隨機場的蛋白質功能預測方法(Gaussian random field, GRF).Wang等人[8]利用余弦函數和格林函數分別對標記之間的相關性和蛋白質之間的互作強度分別進行度量,提出一種基于功能相關性的多標記學習方法(function correlated multi-label learning, FCML)預測蛋白質功能.Yu等人[14]采用有向的雙關系圖模型描述蛋白質之間的互作信息,蛋白質的功能標記信息和標記之間的關聯關系,提出一種直推式多標記分類方法(transductive multi-label classi-fication, TMC)預測蛋白質功能.Chi等人[15]假定蛋白質的功能與蛋白質之間的特征相似度存在關聯,提出了一種基于余弦迭代(Cosine iterative algorithm, CIA)的蛋白質功能預測方法,每一次迭代CIA都將候選標記集中置信度最高的功能標記增量標注到待預測的蛋白質上,再基于蛋白質更新的功能標記集合重新計算蛋白質之間的相似度,如此迭代直至算法收斂或達到指定的迭代次數.Yu等人[16-17]通過綜合利用功能標記間的關聯性和多個蛋白質互作網絡,提出基于多核集成和多網絡對準的功能預測方法.

上述這些方法并沒有較好地處理蛋白質功能標記的不平衡和稀疏特性[18].截止2016-03-01,GO中已有超過50 000個功能標記,它們分布在3個不同分支:生物過程(biological process, BP)、細胞成分(cellular component, CC)和分子功能(molecular function, MF),每個分支均用一個有向無環圖描述功能標記間的層次結構關系.這些功能標記分布并不均衡,僅有少量功能標記被標注到成百上千個蛋白質,大部分標記被標注到的蛋白質個數都少于30.此外,一個蛋白質通常僅被標注了GO中幾個或者幾十個功能標記.因此從如此大量的候選功能標記集合中準確預測蛋白質功能非常困難.

由于蛋白質功能標記的開放世界假設(open world assumption)[19-20]特性,蛋白質功能標記數據通常僅提供蛋白質具有某個功能信息(正樣例),極少登記蛋白質不具有某個功能的信息(負樣例),原因是測定蛋白質所具有的全部功能非常困難,生物學家通常更關注蛋白質具有的功能.因此,蛋白質與大量功能標記的正負關聯性未知.當前的絕大部分蛋白質功能預測方法通常假設這些未知的關聯為蛋白質的負樣例,由于很多蛋白質已有的功能標記信息并不完整,存在缺失[18-23],這種假設降低了蛋白質功能預測的精度和覆蓋度.

大部分基于機器學習的蛋白質功能預測算法都需要一定量的蛋白質正負樣例作為訓練樣本,從而獲得具有較好判別性的蛋白質功能預測模型.Zhao等人[24]借助正樣例-無標記數據(positive-unlabeled data)[25]學習的思想,將標注有某個功能標記的蛋白質作為正樣例,未標注該功能標記但標注有其他功能標記的蛋白質作為未標記數據,再在訓練分類器的過程中從未標記數據中選擇負樣例,進而實現蛋白質功能預測.

一些學者近期的研究也證實了蛋白質負樣例在蛋白質功能預測中的重要性.Yu等人[26]發現在預測蛋白質缺失標記的過程中結合設定的負樣例,不僅可以減小預測問題的規模,還能極大地提高功能預測的精度.一些方法采用啟發式技巧預選一部分負樣例,再結合已有的正樣例預測蛋白質功能,并指明負樣例在提高功能預測精度方面發揮著重要作用.Guan等人[27]假定所有未標注有某個功能標記的蛋白質為該功能標記的負樣例,Mostafavi等人[6,28]和Cesa-Bianchi等人[29]將標注了某個功能標記但未標注該標記的兄弟標記的蛋白質作為該標記的負樣例.由于已有蛋白質的功能標記信息并不完整,蛋白質實際可能具有這些兄弟標記對應的功能,這些啟發式方法很容易選擇錯誤的負樣例.Youngs等人[30]提出了一種參數化貝葉斯先驗方法(ALBias)預測蛋白質的負樣例,該方法首先基于已有的蛋白質功能標記信息，計算當已知一個功能標記被標注到一個蛋白質上時,其他功能標記被標注在該蛋白質上的經驗條件概率,再結合一個蛋白質已有的功能標記集合匯總這些條件概率,選取概率最低的標記作為該蛋白質的負樣例,實驗證明這種方法選擇的負樣例可以提高功能預測精度.但是ALBias只利用了蛋白質功能標記數據庫中提供的每個蛋白質的直接功能標記信息,并未考慮標記間的層次結構關系,而已有研究發現標記間的結構關系在蛋白質功能預測中發揮著重要作用[18,31-33].Youngs等人[34]提出2種負樣例選擇方法SNOB(select negative via observed bias)和NETL(negative examples via topic likelihood).SNOB利用標記間的層次結構關系將一個蛋白質的直接功能標記的祖先標記增補到該蛋白質上,在此基礎上重新計算標記之間的條件概率,再利用類似ALBias的方式選擇負樣例.NETL方法將每個蛋白質看作一個文檔,所有標注到蛋白質的功能標記看作文檔中的單詞,然后利用LDA(latent Dirichlet allocation)[35]進行負樣例預測.

上述方法在預測負樣例的過程中,均基于蛋白質已有的正樣例和GO結構信息,并不能利用已有的少量的負樣例和蛋白質的其他特征信息,如蛋白質之間的互作和氨基酸序列信息等.當前,蛋白質功能標記數據庫中已累計登記了幾千個蛋白質負樣例,但數量遠小于正樣例的數量[36].在分析上述研究工作的基礎上,本文提出一種基于正負樣例的蛋白質功能預測方法(protein function prediction using positive and negative examples, ProPN).ProPN首先通過一個有向符號混合圖描述蛋白質之間的互作,蛋白質已有的正負樣例和標記間的關聯關系,再利用符號混合圖上的標簽傳播算法預測蛋白質功能.在3個不同物種(Yeast,Mouse和Human)蛋白質數據集上的實驗表明,本文提出的ProPN不僅能較其他相關方法更準確地預測蛋白質的負樣例,在蛋白質功能預測上也獲得較其他對比算法更高的精度.

1　基于正負樣例的蛋白質功能預測

1.1有向符號混合圖

基于蛋白質互作網的功能預測方法通常利用圖來描述蛋白質之間的互作信息,圖中每個節點對應一個蛋白質,節點間的連線描述節點間的互作,這類方法再將蛋白質已有正樣例作為隨機游走算子進行標簽傳播,預測蛋白質功能.雖然這種圖也可以進行蛋白質正負樣例的傳播預測,但它并不能描述和利用功能標記間的關聯信息.Wang等人[37]和Yu等人[14]設計的雙關系圖模型雖然能夠刻畫蛋白質正樣例和功能標記間的關聯信息,但仍無法描述和利用蛋白質負樣例信息.

為了充分描述和利用蛋白質互作信息、蛋白質正負樣例信息和功能標記間的關聯性,本文設計了一種如圖1所示的有向符號混合圖.

Fig. 1　Direct signed hybrid graph.圖1　有向符號混合圖示意圖

圖1中左側子圖中每個節點對應一個蛋白質,節點之間的連線描述蛋白質之間的互作,連線的粗細描述互作的強度(或置信度);右側子圖中每個節點對應一種功能標記,標記間的關聯用虛線描述,線的粗細描述關聯的大小;蛋白質與標記之間的正關聯信息用有向實線(+1)描述,它們之間的負關聯信息用有向虛線(-1)描述.為避免標簽傳播過程中標記被覆蓋的風險,與文獻[14]類似,本文的有向符號混合圖僅允許功能標記節點上的信息傳遞到蛋白質節點.本文將通過有向混合圖上的標簽傳播算法預測圖中未完整標注功能蛋白質(如1圖中P1,P2,P3和P4)的負樣例和功能信息完全未知蛋白質(如圖1中P5,P6和P7)的功能.值得注意的是本文的符號混合圖中邊的權重具有符號特性,而文獻[14,37]的雙關系圖僅包含權重為非負的邊,無符號特性.

1.2符號混合圖上的標簽傳播算法

(1)

其中,WPP∈N×N描述蛋白質之間互作狀況及其強度(或置信度),它由已有的蛋白質互作網絡直接初始化;WFP∈C×N描述功能標記與蛋白質的關聯關系,它可基于已有的蛋白質功能標記信息進行設置,當已知標記c為第i個蛋白質的正樣例時WFP(c,i)=1,當已知c為第i個蛋白質的負樣例時WFP(c,i)=-1,而當c與第i個蛋白質的關聯信息未知時WFP(c,i)=0.由于圖1為一個有向混合圖,所以W的右上角的矩陣為一個大小為N×C的全0矩陣.WFF∈C×C描述功能標記間的關聯關系,與文獻[8,14]中的方法類似,本文基于成對功能標記共同標注在同一個蛋白質上的情況對其進行如下設置:

(2)

令Y=[Y1,Y2,…,YC],其中Yc∈N+C,描述第c個功能標記與N個蛋白質節點和C個功能節點的關聯關系,具體定義如下:

(3)

(4)

在上述初始化和設置的基礎上,與文獻[38]中局部與全局一致性學習的目標方程類似,本文定義圖1中有向符號混合圖上的標簽傳播目標方程為

(5)

f(i)∈C為預測的第i個節點與C個功能標記節點的關聯性大小,Y(i)∈C表示第i個節點與C個功能標記節點的初始關聯大小,D∈(N+C)×(N+C)為對角矩陣,其對角元素為,η>0用于調整式(5)中等號右側第1項和第2項的權重.sgn(Wi j)為符號函數,當Wi j>0時取1,當Wi j<0時取-1.式(5)中等號右側第1項為經驗損失項,最小化該項的目的是促使預測的f(i)與已知的Y(i)保持一致.式(5)中右側第2項為平滑性損失項,該項可細分為3種情況分別討論:

1) 當i和j均為蛋白質節點時,Wi j≥0描述它們之間的互作強度(或氨基酸序列相似度等),當Wi j值較大時,最小化平滑損失項可以促使f(i)和f(j)與C個功能標記的關聯性大小彼此靠近.

2) 當i為蛋白質節點而j為標記節點時,Wi j∈{-1,+1},其中Wi j=-1表示j為i的負樣例,Wi j=1表示j為i的正樣例,f(j)≥0描述標記j與C個標記節點的關聯關系大小.若sgn(Wi j)=-1,最小化平滑損失項促使f(i)向-f(j)的靠近,而當sgn(Wi j)=1時會使f(i)向f(j)靠近,因此sgn(Wi j)可以保持并利用蛋白質正樣例和負樣例.

3) 當i和j均為功能標記節點時,Wi j≥0描述它們之間的關聯大小,最小化平滑損失項可以促使f(i)與f(j)在C個功能標記節點上關聯大小彼此靠近.當已知一個蛋白質與i正關聯時,由于Wi j>0蛋白質也可能與j正關聯;類似地,當一個蛋白質與i負關聯時該蛋白質與j也可能負關聯,這種設置有助于利用標記間的關聯性.

綜上所述,通過最小化式(5)可以預測已知部分功能標記蛋白質的負樣例以及對完全未標注功能蛋白質的功能預測.

(6)

其中,tr()為求矩陣的跡,I是與S同型的單位矩陣,S是有向符號混合圖W中各子圖分別歸一化的后關聯矩陣,其定義如下:

(7)

其中:

(8)

(9)

(10)

DPP和DFF均為對角矩陣,它們的對角元素值分別為|WPP|和|WFF|行(或列)和.DP∈N×N和DF∈C×C也為對角矩陣,它們的對角元素值分別對應|WFP|的列和與行和.

對式(6)求關于f的導數可得:

(11)

(12)

由此可得f*的顯示解如下:

(13)

令α=1(1+η),則(1-α)=η(1+η),與文獻[37]類似,式(11)可以轉化為一個顯式的迭代標簽傳播目標方程:

(14)

f(i)t∈C是第t次迭代時預測的第i個節點與C個功能標記的關聯度大小,α用于平衡蛋白質i與功能標記的初始關聯信息和其他節點傳遞給i的標記信息,α值越大說明其他節點傳遞的信息對f(i)影響越大.

令f0=Y,式(14)可以改寫成如下的目標方程:

(15)

由于|αS(i,j)|<1,當t→+∞時式(15)中等號右側第1項的極限為0、第2項為收斂的等比數列,其極限為(1-α)(I-αS)-1Y.在此基礎上,可得式(14)的顯式解如下:

f=(1-α)(I-αS)-1Y,

(16)

2　實　　驗

2.1數據集

本文下載了2016-02-21的GO數據庫*http://geneontology.org,GO數據庫描述了功能標記間的層次結構關系.這些標記分布在3個不相交的分支,分別是BP,MF和CC.與以往實驗類似,本文剔除了GO中標注為“obsolete”的功能標記.本文采用Mostafavi等人[6]提供的Yeast,Human和Mouse蛋白質數據集,每個數據集中都包含了多個功能關聯網絡,本文將這些網絡等權重合并為一個復合互作網絡.本文同時也下載上述物種的功能標記數據*http://geneontology.org//page//download-annotations,這些標記數據提供了該物種當前已知的蛋白質的直接功能標記信息.為避免循環預測問題,本文剔除了證據屬性(Evidence Code)為IEA(inferred from electronic annotation)的蛋白質功能標記.在此基礎上,本文利用GO中的True Path Rule對蛋白質功能標記數據進行增補,將蛋白質正樣例對應的標記節點的祖先節點標記也標注到相應的蛋白質上,蛋白質負樣例對應標記節點的子孫節點也設定為相應蛋白質的負樣例.

表1列出了上述3個數據集的統計信息,可以發現,蛋白質的正樣例數量遠大于其負樣例的數量,少量的蛋白質直接負樣例通過True Path Rule進行了一定的增補,每個物種的蛋白質均被上千個不同的功能標記所標注,其中Human在BP分支中的功能標記種類還大于其蛋白質數量.

Table1　Dataset Statistics表1　實驗數據集統計信息

Note: Avg±Std is the average number of functions per protein and the standard deviation.

2.2對比方法與評價度量

本文實驗分為2部分,預測已標注部分功能標記蛋白質的負樣例和預測功能信息完全未知蛋白質的功能.

在負樣例預測實驗中本文選取當前最新的SNOB[34],ALBias[30]及基準方法Random作為ProPN的對比方法.Youngs等人實驗驗證SNOB比NETL效果更好[34],也優于啟發式方法[6]和正樣例無標記數據學習方法[24],所以本文沒有采用這些方法作為對比方法.對于一個給定的功能c,ALBias對其作為蛋白質i負樣例的關聯性大小計算方式如下:

(17)

其中,Ai為蛋白質功能標記數據庫中第i個蛋白質的直接功能標記集合,p(c|c′)表示經驗條件概率:

(18)

在對功能信息完全未知的蛋白質進行功能預測的實驗中,本文選取CIA[15],FCML[8],GRF[7],TMC[14]和Na?ve[1]作為ProPN的對比方法,前面4個方法在本文的引言中已經介紹,第5個方法Na?ve是國際大規模蛋白質功能預測算法評測競賽(critical assessment of protein function annotation algorithms, CAFA)中推薦的基準方法[1],Na?ve基于功能標記出現在N個蛋白質上的頻率進行預測,蛋白質標注某個功能標記的概率正比例于該標記的頻率.在本部分實驗中本文選取4個常用的評價度量MacroF1,MicroF1,Fmax和RankLoss評估上述蛋白質功能預測算法的性能.MicroF1將不同標記上的預測結果看作整體,求取全局的F1-Score作為評估結果,MicroF1更傾向頻率高的標記.MacroF1是另外一種以標記為中心的評價度量,它求取每個功能標記的F1-Score,再基于這些標記F1-Score的均值評估預測性能,與MicroF1不同,MacroF1傾向頻率低的標記.Fmax是CAFA推薦的一種以蛋白質為中心的評價準則[1],它基于全局準確率和查準率對應的F1分數的最大值評估預測性能. RankLoss是另外一種以蛋白質為中心的評價度量,它以每個蛋白質預測錯誤的功能標記排在正確標記前面的平均概率作為評價指標,顯然RankLoss越低越好.為了保持與其他評價度量的一致性,本文實驗中使用1-RankLoss作為評價度量,因此算法在上述4個度量上的值越高表明算法的預測性能越好.從這些評價度量的定義可知這些度量從不同的角度評估蛋白質功能預測的性能,一個算法很難在這些度量上均超過其他對比算法,關于這些度量的形式化定義可以參見文獻[1,10,16].MicroF1和MacroF1需要將預測關聯向量fP∈N×C轉換成0-1的標記矩陣,與文獻[7,14]類似,本文選取每個蛋白質對應預測關聯向量中最大的K個元素對應的標記為該蛋白質的功能標記.K為數據集中每個蛋白質正樣例的平均個數,例如在Human數據集的CC分支下,每個蛋白質平均標注有19.12個標記,則K=20.

2.3蛋白質負樣例預測

ProPN利用2013年蛋白質功能標記數據設置蛋白質與功能標記之間的關聯邊,若已知一個蛋白質的正樣例,則在該蛋白質與相關標記及其祖先標記之間設置權重為1的正關聯邊,若已知一個蛋白質負樣例,則在該蛋白質與相關標記及其子孫標記之間設置權重為-1的負關聯邊.基于符號混合圖上的標簽傳播算法得到N個蛋白質與C個功能標記的關聯性大小矩陣fP∈N×C,參照SNOB和ALBias中的負樣例選擇與評價方法,本文通過對fP中全部N×C個元素按從小到大的順序排序,選取前m個最小值對應的元素為N個蛋白質的負樣例.然后基于2016年更新的蛋白質功能標記數據,統計m個預測的負樣例中假陰性的數量FNs.對比算法ALBias,SNOB和Random同樣也基于2013年的蛋白質功能標記數據進行負樣例預測,再基于2016年的蛋白質功能標記數據統計各自產生的FNs.這些算法在不同的m下各自的FNs如表2～4所示：

Table 2　Number of False Negative Predictions on Yeast Genome表2　Yeast數據集不同統計數量下的假陰性個數

Table 3　Number of False Negative Predictions on Human Genome表3　Human數據集不同統計數量下的假陰性個數

Table 4　Number of False Negative Predictions on Mouse Genome表4　Mouse數據集不同統計數量下的假陰性個數

從這3個表中的實驗結果不難發現,本文提出的ProPN在絕大部分實驗設置下都比其他對比算法精度高.以Yeast數據集BP分支上的實驗為例,在m=80 k的情況下,ProPN有6個假陰性預測,SNOB有38個,ALBias有427個,而Random約有95.2個.上述實驗結果證明了ProPN能夠較當前負樣例選擇預測方法更準確地預測蛋白質的負樣例.

SNOB通過True Path Rule補充了蛋白質的功能標記,在一定程度上利用標記間的層次結構關系,但它只在蛋白質正樣例的基礎上計算標記之間的經驗條件概率,忽略了數量極少但信息豐富的蛋白質負樣例,此外它沒有考慮蛋白質之間的互作關系,因此它預測的FNs比ProPN多.ProPN同時考慮了蛋白質的正負樣例和蛋白質的互作信息,預測的FNs較SNOB更少,這些實驗結果表明結合蛋白質已有的負樣例和其他特征信息進行負樣例預測是有效的,也證明了利用有向符號混合圖對上述信息進行描述和利用的必要性.

ALBias只利用了功能標記數據中提供的直接功能標記信息,對標記間層次結構關系的利用有限.與SNOB類似,ALBias也沒有考慮蛋白質的互作信息和負樣例,所以它在很多情況下預測的FNs比SNOB和ProPN多,這表明利用標記間的關系可以提高負樣例的預測精度.ALBias在一些實驗設置下較其他對比算法產生更少的FNs,原因是它通過λ和γ對蛋白質的缺失標記和標記不平衡進行了平滑處理.這說明在蛋白質的負樣例預測任務中需考慮蛋白質功能標記信息的缺失情況,這也是本文后續研究工作之一.

Random僅基于標記出現的頻率預測蛋白質的負樣例,但它有時產生的FNs比SNOB和ALBias要少.原因是該方法并不是真正的隨機選定功能標記為蛋白質的負樣例,由于標記的層次結構特性,出現頻率最低的標記最有可能預測為相關蛋白質的負樣例,而這類負樣例在新近的蛋白質功能標記數據中更難被驗證.實際上ALBias和SNOB也偏向預測頻率低的標記作為蛋白質負樣例.

不同于這3個對比方法,ProPN通過有向符號混合圖對蛋白質互作信息、已有蛋白質的正負樣例和標記關聯性進行描述和利用,在一定程度上避免了蛋白質功能標記的缺失性和不平衡性的影響,因此預測的負樣例中FNs在絕大多數情況下均少于其他對比算法.

2.4蛋白質功能預測

在功能信息完全未知的蛋白質功能預測實驗中,本文利用Yeast,Human和Mouse這3個物種蛋白質的2016年功能標記數據,隨機將每個數據集劃分為2部分,其中一部分蛋白質(占70%)被作為訓練樣本,剩余的蛋白質用作為測試樣本.測試樣本的功能標記在訓練和預測過程中視為未知,僅在評測試階段用于評估算法的性能.為避免隨機性,本文對每個算法都獨立重復10次,每次獨立實驗中均對訓練樣本和測試樣本做一次隨機劃分,再報告這10次實驗的平均結果和方差.Myers等人[39]認為標注到極少量蛋白質的功能標記無法在濕實驗中測定,與其他對比方法[7,8,14]中的實驗設置類似,本文過濾掉標注的蛋白質數量少于10的功能標記,過濾后3個數據集中每個蛋白質的功能標記情況見表1中最后一列.表5～7分別報告了各蛋白質功能預測算法在Yeast,Human和Mouse上的實驗結果,3個表中加粗的實驗結果為在95%置信度下成對t檢驗下最優的結果.在本部分實驗中,為了提高有向符號混合圖中節點間信息傳播的速率,ProPN中的α和β分別設置為0.9和0.1,其他對比算法的參數設置采用原文作者推薦的方法進行設置.由于評價度量MacroF1和MicroF1需顯式的將fP∈N×C轉化為0-1矩陣,參照TMC和GRF等對比方法的實驗方案,在蛋白質功能預測實驗中,本文選取fP中每一行最大的K個元素對應的標記為該蛋白質的正樣例,K為訓練樣本中每個蛋白質平均的正樣例個數.1-RankLoss和Fmax不需要顯示地將fP轉化為0-1矩陣,它們直接基于fP進行計算.

Table 5　Results on Yeast with Respect to Different Evaluation Metrics表5　Yeast數據集蛋白質功能預測評估結果

Table 6　Results on Human with Respect to Different Evaluation Metrics表6　Human數據集蛋白質功能預測評估結果

Table 7　Results on Mouse with Respect to Different Evaluation Metrics表7　Mouse數據集蛋白質功能預測評估結果

從表5～7中我們可以看到ProPN在絕大多數情況下均獲得較這些對比算法更好的預測結果.具體地在本文36種(3種數據集×3個GO分支×4種評價度量)實驗對比中,ProPN分別在72.2%, 86.1%和91.7%情況下顯著性優于GRF,Na?ve和FCML;ProPN在8.3%, 0%, 2.7%情況下獲得與這3個對比方法類似的結果;ProPN在19.4%, 13.9%, 5.6%情況下比這3個方法差;ProPN總是獲得較TMC和CIA更好的實驗結果.

TMC和ProPN均能描述和利用蛋白質的互作信息,蛋白質與標記間的關聯信息和標記間的關聯關系,但ProPN的預測精度遠高于TMC.原因是ProPN考慮了蛋白質的負樣例并基于符號混合圖對負樣例信息進行了描述和利用,而TMC采用的有向雙關系圖無法對負樣例進行描述和利用.ProPN與TMC預測結果的差異性也證實了負樣例在蛋白質功能預測中的幫助作用.GRF與ProPN之間的預測結果差異最小,原因是GRF也利用了蛋白質之間的互作信息,標記間關聯關系和與式(5)類似的目標方程預測蛋白質功能,但由于它沒有利用蛋白質的負樣例,所以它的精度通常低于ProPN.FCML也利用了標記之間的關聯關系和蛋白質互作網,它有時獲得與ProPN和GRF類似的結果,原因是它在蛋白質互作網對應的權重鄰接矩陣上應用格林方程[8],在一定程度上降低了蛋白質噪聲互作的干擾.這表明蛋白質之間互作信息的質量影響著基于互作網絡的蛋白質功能預測算法的精度.雖然CIA也利用了蛋白質互作網進行功能預測,但它沒有顯式地考慮標記之間的關聯性,因此其預測精度通常遠低于上述對比算法.Na?ve僅基于標記出現的頻率預測蛋白質功能,它在4個評價度量上有時獲得比其他對比算法更高的結果,特別是在MicroF1和1-RankLoss度量上,這種結果也與文獻[1]中的結果類似.原因之一是功能標記的不平衡性和標記間的層次結構關系,高頻率標記標注到蛋白質的概率更高,另一個原因是MicroF1更偏向頻率高的標記.上述實驗結果和分析證明本文提出的ProPN能夠綜合利用蛋白質的互作信息、標記間關聯關系和蛋白質的正負樣例,所以它獲得較其他對比算法更高的預測結果.

2.5算法運行時間分析

為了分析各個對比算法的效率,與2.4節的實驗設置類似,本文記錄了5個對比方法(基線方法Na?ve除外)各自的運行時間(算法評價度量除外),表8中報告的時間為算法5次獨立運行的平均時間.這些方法均基于Matlab2011b(64 b)編碼實現,實驗運行平臺配置為: Linux OS 3.13.0, AMD Opteron 6367, 64 GB RAM.

Table 8　Runtime Costs表8　運行時間　s

從式(12)可知圖上標簽傳播算法的時間復雜度為O(N3),其中N為圖中節點的個數,因此GRF和FCML的時間復雜度均為O(N3).由于ProPN和TMC采用的圖中節點個數為N+C,所以其時間復雜度為O((N+C)3).CIA采用一種類似投票的機制預測蛋白質功能,但由于它需要多次迭代,每次迭代中都要重新計算N蛋白質之間的相似度大小和每個標記的局部和全局得分信息,因此其時間復雜度為O(tN2C),t為迭代次數.從表8也可以發現ProPN和TMC的時間耗費彼此接近,均大于GRF而又小于FCML和CIA,這是因為蛋白質互作網和蛋白質與功能標記的關聯矩陣均為稀疏矩陣.FCML由于需要對蛋白質互作網對應的權重關聯矩陣進行本征值分解,非常耗時,所以其真實時間耗費遠大于其他算法,CIA由于需要多次迭代,每次迭代增量地更新蛋白質的功能標記集合和重新計算蛋白質之間的相似度,所以其時間耗費比較大.上述實驗結果表明本文提出的ProPN不僅能較其他對比算法更準確地預測蛋白質功能,還能保持較高的效率.

3　結束語

本文將蛋白質的正負樣例信息和蛋白質的互作信息綜合應用于蛋白質功能預測當中,獲得了較其他相關算法更好的預測效果,得到了若干有指導意義的結論.與現有蛋白質功能預測方法相比,本文不僅利用了蛋白質與功能標記的正關聯信息,還利用了其中為數不多但富含信息的蛋白質與功能標記的負關聯信息,為后續蛋白質功能預測方法的研究提供了新的思路.如何有效預測蛋白質負樣例并結合負樣例到蛋白質功能預測任務中、如何對蛋白質的潛在缺失標記進行建模均是值得深入研究的問題.此外,蛋白質互作網絡質量和標記之間的關聯性度量也影響著ProPN的性能,如何克服互作網中的噪聲互作、如何更準確地描述功能標記間的關聯關系都有待進一步研究.ProPN算法的matlab代碼和部分采用的數據集可在www.scholat.comteammlda下載.

[1]Radivojac P, Clark W, Oron T, et al. A large-scale evaluation of computational protein function prediction[J]. Nature Methods, 2013, 10(3): 221-227

[2]Schwikowski B, Uetz P, Field S. A network of protein-protein interactions in yeast[J]. Nature Biotechnology, 2000, 18(12): 1257-1261

[3]Guo Maozu, Dai Qiguo, Xu Liqiu, et al. On protein complexes identifying algorithm based on the novel modularity function[J]. Journal of Computer Research and Development, 2014, 51(10):2178-2186 (in Chinese)

(郭茂祖, 代啟國, 徐立秋, 等. 一種蛋白質復合體模塊度函數及其識別算法[J]. 計算機研究與發展, 2014, 51(10): 2178-2186)

[4]Chua H, Sung W, Wong L. Exploiting indirect neighbours and topological weight to predict protein function from protein-protein interactions[J]. Bioinformatics, 2006, 22(13): 1623-1630

[5]Deng M, Tu Z, Sun F, et al. Mapping Gene Ontology to proteins based on protein-protein interaction data[J]. Bioinformatics, 2004, 20(6): 895-902

[6]Mostafavi S, Morris O. Fast integration of heterogeneous data sources for predicting gene function with limited annotation[J]. Bioinformatics, 2010, 26(14): 1759-1765

[7]Zhang X, Dai D. A framework for incorporating functional interrelationships into protein function prediction algorithms[J]. IEEE//ACM Trans on Computational Biology and Bioinformatics, 2012, 9(3): 740-753

[8]Wang H, Huang H, Ding C. Function-function correlated multi-label protein function prediction over interaction networks[J]. Journal of Computational Biology, 2013, 20(4): 322-343

[9]Wu J, Huang S, Zhou Z. Genome-wide protein function prediction through multi-instance multi-label learning[J]. IEEE//ACM Trans on Computational Biology and Bioinformatics, 2014, 11(5): 891-902

[10]Zhang M, Zhou Z. A review on multi-label learning algorithms[J]. IEEE Trans on Knowledge & Data Engineering, 2014, 26(8): 1819-1837

[11]Ashburner M, Ball C A, Blake J A, et al. Gene ontology: tool for the unification of biology[J]. Nature Genetics, 2000, 25(1): 25-29

[12]Pandey G, Myers C, Kumar V. Incorporating functional inter-relationships into protein function prediction algorithms[J]. BMC Bioinformatics, 2009, 10: No.142

[13]Belkin M, Niyogi P, Sindhwani V. Manifold regularization: A geometric framework for learning from labeled and unlabeled examples[J]. Journal of Machine Learning Research, 2006, 7(1): 2399-2434

[14]Yu G, Domeniconi C, Rangwala H, et al. Transductive multi-label ensemble classification for protein function prediction[C] //Proc of 18th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2012: 1077-1085

[15]Chi X, Hou J. An iterative approach of protein function prediction[J]. BMC Bioinformatics, 2011, 12: No.437

[16]Yu G, Rangwala H, Domeniconi C, et al. Predicting protein function using multiple kernels[J]. IEEE//ACM Trans on Computational Biology and Bioinformatics, 2015, 12(1): 219-233

[17]Yu G, Zhu H, Domeniconi C, et al. Integrating multiple networks for protein function prediction[J]. BMC Systems Biology, 2015, 9(S1): S3

[18]Tao Y, Sam L, Li J, et al. Information theory applied to the sparse gene ontology annotation network to predict novel gene function[J]. Bioinformatics, 2007, 23(13): i529-i538

[19]Rhee S, Wood V, Dolinski K, et al. Use and misuse of the gene ontology annotations[J]. Nature Review Genetics, 2008, 9(7): 509-515

[20]Schnoes M, Ream D, Thorman A, et al. Biases in the experimental annotations of protein function and their effect on our understanding of protein function space[J]. PLoS Computational Biology, 2013, 9(5): No.e1003063

[21]Yu G, Zhu H, Domeniconi C, et al. Predicting protein function via downward random walks on a gene ontology[J]. BMC Bioinformatics, 2015, 16: No.273

[22]Legrain P, Aebersold R, Archakov A, et al. The human proteome project: current state and future direction[J]. Molecular and Cellular Proteomics, 2011, 10(7): M111.00999

[23]Gao Lei, Li Xia, Guo Zheng, et al. Broadly predicting specific protein functions with protein-protein interactions and gene expression profiles[J]. China Science: Life Science, 2006, 36(5): 441-450 (in Chinese)

(高磊, 李霞, 郭政,等. 結合蛋白質互作與基因表達譜信息大范圍預測蛋白質的精細功能[J]. 中國科學: 生命科學, 2006, 36(5): 441-450)

[24]Zhao X, Wang Y, Chen L, et al. Gene function prediction using labeled and unlabeled data[J]. BMC Bioinformatics, 2008, 9: No.57

[25]Elkan C, Noto K. Learning classifiers from only positive and unlabeled data[C] //Proc of the 14th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2008: 213-220

[26]Yu G, Rangwala H, Domeniconi C, et al. Protein function prediction with incomplete annotations[J]. IEEE//ACM Trans on Computational Biology and Bioinformatics, 2014, 11(3): 579-591

[27]Guan Y, Myers C, Hess D, et al. Predicting gene function in a hierarchical context with an ensemble of classifiers[J]. Genome Biology, 2008, 9(S1): S3

[28]Mostafavi S, Ray D, Warde-Farley D, et al. GeneMANIA: A real-time multiple association network integration algorithm for predicting gene function[J]. Genome Biology, 2008, 9(S1): S4

[29]Cesa-Bianchi N, Re M, Valentini G. Synergy of multi-label hierarchical ensembles, data fusion, and cost-sensitive methods for gene functional inference[J]. Machine Learning, 2012, 88(1//2): 209-241

[30]Youngs N, Duncan P, Kevin D, et al. Parametric Bayesian priors and better choice of negative examples improve protein function prediction[J]. Bioinformatics, 2013, 29(9): 1190-1198

[31]Yu G, Zhu H, Domeniconi C. Predicting protein function using incomplete hierarchical labels[J]. BMC Bioinformatics, 2015, 16: No.1

[32]Pena-Castillo L, Tasan M, Myers C, et al. A critical assessment of mus musculus gene function prediction using integrated genomic evidence[J]. Genome Biology, 2008, 9(S1): S2

[33]Valentini G. True path rule hierarchical ensembles for genome-wide gene function prediction[J]. IEEE//ACM Trans on Computational Biology and Bioinformatics, 2011, 8(3): 832-547

[34]Youngs N, Penfold-Brown D, Bonneau R, et al. Negative example selection for protein function prediction: the NoGO database[J]. PLoS Computational Biology, 2014, 10(6): e1003644

[35]Blei D, Ng A, Jordan M. Latent dirichlet allocation[J]. Journal of Machine Learning Research, 2003, 3: 993-1022

[36]Huntley R, Sawford T, Martin M, et al. Understanding how and why the Gene Ontology and its annotations evolve: the GO within UniProt[J]. GigaScience, 2014, 3: No.4

[37]Wang H, Huang H, Ding C. Image annotation using bi-relational graph of images and semantic labels[C] //Proc of the 24th IEEE Conf on Computer Vision and Pattern Recognition. Piscataway, NJ: IEEE, 2011: 793-800

[38]Zhou D, Bousquet O, Lal T, et al. Learning with local and global consistency[C] //Advance in Neural Information Processing Systems. Cambridge, MA: MIT Press, 2003: 321-328

[39]Myers C, Barrett D, Hibbs M, et al. Finding function: evaluation methods for functional genomic data[J]. BMC Genomics, 2006, 7(1): No.187

Fu Guangyuan, born in 1993. Master. Student member of China Computer Federation. His main research interests include machine learning and bioinfor-matics.

Yu Guoxian, born in 1985. Associated professor. Member of China Computer Federation. His main research interests include machine learning, data mining and bioinformatics (gxyu@swu.edu.cn).

Wang Jun, born in 1983. Associated professor. Member of China Computer Federation. Her main research interests include data mining and bioinformatics (kingjun@swu.edu.cn).

Guo Maozu, born in 1966. Professor, PhD supervisor. Member of China Computer Federation. His main research interests include machine learning, data mining and bioinformatics (maozuguo@hit.edu.cn).

Protein Function Prediction Using Positive and Negative Examples

Fu Guangyuan1, Yu Guoxian1, Wang Jun1, and Guo Maozu2

1(CollegeofComputerandInformationScience,SouthwestUniversity,Chongqing400715)2(SchoolofComputerScienceandTechnology,HarbinInstituteofTechnology,Harbin150001)

Predicting protein function is one of the key challenges in the post genome era. Functional annotation databases of proteins mainly provide the knowledge of positive examples that proteins carrying out a given function, and rarely record the knowledge of negative examples that proteins not carrying out a given function. Current computational models almost only focus on utilizing the positive examples for function prediction and seldom pay attention to these scarce but informative negative examples. It is well recognized that both positive and negative examples should be used to achieve a discriminative predictor. Motivated by this recognition, in this paper, we propose a protein function prediction approach using positive and negative examples (ProPN) to bridge this gap. ProPN first utilizes a direct signed hybrid graph to describe the positive examples, negative examples, interactions between proteins and correlations between functions; and then it employs label propagation on the graph to predict protein function. The experimental results on several public available proteomic datasets demonstrate that ProPN not only makes better performance in predicting negative examples of proteins whose functional annotations are partially known than state-of-the-art algorithms, but also performs better than other related approaches in predicting functions of proteins whose functional annotations are completely unknown.

protein function prediction; positive examples; negative examples; signed hybrid graph; label propagation

2016-03-21；

2016-05-25

國家自然科學基金項目(61402378,61571163,61532014);重慶市基礎與前沿研究項目(cstc2014jcyjA40031,cstc2016jcyjA0351);重慶市研究生科研創新項目(CYS16070);中央高校基本科研業務費基金項目(2362015XK07,XDJK2016B009,XDJK2016D021)

余國先(gxyu@swu.edu.cn)

TP391

This work was supported by the National Natural Science Foundation of China (61402378,61571163,61532014), the Natural Science Foundation of CQ CSTC (cstc2014jcyjA40031,cstc2016jcyjA0351), Chongqing Research Innovation Fund for Graduate (CYS16070), and the Fundamental Research Funds for the Central Universities of China (2362015XK07,XDJK2016B009,XDJK2016D021).