基于布爾矩陣分解的蛋白質功能預測框架

劉 琳 唐 麟 唐明靖 周 維

1(云南師范大學信息學院 昆明 650500)2(民族教育信息化教育部重點實驗室(云南師范大學) 昆明 650500)3(云南師范大學校長辦公室 昆明 650500)4(云南大學國家示范性軟件學院 昆明 650091)

蛋白質(protein)是組成生命體一切細胞、組織的基本有機物，是生命活動的主要承擔者.根據遺傳學中心法則，基因在經過轉錄和翻譯之后才能由蛋白質在各種生命活動中執行其功能.因此，在大規模水平上對蛋白質的結構及功能進行研究的蛋白質組學對于闡明生命現象的本質和活動規律具有重要的意義，也是后基因組時代生命科學研究的核心內容之一.當前，蛋白質組學研究的一個重要內容就是對蛋白質進行功能注釋.然而傳統基于生物實驗的蛋白質功能注釋方法費時費力，無力填補基因組測序技術所獲得的大量蛋白質與其功能之間的鴻溝.近年來，越來越多的生物信息學研究者利用蛋白質序列數據、基因表達數據、系統發生譜等各種類型的生物數據，針對數據特點建立相應的計算模型以完成蛋白質功能的自動注釋.這類基于計算模型的蛋白質功能預測方法可以大大節省蛋白質功能注釋的時間和人力消耗，因此已成為目前蛋白質組學中的一個研究熱點.

從計算模型的角度看，該領域的研究大致可分為兩大類：基于分類的方法和基于網絡的方法.1)基于分類的蛋白質功能預測方法是將蛋白質看作需要分類的實例，而將注釋蛋白質的功能術語看作類別標簽，功能術語可由FunCat(funcat category)[1]和基因本體(gene ontology, GO)[2]所定義，與功能相關的各種生物數據轉換為蛋白質的特征，最后利用各種多標簽分類器的訓練和測試來完成蛋白質功能標簽預測.2)基于網絡的蛋白質功能預測方法是通過網絡中節點的距離來衡量蛋白質功能的相似度，可以基于蛋白質的功能關聯性或蛋白質相互作用網絡構建出以蛋白質為節點的網絡表達[3-5].

在基于分類的蛋白質功能預測研究中，很多傳統的多標簽分類方法如支持向量機 (support vector machine, SVM)、神經網絡和決策樹等[6-10]已取得較好的預測效果.但同時，我們的大量前期研究表明：與普通的分類場景相比，蛋白質功能預測中功能注釋標簽數量非常龐大，如僅在文獻[8]的D1數據集中就包含了4 133個GO術語.換句話說，處理蛋白質功能預測數據集的算法所面對的不再是幾個或幾十個標簽，而是成百上千的大規模標簽，這會直接導致計算模型的訓練時間非常長.特別是對于一些傳統的多標簽分類算法，根本無法處理大規模標簽分類問題，例如BR(binary relevance)方法不可用在具有104個標簽的多標簽分類問題中，因為這意味著它需要訓練104個二值分類器.同時，已有研究表明：面對這種大量標簽的多標簽分類數據集，SVMs等判別式模型的分類性能會急劇下降[11].

此外，由于蛋白質功能標簽之間均具有層次結構，顯然被低層功能標簽注釋的蛋白質數量會比高層功能標簽注釋的蛋白質數量少很多，這種標簽的標注樣本頻率極度不平衡的情況會直接導致分類效果不佳.圖1展示了對D1數據集[8]中功能標簽標注頻率的統計結果.從圖1中可以看出，大量的功能標簽注釋了非常少的蛋白質，僅僅有較少的功能標簽注釋了超過30個蛋白質.

Fig. 1 The number statistics of function labels annotated protein in protein function annotation dataset圖1 蛋白質功能注釋數據集中標簽注釋樣本頻率示意圖

面對蛋白質功能標簽數據的這一特點，目前蛋白質功能預測方法的研究是采取一種只對低維標簽空間分類的策略.這些研究通過一定的規則首先從標簽集中選擇出一個小規模的標簽子集，然后算法僅針對小規模性的標簽子集進行訓練和預測，而并不是直接面對高維標簽空間進行分類.如Yu等人[6]使用文獻[12]中的標準蛋白質數據集，這一數據集是通過GO進行生物功能注釋，研究者對其中的酵母數據過濾出注釋了至少100個蛋白質且最多300個蛋白質的GO功能標簽，對人類和小鼠數據過濾出注釋了至少30個蛋白質且最多100個蛋白質的GO功能標簽.最后，酵母數據中保留的功能標簽數量為57個，人類數據保留了254個功能標簽，小鼠數據保留了239個標簽，繼而預測模型只對這些少量的標簽進行處理.Xiong等人[13]使用有益功能類[14]的概念來選擇GO標簽，一個有益GO標簽是指：1)至少注釋了30個蛋白質；2)沒有任何孩子標簽注釋至少30個蛋白質.最后，該研究在酵母數據集中獲得了66個有益的GO標簽，并且在小鼠注釋數據集中獲得了130個有益GO term，同樣預測模型也僅對有益GO標簽進行預測.顯然，以上這些方式可以大大減少分類器所面對的標簽數量，但同時預測結果也僅限于小規模的標簽子集內.因此，目前蛋白質功能預測方法的研究其實并沒有真正解決大量標簽分類問題.

基于以上考慮，本文針對蛋白質功能注釋標簽數量龐大的問題，提出一種基于布爾矩陣分解的蛋白質功能預測框架(protein function prediction based on Boolean matrix decomposition, PFP-BMD)，并特別針對框架中的精確布爾矩陣分解(Boolean matrix decomposition, BMD)模塊進行具體研究，提出一種基于標簽簇的精確BMD算法Label-Cluster.本文的研究也是首次基于布爾矩陣分解針對蛋白質功能預測問題開展的研究，可為各種多標簽分類器在蛋白質功能預測中的高效應用奠定基礎.

1 相關工作

除了在蛋白質功能注釋數據中，在文本和圖片分類場景中也會存在標簽數量過于龐大的問題.針對這一問題，一種稱為標簽空間降維(label space dimension reduction, LSDR)的方法被研究者們提出，其基本思想就是利用矩陣降維技術將標簽空間矩陣投影到低維標簽空間，多標簽分類器的訓練和測試都只對低維標簽空間進行.

Hsu等人[15]在2009年利用壓縮感知技術首次實現了該類方法.此后研究者們相繼利用主成分分析[16]、典型相關分析[17]和奇異值分解[18]等手段對LSDR進行了研究.盡管主成分分析和奇異值分解等矩陣降維技術可以很好地將大規模標簽降維一個低維空間，但是降維后的空間也失去了原始標簽的含義.為了解決這一問題，Balasubramanian等人[19]提出了標簽子集選擇的思想，即低維標簽選擇自原標簽空間.此后，Bi等人[20]提出了多標簽分類的列子集選擇方法(column subset selection for multi-label, CSS-ML)，該方法基于一個隨機采樣過程選擇出k個標簽以盡可能覆蓋所有的標簽，并且在選擇好的標簽上學習了k個分類器.總的來說，以上方法都只是將標簽矩陣看作一個普通的矩陣來進行維度降低.從多標簽分類的角度看，蛋白質功能標簽矩陣顯然是一個布爾矩陣(只有2種值0和1).文獻[21]已證明：某些能夠進行精確BMD的矩陣卻不一定能進行普通的矩陣分解，因此BMD對標簽的降維效果要好于普通矩陣分解.

通過以上分析可知，數量龐大的蛋白質功能注釋標簽已成為提高各類多標簽分類器預測效果的一大障礙.本文采用BMD方法實現蛋白質功能預測過程中功能標簽的維度降低，即可保留功能標簽的生物意義亦可完成更精確的降維.同時，本文在PFP-BMD中使用精確BMD算法，能夠使降維后的分類及還原最大程度地保留分類器的分類精度，而“列利用條件”則可使降維后的標簽空間仍然具有原標簽的意義.

2 基于布爾矩陣分解的蛋白質功能預測框架

在本節中，我們詳細介紹PFP-BMD的基本思想.

2.1 蛋白質功能預測及相關符號定義

基于多標簽分類的思想，本文首先對蛋白質功能預測問題進行形式化定義：

蛋白質功能預測的任務就是從已知特征向量和功能標簽向量的訓練數據集Dtrain={X1,X2,…,Xm|Xd=(Fd,Yd),d∈[1,m]}中，對多標簽分類模型進行訓練，然后使用訓練好的模型對已知特征向量但未知功能注釋標簽向量的新蛋白質Dtest={X1,X2,…,Xn|Xd=(Fd,?),d∈[1,n]}，預測出其功能標簽Yd.

2.2 框架描述

Fig. 2 The framework of protein function prediction based on Boolean matrix decomposition圖2 基于布爾矩陣的蛋白質功能預測框架

為了解決蛋白質功能預測中數量龐大的功能標簽問題，本文采用LSDR的思想，在預測過程中加入精確布爾矩陣模塊以實現蛋白質功能標簽矩陣的降維和還原，精確BMD模塊與多標簽分類器一起構成了本文的PFP-BMD.PFP-BMD的流程描述如圖 2所示:

PFP-BMD的基本思想為：

由圖2可看出，基于布爾矩陣分解的蛋白質功能預測框架的優勢在于：利用精確的布爾矩陣分解得到的矩陣能夠一定程度上減輕多標簽分類器的訓練及預測任務，而多標簽分類器的輸出結果只需要和矩陣B進行簡單的布爾乘即可還原回原標簽空間.在框架中，精確BMD模塊和多標簽分類器模塊是2個相對獨立的部件，因此該框架可適用于多種多標簽分類器，其中精確BMD模塊既能保留在分類時標簽的生物意義，同時在還原回原標簽時并不降低分類精度.

3 精確布爾矩陣分解算法

在本節中，我們針對PFP-BMD中的精確BMD模塊進行具體研究，提出一個改進的精確布爾矩陣分解算法Label-Cluster.

3.1 精確布爾矩陣分解算法基礎

本節首先給出布爾矩陣分解的定義及文獻[27]中的相關定義、命題和定理.

換句話說，布爾矩陣乘法就是在普通矩陣乘法中加一條額外的定義1+1=1，最小的k通常被稱為Y的布爾軼，且已有研究表明一個布爾矩陣的布爾軼可能大于或小于它的實數軼[28].對于可以找到最小k的布爾矩陣分解算法，則稱其為最優布爾矩陣分解.

即Y=C°B.

定義1.給定2個布爾矩陣U=(Ui j)∈{0,1}m×n和V=(Vi j)∈{0,1}m×n，如果對于所有的i=1,2,…,m和j=1,2,…,n都滿足Ui j≥Vi j，則稱U≥V.

命題1.布爾乘法滿足擴展:

在文獻[27]所提出的BMD方法中，首先證明了存在一個布爾矩陣J，使得Y=Y°JT成立，并且當J中的任意元素從0改變為1時等式就不再成立，即J是使等式成立的最大矩陣.文獻中所提出的啟發式算法Remove-Smallest基于2個定理：

3.2 功能標簽關聯矩陣

矩陣J在文獻[27]中與原矩陣Y一起構成了最優布爾矩陣分解的搜索空間.在對矩陣J的深入研究中，本文發現：矩陣J本質上是對原矩陣Y各列關聯關系的一種表示.我們將在本節對蛋白質功能預測中的功能標簽關聯矩陣A進行定義，以及通過推論1證明其與矩陣J的關系.

在蛋白質功能注釋命名方案GO和FunCat中，蛋白質的功能標簽之間具有層次關系，FunCat中是樹形結構，而GO中是有向無環圖(directed acyclic graph, DAG)結構.也就是說，不論是在FunCat還是在GO中，用于蛋白質功能預測的多標簽分類器必須滿足層次約束，即被一些功能注釋的蛋白質一定會被這些功能的父節點功能注釋.本文使用符號parent(ci)表示功能標簽ci的父標簽集，使用des(ci)表示功能標簽ci的祖先標簽集.如圖3所示c1到c8共8個功能標簽的層次關聯，其中des(c7)={c1,c2,c3,c4}.

Fig. 3 The diagram of associated labels圖3 標簽關聯示意圖

對于功能標簽間的DAG層次關聯關系，本文使用了一個矩陣A=(Ai j)∈{0,1}S×S來描述，A中的元素Ai j滿足：若功能標簽ci∈des(cj)則Ai j=1，否則為0.顯然，矩陣A可通過功能標簽間固有的DAG關系計算得出圖3的矩陣A：

下面通過推論1來證明矩陣A和矩陣J之間的關系.

證明. 從定理1可得只要證明Y=Y°AT，則有J≥A.在A中，Ai j=1表示第i個標簽是第j個標簽的祖先；在AT中，(AT)i j=1說明第i個標簽是第j個標簽的子孫；顯然對于A和AT，Ai i=1以及(AT)j j=1成立.下面分2種情況進行證明：當矩陣Y中的元素Yi j=1時，由于有(AT)j j=1，則Y°AT中的元素(Y°AT)i j=1；當矩陣Y中的元素Yi j=0時，由于矩陣Y中的第i行不可能存在一個元素Yi k=1且AT中的(AT)k j=1，因為(AT)k j=1說明標簽k是標簽j的子孫，如果Yi k=1則一定有Yi j=1，這與假設相背，因此Y°AT中的元素(Y°AT)i j=0.綜上2種情況，Y=Y°AT均成立，則由定理1可得J≥A成立.

證畢.

從推論1可以看出，矩陣J不僅覆蓋了原始標簽集的一個DAG關聯，并且還反映了由矩陣Y中的值隱含的列之間的關聯關系.因此，矩陣J本質上是一個標簽關聯矩陣.

3.3 基于標簽簇的布爾矩陣分解算法

由3.2節討論可知，對于矩陣Y，矩陣A反映的是標簽間固有的層次約束關系，即Y中的元素必須滿足：如果矩陣A中的元素Ai j=1，且Yd j=1，則Yd i=1.換句話說，當子孫標簽cj注釋了某蛋白質d時，它會使得cj所有的祖先標簽des(cj)均注釋該蛋白質.如圖3中的功能標簽c7，其所注釋的蛋白質也一定被其祖先標簽集des(c7)={c1,c2,c3,c4}所注釋.

基于以上這種層次約束關系，如果將矩陣Y中所有祖先標簽這種因其子孫擴展而來的注釋關系去掉，那么可能會出現大量祖先標簽注釋蛋白質的數量為0，當將這些不再注釋蛋白質的祖先標簽從標簽集中去掉時，并不會影響其他標簽對蛋白質的注釋關系，而通過祖先標簽與保留的子孫標簽的層次關聯關系，又可以很容易地恢復祖先標簽對蛋白質的標準.顯然，只需保留最下層的葉子標簽即可最大程度地刪除不再注釋蛋白質的祖先標簽.本文將這種保留下的子孫標簽稱為一個標簽簇，因為盡管保留下來的僅僅是一個單獨的子孫標簽列，但是它卻包含了從它開始向上擴展一直到根標簽的一個標簽子集.

如圖3中的功能標簽c7可與其祖先標簽集構成一個標簽簇{c1,c2,c3,c4,c7}，而c7對蛋白質的注釋數據同時也可反映出c1～c4是否注釋了某些蛋白質.如果對矩陣Y找出所有這樣的標簽簇，保留下標簽簇中的最下層標簽，那么相當于實現了標簽空間的降維，而標簽簇對蛋白質的注釋矩陣與標簽簇與標簽的對應關系矩陣相乘則可得到對原標簽空間的還原，這一過程實際就是一個精確的BMD.

由推論1可知，矩陣J本質上是一個標簽的關聯矩陣且J≥A，即矩陣J描述功能標簽間關聯關系最完整的矩陣，不僅包含功能標簽間固有的DAG關系，同時還包含了矩陣Y中的值之間反映的關聯關系.因此，按照以上標簽聚簇思想同樣可基于矩陣J來構造標簽簇集，以完成Y的精確BMD.基于以上分析，本文提出了基于標簽簇的精確BMD算法，如算法1所示:

算法1.Label-Cluster算法.

① 輸入布爾矩陣Y∈{0,1}D×S；

③ For eachi=1,2,…,Ddo

For eachj=1,2,…,Sdo

IfYi j=1 then

End If

End For

End For

⑤ 計算矩陣B∈{0,1}k×S:從J中挑選出對應到C中的k列得到J′∈{0,1}S×k，最后得到B=(J′)T;

⑥ 對矩陣C按照矩陣B進行標簽關聯擴展：若對于Ci j=0，存在Ci m=1且Bm j=1，則Ci j=1;

⑦ 輸出布爾矩陣C∈{0,1}D×k和B∈{0,1}k×S.

在Label-Cluster算法中，矩陣C成為了蛋白質功能的“標簽”矩陣，其中每一個新的功能“標簽”(即C中的每一列)既是一個原始標簽也代表了原始標簽集的一個子集(標簽簇：一個原始標簽的所有祖先標簽及其本身的一個集合)，即滿足“列利用條件”約束.對于每個蛋白質，矩陣C以一個更低的維度表現了蛋白質所有的原始功能標簽，而矩陣B中的每一行是一個標簽簇到原始標簽的一個對應關系，如果Bi j=1，那么標簽簇i中包含了原始標簽j，否則為0.矩陣B所描述的這種標簽簇與標簽間的對應關系，可以很自然地用于標簽簇矩陣到原始標簽矩陣的還原.

同時，需要注意的是:不是所有的祖先標簽都能在被聚簇后而在矩陣C中被消去，除非它對所有蛋白質的注釋都能被其標簽簇所表示.因此，在算法1中，步驟2首先是將對矩陣Y中的每一個元素進行更新，如果Yi j=1，且存在j的某孩子標簽m有Yi m=1，那么將Yi j更新為0，在對Y中的每個元素進行更新后，如果某標簽可以被其標簽簇完全表示，那么該列將全部為0，即可刪除.在步驟3刪除全0列得到矩陣C之后，還需要步驟5對步驟2中更新為0但沒有被隨列刪除的元素進行恢復，進而使得矩陣C滿足“列利用條件”.因此算法1是對聚簇操作的一種程序實現的具體表示，與本節所闡述的聚簇思想相對應.

3.4 Label-Cluster算法的相關推論及證明

為了證明Label-Cluster算法可得到矩陣Y的最優精確布爾矩陣分解，我們在本節中通過4個推論對其進行證明.

推論2.給定一個布爾矩陣Y∈{0,1}D×S，(C,B)=Label_Cluster(Y)，C∈{0,1}D×k且B∈{0,1}k×S.那么通過算法Label-Cluster′(將Label-Cluster中的矩陣J替換為任意滿足式Y=Y°HT的矩陣H)可得到(C′,B′)=Label_Cluster′(Y)，C′∈{0,1}D×k′且B∈{0,1}k′×S，則k≤k′成立.

證畢.

通過推論2可得，在算法Label-Cluster中基于矩陣J所得到的矩陣C的列數k是最小的，若在Label-Cluster算法中基于其他關聯標簽關聯矩陣所得到的矩陣C的列數k′均大于k.

推論3.給定一個布爾矩陣Y∈{0,1}D×S，(C,B)=Label_Cluster(Y)，C∈{0,1}D×k且B∈{0,1}k×S，則Y=C°B成立.

證明. 假定Yi j=0，當C中第i行的任意元素Ci m=1，說明第i個實例被第m個標簽簇所標注，如果有Bm j=1，說明第m個標簽簇包含了第j個標簽，則第i個實例一定也被第j個標簽所標注，即Yi j=1，但這與假設相悖.因此當Ci m=1時，一定不存在Bm j=1，則(C°B)i j=0.假定Yi j=1，因為C中不存在全0列，因此一定有一個Ci m=1，同樣，如果Bm j=0，說明第m個標簽簇不包含第j個標簽，那么第i個實例一定不被第j個標簽所標注，即Yi j=0，這與假設相悖.因此當Ci m=1時，一定有Bm j=1，則(C°B)i j=1.綜上所述，2種情況下Yi j=(C°B)i j，即Y=C°B成立.

證畢.

通過推論3可得，算法Label-Cluster所得到的矩陣C和B是Y的精確BMD.

證畢.

證畢.

由推論4和推論5可得，算法Label-Cluster得到的矩陣C和B滿足：如果再從矩陣C和B中刪除列和行，則所得到的矩陣不再能滿足Y的精確分解.即證明了矩陣C和B是Y的最優布爾矩陣分解.

4 蛋白質功能預測實驗

在本節中，我們分別對Label-Cluster算法和PFP-BMD在3個數據集進行了實驗驗證，并選用針對大規模標簽的分類模型與本文所提方法進行對比.

4.1 數據集

為驗證Label-Cluster算法和PFP-BMD的有效性及優勢，本文采用了一個被廣泛使用的標準蛋白質功能預測數據集酵母數據集(s.cerevisiae dataset, S.C)[9]進行實驗分析.該數據集的蛋白質特征數據包含酵母基因的多個方面，如序列統計特征、表型特征、基因表達特征、二級結構特征和同源特征等，其包含了S.C-1到 S.C-12共12個數據集，并且每個數據集都使用了FunCat和GO這2種功能注釋方案，本文主要使用了S.C中GO功能注釋方案的S.C-1到S.C-3數據集.該數據集的數據格式都是Weka(waikato environment for knowledge analysis)的arff文件，以便于更多的Weka中的基準多標簽分類算法應用到該數據集上.由于S.C數據集均已根據GO功能標簽間的DAG結構對標簽注釋數據進行了擴展，因此本文無需再做此預處理.

Table 1 The Statistics of S.C Dataset表1 S.C數據集統計

4.2 Label-Cluster實驗分析

4.2.1 對比算法及時間復雜度分析

本節將Label-Cluster算法與文獻[27]中的Remove-Smallest算法進行蛋白質功能標簽矩陣降維實驗對比.由于Remove-Smallest和Label-Cluster算法都是屬于精確BMD方法，均能完整地還原回原矩陣空間，因此2個算法在文獻[27]中使用的BMD算法評價標準覆蓋率值均為100%.下面對2個算法的時間復雜度進行分析.

4.2.2 實驗結果

Label-Cluster算法分別在上述3個數據集中進行布爾矩陣分解，實驗結果如圖4所示，圖4中降維率=(原標簽數量-降維后的標簽數量)原標簽數量，降維率可以反映了精確BMD算法對不同數據集的降維效果差異，其值越大說明對高維標簽的降維程度越高.

Fig. 4 The dimension deduction comparisons of Label-Cluster algorithm in three dataset圖4 Label-Cluster算法在3個數據集上的降維效果對比

由圖4可以看出，對于不同的數據集，Label-Cluster算法的降維率不盡相同，其中對S.C-2數據集的降維程度最高.這主要是各數據集中標簽的關聯程度不同導致的，如圖4中的虛線所示，S.C-2數據集的樣本平均標簽數量要高于S.C-1和S.C-3數據集.換句話說，Label-Cluster算法對于標簽關聯度更大的數據趨向于得到更高的降維率.

由于Remove-Smallest和Label-Cluster算法都是屬于精確BMD算法，因此在不同的數據集上在降維效果上是完全相同的.但由4.2.1節的分析可知，Label-Cluster較Remove-Smallest算法在時間復雜度上有較大優勢，表2和圖5展示了2個算法運行的實驗環境及在不同數據集中的運行時間對比.

Table 2 The Experimental Environment表2 實驗環境

從圖5可知：本文提出的Label-Cluster相比Remove-Smallest算法在計算速度上有較大提高，運行時間能減少90%左右，且能完成標簽矩陣的精確布爾分解，并遵循“列利用條件”.特別是算法中引入了標簽簇的思想，對分解后的保留的標簽看作是原有標簽的一個聚類，更利于解釋后續分類的結果.

Fig. 5 The run time comparisons of Label-Cluster and Remove-Smallest algorithm圖5 Remove-Smallest算法和Label-Cluster算法運行時間對比

4.3 PFP-BMD實驗分析

4.3.1 評價標準

蛋白質功能預測作為一個多標簽分類問題，可以使用通用的多標簽分類評價指標對模型的分類性能進行評估.如引言所述，目前常用的蛋白質功能預測算法主要是針對小規模的功能標簽子集進行訓練和預測.文獻[9]是一個針對大規模蛋白質功能標簽集的多標簽分類方法研究，為了與此類方法進行對比，本文亦采用了相同的評價標準，即精確率-召回率曲線下面積(area under the precision-recall curve, AUPRC).AUPRC的值越接近于1，則模型性能越好.

在蛋白質功能預測數據集中大部分的功能標簽注釋的蛋白質數量很少，這也就意味著對于大部分功能標簽來說負例的數量會大大超過正例的數量.而本文更加關心的是正確預測出的正例(蛋白質被某個功能標簽所注釋)，而不是正確預測出負例(蛋白質不被某個功能標簽所注釋).據此，本文采用PR(precision-recall)曲線進行評價是合理的.

當然，PR曲線僅僅是針對單個的標簽來計算，而對于蛋白質功能預測則要同時面對多個功能標簽.因此，為了評價蛋白質功能預測方法的整體性能，文獻[9]采用了2種AUPRC評價指標.

1) 平均PR曲線下的面積(area under the average PR curve,RMicroAUPRC)

第1種獲得多標簽分類模型整體性能分數的方法就是通過將多標簽分類問題轉化為一個二值問題以構造出整體的PR曲線.假設一個二值分類器的輸入是一個(樣本，類別)對，輸出是預測出該樣本是否輸入該類別，一個排序分類器可以通過選擇一個閾值而轉化為一個二值分類器，并且通過變化閾值則可得到一條PR曲線.

對于給定的閾值，對應的是PR空間中的一個點的坐標值為(prec,rec)，其定義為

其中，i表示第i個標簽，通過變化閾值就可以得到1根平均PR曲線，并將其曲線下的面積表示為RMicroAUPRC.

2) PR曲線下的平均面積(average area under the PR curves,RMacroAUPRC)

第2類方法是求單根PR曲線(一個標簽)下面積的權值平均，計算方法如下：

其中，Ri表示第i個標簽的AUPRC值.當將所有wi設置為1時，計算結果表示為RMacroAUPRC. 若對wi以不同的策略取值，計算結果表示為RMacroWAUPRC. 在RMacroWAUPRC的計算過程中，對于權值wi最直觀的想法就是設置為1|S|，其中S是標簽的數量.對于權值wi第2種最自然的取值就是其中vi表示類別si在數據集中出現的頻率.第2種權值設置方法反映出標注樣本越多的標簽越重要.

總的來說，上述2種針對多標簽分類的AUPRC值計算方法，RMicroAUPRC實際是對AUPRC值求微平均，因此可稱其為PR曲線下面積微平均值(micro average of AUPRC,MICRO-AUPRC)，換句話說RMicroAUPRC是在所有標簽的混合中來評價模型.而RMacroAUPRC實際是對AUPRC求宏平均，可稱其為PR曲線下面積宏平均值(macro average of AUPRC,MACRO-AUPRC)，RMacroWAUPRC則稱為PR曲線下面積帶權重宏平均值(macro average of AUPRC with weight,MACRO-WAUPRC)，它們可在一定程度上反映出各個獨立標簽的預測準確率.

4.3.2 對比算法及實驗設置

本節在蛋白質功能預測框架PFP-BMD中的精確BMD模塊采用Label-Cluster算法，多標簽分類器模塊采用多標簽最近鄰算法(multi-label K-nearest neighbor, MLKNN)[29-30].對比算法使用文獻[26]中的MLC-BMAD(multi-label classification using Boolean matrix decomposition)，以及文獻[9]中的3個層次多標簽分類算法CLUS-HMC，CLUS-SC，CLUS-HSC.

MLKNN是對傳統K近鄰算法在多標簽分類中的一種改進，本文在實驗中設置MLKNN的鄰居數目為10，平滑因子為1.

MLC-BMAD是一個專門針對大規模標簽的多標簽分類的方法.其思想與PFP-BMD非常類似，也是先通過BMD對原標簽進行降維，預測之后再還原回原標簽空間，但MLC-BMaD中使用的是近似BMD算法，因此需預先設定降維后的標簽數量，同時本文將MLC-BMAD在3個數據集上的標簽關聯閾值均設置為0.5.

CLUS-HMC，CLUS-SC，CLUS-HSC是3個基于決策樹的層次多標簽分類器，其中CLUS-HMC可同時學習所有的層次標簽，CLUS-SC是為每個標簽學習一棵獨立的決策樹，CLUS-HSC在CLUS-SC的基礎上考慮了標簽間的層次依賴.這一個算法在多篇對蛋白質功能預測的研究論文中被證明是一類性能較佳的算法，特別是CLUS-HMC在數據集S.C中的實驗結果均優于多個層次多標簽分類器及CLUS-SC和CLUS-HSC.本文CLUS-HMCHSCSC算法的實驗結果來自于文獻[9]中.在文獻[9]的實驗中，CLUS-HMCHSCSC算法是在完整的S.C數據集中進行，保留了功能標簽間的層次關系，且無需經過標簽降維.盡管PFP-BMD需要經過標簽降維，但降維后的標簽還能還原回原始標簽，因此它和CLUS-HMCHSCSC算法在預測結果的標簽空間上是相同的.

本文的多標簽分類實驗采用十折交叉驗證，實驗評價指標使用了4.3.1節所述的RMicroAUPRC，RMacroAUPRC，RMacroWAUPRC3種PRC曲線下面積，對于這3種評價標準，評價標準的值越大，預測準確率越高.

4.3.3 PFP-BMD與MLC-BMAD對比實驗結果

由于MLC-BMAD采用的是近似布爾矩陣分解算法進行降維，因此本文分別在3個數據集中為其設置一個降維標簽數量的范圍，最后與PFP-BMD在固定的降維標簽數下進行對比.圖 6展示了對比結果:

Fig. 6 The experimental comparisons of PFP-BMD and MLC-BMAD圖 6 PFP-BMD與MLC-BMAD實驗結果對比

由圖6可以看出，隨著設置的標簽數量的增加，MLC-BMAD的3個評價標準值均在降低，這是由于較小的降維后標簽數量可使分類器獲得更高的分類準確率.同時，由于MLC-BMAD所使用的近似布爾矩陣分解算法不能夠在分類后將標簽矩陣精確還原，這會大大損失還原后的分類準確率.因此對于S.C-1，S.C-2，S.C-3數據集，盡管MLC-BMAD方法可設置較大范圍的降維后標簽數量，但與PFP-BMD固定數量的降維標簽相比，MLC-BMAD在3個評價標準RMicroAUPRC，RMacroAUPRC，RMacroWAUPRC上所獲得的值顯著低于PFP-BMD.在數據集S.C-1上，PFP-BMD的RMacroWAUPRC值高于MLC- BMAD在各降維標簽數量范圍內平均值的31%，RMacroAUPRC值高于MLC-BMAD的46%，RMicroAUPRC值高于MLC-BMAD的20.4%；在數據集S.C-2上，PFP-BMD的RMacroWAUPRC值高于MLC-BMAD在各降維標簽數量范圍內平均值的1.2%，RMacroAUPRC值高于MLC-BMAD的2.5%，RMicroAUPRC值高于MLC- BMAD的50%；在數據集S.C-3上，PFP-BMD的RMacroWAUPRC值高于MLC-BMAD在各降維標簽數量范圍內平均值的4%，RMacroAUPRC值高于MLC-BMAD的0.1%，RMicroAUPRC值高于MLC-BMAD的34%.

由圖7所示，在將所有標簽看作同等重要的評價指標RMacroAUPRC上，PFP-BMD具有顯著優勢.分別與CLUS-HMC，CLUS-HSC，CLUS-SC相比：PFP-BMD在數據集S.C-1上的RMacroAUPRC值提高了86.5%，86.9%，86.9%；在數據集S.C-2上的RMacroAUPRC值提高了92.7%，93.4%，92.7%；在數據集S.C-3上的RMacroAUPRC值提高了90.2%，90%，90%.這是由于RMacroAUPRC的計算并不偏重于反映注釋較多蛋白質的功能標簽預測準確率，而是針對所有標簽預測準確性的平均.在PFP-BMD中，注釋蛋白質較少的功能標簽在BMD之后更趨向于被降維刪除，但矩陣B表示了它和保留標簽的關聯關系，可以通過矩陣還原較準確的得到它的預測結果，以此提高了所有標簽的平均預測準確率.同時，由圖7也可以看出，CLUS-HMC，CLUS-HS，CLUS-SC這3個算法在數據集S.C-1到S.C-3上獲得了相似的RMacroAUPRC值.PFP-BMD在RMacroAUPRC上的優勢說明PFP-BMD較CLUS-HMCHSCSC更有利于提高標注蛋白質少的標簽的分類結果.

Fig. 7 The experimental comparisons of PFP-BMD and CLUS-HMCHSCSC圖7 PFP-BMD與CLUS-HMCHSCSC實驗結果對比

同時，對于考慮了標簽標注頻率的評價指標RMicroAUPRC，PFP-BMD在3個數據集上的值略低于CLUS-HMC，但在RMacroWAUPRC評價標準上獲得了和CLUS-HMC基本一致的結果，且顯著優于CLUS-HSC和CLUS-SC.在數據集S.C-1上，PFP-BMD的RMacroWAUPRC值和CLUS-HMC相比提高了1.3%，和 CLUS-HSC相比提高了25%，和CLUS-SC相比提高了26%；在數據集S.C-2上，PFP-BMD的RMacroWAUPRC值和CLUS-HMC相比降低了1.3%，和CLUS-HSC相比提高了19%，和CLUS-SC相比提高了19%；在數據集S.C-3上，PFP-BMD的RMacroWAUPRC值和CLUS-HMC相比降低了1.5%，而和CLUS-HSC相比提高了17.6%，和CLUS-SC相比提高了 18.9%.CLUS-HMC在考慮了標簽標注頻率評價標準上的優勢是由于這類層次多標簽分類算法在分類過程中考慮了標簽間的層次關系，因此對于處于底層的標注頻率較高的標簽具有更好的預測準確率，而標注頻率較高的標簽預測結果對RMicroAUPRC和RMacroWAUPRC的貢獻較大.

總結：從以上實驗結果可以看出，本文PFP-BMD的首先利用Label-Cluster算法完成對蛋白質功能標簽矩陣的精確布爾矩陣分解，能有效地降低后續多標簽分類器的負擔并提高多標簽分類器的分類準確率，最后再通過Label-Cluster算法得到的矩陣B可完整地將預測結果還原回原標簽空間.這類LSDR的思想與直接對大規模功能標簽進行分類的方法相比(如CLUS-HMCHSCSC)，由于在降維過程中趨向于舍去標注蛋白質少的功能標簽，但最后在還原過程可以對其進行完整的還原，因此對于提高這一類功能標簽的預測準確率具有明顯優勢.而與近似布爾矩陣分解的多標簽分類方法相比(如MLC-BMAD)，盡管近似布爾矩陣可以任意指定降維數以獲得更低的標簽維數，但近似還原同時也會一定程度地降低功能標簽的預測準確率，而Label-Cluster算法可以在不降低預測準確率的條件下對標簽矩陣進行精確還原，因此本文提出的方法在與MLC-BMAD的對比實驗中仍取得了較好的結果.

5 結束語

蛋白質功能注釋是蛋白質組學最重要的研究內容，通過各種可計算模型實現蛋白質功能的自動注釋是當前生物信息學的一個研究熱點.本文將蛋白質功能預測作為一個多標簽分類問題進行研究，針對蛋白質功能標簽數量龐大的問題，提出了一種基于布爾矩陣分解的蛋白質功能預測框架.并針對框架中的布爾矩陣分解模塊，提出了一種基于標簽簇的精確布爾矩陣分解算法Label-Cluster.該算法利用標簽關聯矩陣J對標簽矩陣進行標簽簇構造，每一個標簽簇代表了一個原始標簽的所有祖先標簽及其本身的集合，因此滿足“列利用條件”約束.實驗結果表明：Label-Cluster算法能夠有效地完成大規模標簽降維任務并且在運行速度上具有明顯優勢，且應用該算法的蛋白質功能與PFP-BMD能夠有效提高大規模功能標簽的整體預測準確率，特別對于提高注釋蛋白質數量較少的功能標簽預測準確率具有較大優勢.

同時，PFP-BMD中多標簽分類器的選用對分類結果有較大影響，盡管本文的實驗部分僅選用了MLKNN一種分類器，但PFP-BMD可支持多種分類器的應用，因此PFP-BMD的實驗效果還具有較大的提升潛力.目前，隨著網絡應用的蓬勃發展，使得更多的多標簽分類場景中的實例傾向于與大量的標簽相關聯，而本文所提出的PFP-BMD和Label-Cluster算法將蛋白質功能預測的過程作為一種通用的多標簽分類場景進行處理，因此本文的研究對于各領域中的大規模多標簽分類問題也具有廣泛的應用價值.