基于FP樹的蛋白質(zhì)功能預(yù)測(cè)算法研究

葛凌霄

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065）

0 引言

蛋白質(zhì)組學(xué)是以蛋白質(zhì)為研究對(duì)象，以研究細(xì)胞、組織或生物體蛋白質(zhì)組成及其變化規(guī)律的科學(xué)，目的是通過(guò)分析生物體內(nèi)的蛋白質(zhì)的表達(dá)模式和功能模式，以此能夠生物體與細(xì)胞的整體水平闡釋生命現(xiàn)象的本質(zhì)規(guī)律。對(duì)細(xì)胞內(nèi)的蛋白質(zhì)進(jìn)行功能注釋是蛋白質(zhì)組學(xué)的一個(gè)重要的研究方向，通過(guò)對(duì)未注釋蛋白質(zhì)的功能預(yù)測(cè)，能夠在生物技術(shù)制藥、生物治療、農(nóng)作物基因改良等領(lǐng)域發(fā)揮重要作用。傳統(tǒng)的生物實(shí)驗(yàn)進(jìn)行功能注釋的方法費(fèi)時(shí)且成本高，因此研究基于蛋白質(zhì)相互作用網(wǎng)絡(luò)內(nèi)的計(jì)算方法是當(dāng)前生物信息學(xué)家所面臨的重要問(wèn)題。

1 方法

1.1 蛋白質(zhì)相互作用網(wǎng)絡(luò)

隨著研究蛋白質(zhì)相互作用的高通量實(shí)驗(yàn)技術(shù)的發(fā)展，現(xiàn)在已可以獲取到大量的蛋白質(zhì)相互作用數(shù)據(jù)，這也讓我們可以使用統(tǒng)計(jì)學(xué)來(lái)對(duì)這些數(shù)據(jù)集進(jìn)行數(shù)據(jù)挖掘。我們以圖的思想，將這些復(fù)雜的蛋白質(zhì)之間相互作用關(guān)系數(shù)據(jù)構(gòu)建成為一張復(fù)雜的網(wǎng)絡(luò)，稱為蛋白質(zhì)相互作用網(wǎng)絡(luò)（Protein-Protein Interaction Network,簡(jiǎn)稱PPI網(wǎng)絡(luò)），接著我們就能夠使用圖論以及復(fù)雜網(wǎng)絡(luò)等研究方法對(duì)其研究。蛋白質(zhì)相互作用網(wǎng)絡(luò)的定義為細(xì)胞內(nèi)所有蛋白質(zhì)中任意對(duì)蛋白質(zhì)之間可能發(fā)生的相互作用關(guān)系的完整集合。

圖1

圖1是一個(gè)蛋白質(zhì)相互作用網(wǎng)絡(luò)，我們通常將其看作為一個(gè)無(wú)向圖G（V，E），圖中每個(gè)節(jié)點(diǎn)v表示一個(gè)蛋白質(zhì)，而每條連接兩個(gè)節(jié)點(diǎn)的邊e表示蛋白質(zhì)與蛋白質(zhì)之間的相互作用關(guān)系，在根據(jù)具體研究需要時(shí)，有時(shí)會(huì)給邊分配權(quán)值變?yōu)橛袡?quán)圖，此時(shí)邊的權(quán)值代表兩個(gè)蛋白質(zhì)之間作用關(guān)系的強(qiáng)度。

1.2 中心接近度

在現(xiàn)實(shí)中，我們經(jīng)常會(huì)遇到求兩個(gè)點(diǎn)之間最短路徑的問(wèn)題，但也有這樣實(shí)際生活場(chǎng)景，例如要建造一個(gè)大型的娛樂(lè)商場(chǎng)，希望光臨的顧客到達(dá)這個(gè)商場(chǎng)的距離都可以盡可能地短。這個(gè)就涉及到接近中心性的概念，接近中心性的值為路徑長(zhǎng)度的倒數(shù)。

接近中心性需要考量每個(gè)結(jié)點(diǎn)到其他結(jié)點(diǎn)的最短路徑的平均長(zhǎng)度。也就是要計(jì)算的是到圖中其他節(jié)點(diǎn)的距離總和比較小，計(jì)算的是這個(gè)節(jié)點(diǎn)處于圖中間位置的程度。在一個(gè)復(fù)雜網(wǎng)絡(luò)里，接近中心性越高的節(jié)點(diǎn)，越趨向于整個(gè)圖的中心。

在蛋白質(zhì)相互作用網(wǎng)絡(luò)里，蛋白質(zhì)i的接近中心度定義為：

式中，N為蛋白質(zhì)節(jié)點(diǎn)i的鄰接節(jié)點(diǎn)，為蛋白質(zhì)節(jié)點(diǎn)i與蛋白質(zhì)節(jié)點(diǎn)j的最短路徑距離。

1.3 FP樹

關(guān)聯(lián)分析通常能夠用來(lái)挖掘出數(shù)據(jù)之間的聯(lián)系，其中最常用的方法就是關(guān)聯(lián)規(guī)則的挖掘。FP樹，又稱FP-growth算法就是關(guān)聯(lián)規(guī)則挖掘的常用方法之一。FP-growth算法的思路為，首先壓縮數(shù)據(jù)集，將數(shù)據(jù)集內(nèi)所有事務(wù)使用FP樹這樣的數(shù)據(jù)結(jié)構(gòu)進(jìn)行表示，接著使用遞歸的方法將頻繁項(xiàng)集依次分解為各自的子問(wèn)題進(jìn)行挖掘。

FP-growth算法步驟：

（1）FP樹的構(gòu)建

FP樹是一種前綴樹，每個(gè)節(jié)點(diǎn)有三個(gè)指針，分別指向父節(jié)點(diǎn)，子節(jié)點(diǎn)和鏈接指針。此外，數(shù)據(jù)結(jié)構(gòu)中還包含有一個(gè)頭指針表，頭指針表中記錄每個(gè)元素出現(xiàn)的第一個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)中的鏈接指針將所有相同的元素連接起來(lái)。

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

（2）挖掘頻繁項(xiàng)集

挖掘頻繁項(xiàng)集時(shí)，從單項(xiàng)集出發(fā)每次增加一個(gè)元素。對(duì)于每一個(gè)頻繁項(xiàng)集以前綴路徑構(gòu)造一棵FP樹，然后向當(dāng)前的頻繁項(xiàng)集中添加一個(gè)元素，然后以深度優(yōu)先的策略遞歸地進(jìn)行這個(gè)過(guò)程直到發(fā)現(xiàn)所有頻繁項(xiàng)集。

2 數(shù)據(jù)與實(shí)驗(yàn)

2.1 數(shù)據(jù)

我們用于實(shí)驗(yàn)的酵母細(xì)胞蛋白質(zhì)的相互作用數(shù)據(jù)來(lái)自于String數(shù)據(jù)庫(kù)（https://string-db.org/cgi/download.pl?UserId=OaGetiAwHwOi&sessionIdGoVW2b711k9A&species_text=Saccharomyces+cerevisiae），共有 6391個(gè)蛋白質(zhì)和2007134條相互作用信息。

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

2.2 實(shí)驗(yàn)過(guò)程

（1）計(jì)算蛋白質(zhì)相關(guān)度閾值

為了提高預(yù)測(cè)的精度，首先對(duì)蛋白質(zhì)相互作用網(wǎng)絡(luò)內(nèi)的蛋白質(zhì)進(jìn)行分類，并計(jì)算相關(guān)性的閾值。

依照接近中心度公式，計(jì)算整個(gè)網(wǎng)絡(luò)內(nèi)每個(gè)節(jié)點(diǎn)的接近中心度，使用整個(gè)網(wǎng)絡(luò)內(nèi)所有節(jié)點(diǎn)計(jì)算中心度的平均值作為篩選閾值，將蛋白質(zhì)分為高相關(guān)度低相關(guān)度兩類。

（2）修剪子圖

使用與待預(yù)測(cè)蛋白質(zhì)節(jié)點(diǎn)所對(duì)應(yīng)相關(guān)度的蛋白質(zhì)節(jié)點(diǎn)組成新的蛋白質(zhì)相互作用網(wǎng)絡(luò)，對(duì)網(wǎng)絡(luò)內(nèi)的每條邊計(jì)算其邊聚數(shù)系數(shù)，如果邊聚數(shù)系數(shù)小于對(duì)應(yīng)的閾值，則將其刪除，最后形成一張新的子圖。

（3）挖掘最大頻繁項(xiàng)集預(yù)測(cè)蛋白質(zhì)功能

在修建過(guò)的子圖里，找到需要預(yù)測(cè)的蛋白質(zhì)節(jié)點(diǎn)的所有鄰接節(jié)點(diǎn)，使用FP-growth算法計(jì)算這些蛋白質(zhì)節(jié)點(diǎn)功能的最大頻繁項(xiàng)集，求得結(jié)果作為預(yù)測(cè)蛋白質(zhì)的功能集合。

2.3 結(jié)果分析

為了測(cè)試和對(duì)比我們的是實(shí)驗(yàn)結(jié)果，我們使用信息檢索領(lǐng)域兩個(gè)常用的評(píng)價(jià)指標(biāo)，準(zhǔn)確率和召回率，定義如下：

其中TP代表真陽(yáng)性、FP代表假陽(yáng)性、FN代表假陰性。

我們將計(jì)算出的兩個(gè)結(jié)果與其他兩種常用算法進(jìn)行比較，結(jié)果如圖2所示，可看出在高相關(guān)度下使用FP樹進(jìn)行頻繁項(xiàng)集挖掘預(yù)測(cè)可以提高蛋白質(zhì)功能預(yù)測(cè)的準(zhǔn)確率。

3 討論

本文研究的是在蛋白質(zhì)相互作用網(wǎng)絡(luò)里對(duì)未注釋的蛋白質(zhì)進(jìn)行功能預(yù)測(cè)。提出的方法是使用待預(yù)測(cè)蛋白質(zhì)在網(wǎng)絡(luò)中的鄰接節(jié)點(diǎn)進(jìn)行關(guān)聯(lián)規(guī)則挖掘。在關(guān)聯(lián)分析之前，首先使用復(fù)雜網(wǎng)絡(luò)里接近中心度的思想計(jì)算網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)的中心性，并計(jì)算出閾值，使用閾值對(duì)蛋白質(zhì)節(jié)點(diǎn)分類并對(duì)網(wǎng)絡(luò)去邊。之后使用FP樹來(lái)挖掘出鄰接節(jié)點(diǎn)的最大頻繁項(xiàng)集。最終通過(guò)實(shí)驗(yàn)證明，該算法能夠提高蛋白質(zhì)的功能預(yù)測(cè)精度。

圖2

參考文獻(xiàn)：

[1]李錦澤，葉曉俊.關(guān)聯(lián)規(guī)則挖掘算法研究現(xiàn)狀[J].計(jì)算機(jī)技術(shù)與應(yīng)用進(jìn)展，2007.

[2]王淑琴.機(jī)器學(xué)習(xí)方法及其在生物信息學(xué)領(lǐng)域中的應(yīng)用[D].吉林：吉林大學(xué)，2009