基于FP樹的蛋白質功能預測算法研究

葛凌霄

（四川大學計算機學院，成都 610065）

0 引言

蛋白質組學是以蛋白質為研究對象，以研究細胞、組織或生物體蛋白質組成及其變化規律的科學，目的是通過分析生物體內的蛋白質的表達模式和功能模式，以此能夠生物體與細胞的整體水平闡釋生命現象的本質規律。對細胞內的蛋白質進行功能注釋是蛋白質組學的一個重要的研究方向，通過對未注釋蛋白質的功能預測，能夠在生物技術制藥、生物治療、農作物基因改良等領域發揮重要作用。傳統的生物實驗進行功能注釋的方法費時且成本高，因此研究基于蛋白質相互作用網絡內的計算方法是當前生物信息學家所面臨的重要問題。

1 方法

1.1 蛋白質相互作用網絡

隨著研究蛋白質相互作用的高通量實驗技術的發展，現在已可以獲取到大量的蛋白質相互作用數據，這也讓我們可以使用統計學來對這些數據集進行數據挖掘。我們以圖的思想，將這些復雜的蛋白質之間相互作用關系數據構建成為一張復雜的網絡，稱為蛋白質相互作用網絡（Protein-Protein Interaction Network,簡稱PPI網絡），接著我們就能夠使用圖論以及復雜網絡等研究方法對其研究。蛋白質相互作用網絡的定義為細胞內所有蛋白質中任意對蛋白質之間可能發生的相互作用關系的完整集合。

圖1

圖1是一個蛋白質相互作用網絡，我們通常將其看作為一個無向圖G（V，E），圖中每個節點v表示一個蛋白質，而每條連接兩個節點的邊e表示蛋白質與蛋白質之間的相互作用關系，在根據具體研究需要時，有時會給邊分配權值變為有權圖，此時邊的權值代表兩個蛋白質之間作用關系的強度。

1.2 中心接近度

在現實中，我們經常會遇到求兩個點之間最短路徑的問題，但也有這樣實際生活場景，例如要建造一個大型的娛樂商場，希望光臨的顧客到達這個商場的距離都可以盡可能地短。這個就涉及到接近中心性的概念，接近中心性的值為路徑長度的倒數。

接近中心性需要考量每個結點到其他結點的最短路徑的平均長度。也就是要計算的是到圖中其他節點的距離總和比較小，計算的是這個節點處于圖中間位置的程度。在一個復雜網絡里，接近中心性越高的節點，越趨向于整個圖的中心。

在蛋白質相互作用網絡里，蛋白質i的接近中心度定義為：

式中，N為蛋白質節點i的鄰接節點，為蛋白質節點i與蛋白質節點j的最短路徑距離。

1.3 FP樹

關聯分析通常能夠用來挖掘出數據之間的聯系，其中最常用的方法就是關聯規則的挖掘。FP樹，又稱FP-growth算法就是關聯規則挖掘的常用方法之一。FP-growth算法的思路為，首先壓縮數據集，將數據集內所有事務使用FP樹這樣的數據結構進行表示，接著使用遞歸的方法將頻繁項集依次分解為各自的子問題進行挖掘。

FP-growth算法步驟：

（1）FP樹的構建

FP樹是一種前綴樹，每個節點有三個指針，分別指向父節點，子節點和鏈接指針。此外，數據結構中還包含有一個頭指針表，頭指針表中記錄每個元素出現的第一個結點，結點中的鏈接指針將所有相同的元素連接起來。

算法開始時會開始掃描兩次數據庫，第一次掃描數據庫時，列舉出所有項，確定1-項頻繁集。第二次掃描數據庫時，將數據中支持度小于閾值的項刪除，然后將這個數據按照剛才項出現次數排序。排序后每個項集都有一個唯一的順序，這樣可以保證后續算法找出所有不重復的頻繁項集。然后將這個數據插入到FP樹中，并且更新頭指針表和鏈接指針。

（2）挖掘頻繁項集

挖掘頻繁項集時，從單項集出發每次增加一個元素。對于每一個頻繁項集以前綴路徑構造一棵FP樹，然后向當前的頻繁項集中添加一個元素，然后以深度優先的策略遞歸地進行這個過程直到發現所有頻繁項集。

2 數據與實驗

2.1 數據

我們用于實驗的酵母細胞蛋白質的相互作用數據來自于String數據庫（https://string-db.org/cgi/download.pl?UserId=OaGetiAwHwOi&sessionIdGoVW2b711k9A&species_text=Saccharomyces+cerevisiae），共有 6391個蛋白質和2007134條相互作用信息。

功能注釋使用的是慕尼黑蛋白質信息中心（MIPS）所制定的功能目錄(FunCat)方案，該方案是一種樹形層次結構的分類方案，總共包含有28個大類的主要蛋白質功能。酵母的FunCat注釋數據源來自于CYGD（Comprehensive Yeast Genome），目前已有功能注釋的蛋白質數量為4779個，這些蛋白質包含了17大類的功能注釋，我們將沒有功能注釋的蛋白質從網絡中刪除，最終得到的酵母細胞蛋白質相互作用網絡的節點為4791個，包含406731條相互作用數據。

2.2 實驗過程

（1）計算蛋白質相關度閾值

為了提高預測的精度，首先對蛋白質相互作用網絡內的蛋白質進行分類，并計算相關性的閾值。

依照接近中心度公式，計算整個網絡內每個節點的接近中心度，使用整個網絡內所有節點計算中心度的平均值作為篩選閾值，將蛋白質分為高相關度低相關度兩類。

（2）修剪子圖

使用與待預測蛋白質節點所對應相關度的蛋白質節點組成新的蛋白質相互作用網絡，對網絡內的每條邊計算其邊聚數系數，如果邊聚數系數小于對應的閾值，則將其刪除，最后形成一張新的子圖。

（3）挖掘最大頻繁項集預測蛋白質功能

在修建過的子圖里，找到需要預測的蛋白質節點的所有鄰接節點，使用FP-growth算法計算這些蛋白質節點功能的最大頻繁項集，求得結果作為預測蛋白質的功能集合。

2.3 結果分析

為了測試和對比我們的是實驗結果，我們使用信息檢索領域兩個常用的評價指標，準確率和召回率，定義如下：

其中TP代表真陽性、FP代表假陽性、FN代表假陰性。

我們將計算出的兩個結果與其他兩種常用算法進行比較，結果如圖2所示，可看出在高相關度下使用FP樹進行頻繁項集挖掘預測可以提高蛋白質功能預測的準確率。

3 討論

本文研究的是在蛋白質相互作用網絡里對未注釋的蛋白質進行功能預測。提出的方法是使用待預測蛋白質在網絡中的鄰接節點進行關聯規則挖掘。在關聯分析之前，首先使用復雜網絡里接近中心度的思想計算網絡內節點的中心性，并計算出閾值，使用閾值對蛋白質節點分類并對網絡去邊。之后使用FP樹來挖掘出鄰接節點的最大頻繁項集。最終通過實驗證明，該算法能夠提高蛋白質的功能預測精度。

圖2

參考文獻：

[1]李錦澤，葉曉俊.關聯規則挖掘算法研究現狀[J].計算機技術與應用進展，2007.

[2]王淑琴.機器學習方法及其在生物信息學領域中的應用[D].吉林：吉林大學，2009