馬吉權(quán), 賈翠翠，張軍杰

(1.黑龍江大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院,哈爾濱 150080;2.山東航天電子技術(shù)研究所，山東 煙臺(tái) 264670)

基于隨機(jī)游走的蛋白質(zhì)功能預(yù)測(cè)算法設(shè)計(jì)與實(shí)現(xiàn)

馬吉權(quán)1, 賈翠翠1，張軍杰2

(1.黑龍江大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院,哈爾濱 150080;2.山東航天電子技術(shù)研究所，山東 煙臺(tái) 264670)

在構(gòu)建蛋白質(zhì)相互作用網(wǎng)絡(luò)時(shí)從通路數(shù)據(jù)出發(fā), 利用通路數(shù)據(jù)整合蛋白質(zhì)相互作用網(wǎng)絡(luò)。提出了一個(gè)基于隨機(jī)游走的蛋白質(zhì)功能預(yù)測(cè)方法, 在該算法中把已知功能的蛋白質(zhì)當(dāng)作起始點(diǎn), 對(duì)于隨機(jī)游走在蛋白質(zhì)互作網(wǎng)絡(luò)中產(chǎn)生的鄰居信息, 轉(zhuǎn)換為注釋模式信息, 并根據(jù)已知功能的蛋白質(zhì)的功能來(lái)提取未知功能蛋白質(zhì)的注釋模式。利用傳統(tǒng)的K近鄰算法從訓(xùn)練樣本集中找到未知功能蛋白質(zhì)的k個(gè)最近鄰。最后, 結(jié)合多標(biāo)簽分類的K近鄰算法, 統(tǒng)計(jì)k個(gè)近鄰中蛋白質(zhì)的功能類數(shù)目, 基于最大后驗(yàn)概率預(yù)測(cè)未知功能蛋白質(zhì)屬于的功能標(biāo)簽類。通過(guò)在構(gòu)建蛋白質(zhì)互作網(wǎng)絡(luò)進(jìn)行實(shí)驗(yàn), 結(jié)果表明提出的方案能夠有效地進(jìn)行蛋白質(zhì)功能預(yù)測(cè)。

蛋白質(zhì)功能預(yù)測(cè)；蛋白質(zhì)-蛋白質(zhì)相互作用網(wǎng)絡(luò)；隨機(jī)游走；蛋白質(zhì)功能注釋；K近鄰；多標(biāo)簽分類

0 引 言

近年來(lái),基于高通量技術(shù)酵母雙雜交[1]實(shí)驗(yàn), 大量的蛋白質(zhì)相互作用網(wǎng)絡(luò)被構(gòu)建并用于蛋白質(zhì)功能的預(yù)測(cè)。一般認(rèn)為, 蛋白質(zhì)相互作用網(wǎng)絡(luò)中相鄰的蛋白質(zhì)表現(xiàn)類似的功能, 提出了很多基于蛋白質(zhì)相互作用網(wǎng)絡(luò)的蛋白質(zhì)功能預(yù)測(cè)方法[2]，比如多標(biāo)簽分類算法[3]、半監(jiān)督學(xué)習(xí)[4]等方法。也有學(xué)者提出了基于隨機(jī)游走的蛋白質(zhì)功能預(yù)測(cè)方法[5], 解決了相互作用數(shù)據(jù)的功能分布和相互作用網(wǎng)絡(luò)的全局拓?fù)浣Y(jié)構(gòu)問(wèn)題。隨機(jī)游走算法綜合了網(wǎng)絡(luò)的全局和局部拓?fù)浣Y(jié)構(gòu)信息, 度量未知功能的蛋白質(zhì)和網(wǎng)絡(luò)中其他蛋白質(zhì)的關(guān)聯(lián)程度。

到目前, 人們通過(guò)實(shí)驗(yàn)方法已經(jīng)確定了蛋白質(zhì)間的一些相互作用, 根據(jù)這些相互作用建立了一些蛋白質(zhì)相互作用數(shù)據(jù)庫(kù), 并了解相互作用的細(xì)節(jié), 累積了一些蛋白質(zhì)相互作用有關(guān)的專業(yè)知識(shí)。但是, 還不能夠構(gòu)建完整精確的蛋白質(zhì)相互作用網(wǎng)絡(luò), 如何利用已有的數(shù)據(jù)預(yù)測(cè)出未知的蛋白質(zhì)相互作用, 以及有效地分析蛋白質(zhì)相互作用網(wǎng)絡(luò), 從而從更深層次了解蛋白質(zhì)的功能, 成為蛋白質(zhì)組學(xué)研究的一個(gè)重要問(wèn)題。根據(jù)蛋白質(zhì)相互作用和蛋白質(zhì)功能預(yù)測(cè)問(wèn)題, 通過(guò)整合一型糖尿病數(shù)據(jù)和BioGrid[6]數(shù)據(jù)庫(kù)下載到的數(shù)據(jù)構(gòu)建了一個(gè)蛋白質(zhì)相互作用網(wǎng)絡(luò), 在相互作用網(wǎng)絡(luò)上實(shí)現(xiàn)了隨機(jī)游走算法, 結(jié)合K近鄰算法實(shí)現(xiàn)了蛋白質(zhì)功能的預(yù)測(cè)。

1 數(shù)據(jù)的獲取與處理

盡管有許多預(yù)測(cè)蛋白質(zhì)功能的方法,但大多數(shù)都只是使用了一種數(shù)據(jù), 而隨著研究的深入, 越來(lái)越多的人把其它數(shù)據(jù)信息融合到相互作用網(wǎng)絡(luò)從而實(shí)現(xiàn)蛋白質(zhì)的功能注釋與預(yù)測(cè)。根據(jù)一型糖尿病通路數(shù)據(jù)構(gòu)建一個(gè)蛋白質(zhì)相互作用網(wǎng)絡(luò), 目的是讓整個(gè)網(wǎng)絡(luò)的功能都是相關(guān)的, 從而提高預(yù)測(cè)的準(zhǔn)確性。

1.1 數(shù)據(jù)的獲取

本文主要對(duì)一型糖尿病蛋白質(zhì)進(jìn)行分析, 并根據(jù)一型糖尿病數(shù)據(jù)構(gòu)建了蛋白質(zhì)相互作用網(wǎng)絡(luò)。注釋數(shù)據(jù)是從GO網(wǎng)站下載得到的所有物種的注釋信息, 采用GO功能注釋[7]格式對(duì)蛋白質(zhì)進(jìn)行功能注釋。

Data 1: 來(lái)源于一型糖尿病的通路數(shù)據(jù), 手工收集到了與一型糖尿病相關(guān)的202個(gè)蛋白質(zhì)。

Data 2: 從BioGrid數(shù)據(jù)庫(kù)下載得到的蛋白質(zhì)相互作用數(shù)據(jù), 其版本號(hào)為2.0.63。該數(shù)據(jù)集共包含336 168條蛋白質(zhì)相互作用數(shù)據(jù)。BioGrid由酵母、線蟲(chóng)、果蠅以及人類蛋白質(zhì)相互作用共4個(gè)子數(shù)據(jù)庫(kù)組成。

1.2 數(shù)據(jù)的整合

筆者在下載到的BioGrid數(shù)據(jù)表中找到了122個(gè)一型糖尿病蛋白質(zhì)相關(guān)的相互作用關(guān)系。在刪除自身相互作用和重復(fù)數(shù)據(jù)后, 構(gòu)建了蛋白質(zhì)相互作用網(wǎng)絡(luò)。發(fā)現(xiàn)在大的網(wǎng)絡(luò)外還有一些小的相互作用關(guān)系, 在刪除這些互作關(guān)系數(shù)據(jù)后，最終得到了蛋白質(zhì)相互作用數(shù)據(jù)包括1 093個(gè)蛋白質(zhì)和1 708條相互作用對(duì)。

筆者認(rèn)為互作網(wǎng)絡(luò)中數(shù)據(jù)源Data 1中的蛋白質(zhì)是已知功能的蛋白質(zhì), 而數(shù)據(jù)源Data 2中的蛋白質(zhì)是未知功能的, 在GO網(wǎng)站下載到了所有物種的功能注釋文件, 對(duì)數(shù)據(jù)源Data 1中的蛋白質(zhì)到GO下載到的注釋文件中查找它們的功能并且對(duì)其功能進(jìn)行了統(tǒng)計(jì), 取出了它們共同擁有的功能最多的前16個(gè)。根據(jù)這些功能類, 對(duì)數(shù)據(jù)源Data 2中數(shù)據(jù)進(jìn)行了處理, 留下有互作關(guān)系的兩個(gè)蛋白質(zhì)都至少有16個(gè)功能類中的一個(gè)互作關(guān)系, 并且對(duì)Data2中各個(gè)功能類中注釋信息所包含的蛋白質(zhì)數(shù)量進(jìn)行了分析統(tǒng)計(jì), 見(jiàn)圖1。

圖1 各個(gè)功能類所注釋的蛋白質(zhì)的數(shù)量Fig.1 Number of protein of function annotations

2 基于蛋白質(zhì)相互作用網(wǎng)絡(luò)的隨機(jī)游走算法的設(shè)計(jì)與實(shí)現(xiàn)

隨機(jī)游走模型的思想是[8]: 粒子從一個(gè)或若干個(gè)頂點(diǎn)開(kāi)始游走一張圖, 從任意一個(gè)起始點(diǎn)開(kāi)始, 以一定的概率pt通過(guò)邊隨機(jī)的移動(dòng)到這個(gè)頂點(diǎn)的鄰居頂點(diǎn)上, 每次游走后得出一個(gè)概率分布pt+1,pt+1體現(xiàn)了圖中起始點(diǎn)隨機(jī)的移動(dòng)到與它相鄰的各頂點(diǎn)的概率, 然后把pt+1的值賦給pt當(dāng)作下一次隨機(jī)移動(dòng)的輸入并且重復(fù)執(zhí)行這個(gè)經(jīng)過(guò)。在符合特殊的條件時(shí),pt與pt+1的變化值會(huì)趨于收斂的狀態(tài), 在這個(gè)狀態(tài)下得到一個(gè)穩(wěn)定的概率分布。

從形式上看, 隨機(jī)游走重新啟動(dòng)被定義為：

(1)

其中,W是列規(guī)范化圖的鄰接矩陣, 表示蛋白質(zhì)相互作用網(wǎng)絡(luò)的相互作用關(guān)系, 矩陣W中的元素wij表示蛋白質(zhì)i和j的相互作用關(guān)系,d(V)表示與蛋白質(zhì)i有相互作用的蛋白質(zhì)的個(gè)數(shù)。wij=1/d(V)表示蛋白質(zhì)i和j間存在某種相互作用關(guān)系,wij=0表示蛋白質(zhì)i和j間沒(méi)有互作關(guān)系。

用W=(wij),i,j∈V表示鄰接矩陣,wij代表W中的每一個(gè)元素, 其中

(2)

r表示粒子每次游走時(shí)回到初始位置的概率。越接近 0, 隨機(jī)游走過(guò)程越能體現(xiàn)圍繞起始點(diǎn)的網(wǎng)絡(luò)全局拓?fù)涮匦? 值越接近1, 則越能體現(xiàn)網(wǎng)絡(luò)局部結(jié)構(gòu)性質(zhì)。p0為n×1的向量, 表示粒子隨機(jī)游走的初始狀態(tài),將網(wǎng)絡(luò)中已知功能的蛋白質(zhì)的初始值設(shè)為相等的值, 并且所有這些值的和為1, 其余未知功能的蛋白質(zhì)均為0。pt是一個(gè)向量, 它保存節(jié)點(diǎn)i在t時(shí)刻的概率。

pt+1是經(jīng)過(guò)第t+1次游走后,粒子在各個(gè)蛋白質(zhì)處出現(xiàn)的概率。經(jīng)過(guò)多次游走, 粒子在各蛋白質(zhì)處出現(xiàn)的概率將趨于穩(wěn)定, 根據(jù)在穩(wěn)定狀態(tài)概率向量p∞的值分別排列未注釋功能的蛋白質(zhì)。p∞的值是在向量pt和向量pt+1之間的差距小于10-6時(shí)獲得的。p∞與蛋白質(zhì)相互作用網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)緊密相關(guān), 能夠度量已知功能的蛋白質(zhì)與相互作用網(wǎng)絡(luò)中未知功能的蛋白質(zhì)間的關(guān)系, 稱穩(wěn)態(tài)分布下概率值為起始蛋白質(zhì)的全局鄰居或鄰居模式。

3 基于鄰居模式的蛋白質(zhì)功能預(yù)測(cè)

傳統(tǒng)的預(yù)測(cè)蛋白質(zhì)功能的方法都是假設(shè)：在相互作用網(wǎng)絡(luò)中拓?fù)渚嚯x較近的蛋白質(zhì)更傾向于具有相似的功能[9]。并沒(méi)有利用到蛋白質(zhì)的注釋信息來(lái)對(duì)蛋白質(zhì)進(jìn)行功能注釋, 因此, 假設(shè)功能相似的蛋白質(zhì)具有相似的注釋模式, 充分考量了蛋白質(zhì)注釋模式的相似性對(duì)蛋白質(zhì)功能注釋的影響。在蛋白質(zhì)相互作用網(wǎng)絡(luò)中, 考慮的范圍不僅是相鄰的蛋白質(zhì), 而是整個(gè)網(wǎng)絡(luò)[10], 通過(guò)與已經(jīng)注釋的蛋白質(zhì)的注釋模式進(jìn)行比較來(lái)預(yù)測(cè)未知蛋白質(zhì)的功能。如果兩個(gè)蛋白質(zhì)的注釋模式相似, 則這兩個(gè)蛋白質(zhì)就具有相似的功能。

提取注釋模式可分為：①在構(gòu)建的蛋白質(zhì)相互作用網(wǎng)絡(luò)上執(zhí)行隨機(jī)游走算法, 經(jīng)過(guò)多次迭代后得到最終的穩(wěn)態(tài)向量, 即目標(biāo)節(jié)點(diǎn)的全局鄰居；②把相互作用網(wǎng)絡(luò)的特征向量, 轉(zhuǎn)換為基于功能的特征向量, 也就是注釋模式。

在互作網(wǎng)絡(luò)中蛋白質(zhì)的功能與其相鄰的蛋白質(zhì)的功能是相似的, 因此, 用執(zhí)行隨機(jī)游走算法后得到的穩(wěn)態(tài)向量來(lái)表示蛋白質(zhì)的注釋環(huán)境Si,i∈[1,n], 即

(3)

表示以i點(diǎn)為起始點(diǎn), 執(zhí)行隨機(jī)游走算法后得到穩(wěn)態(tài)向量后, 蛋白質(zhì)i到全局網(wǎng)絡(luò)其他蛋白質(zhì)的親和向量。

相互作用網(wǎng)絡(luò)見(jiàn)圖2, 白色的圓表示未知功能的蛋白質(zhì), 藍(lán)色的圓表示已知功能的蛋白質(zhì), 方框中為蛋白質(zhì)所具有的功能, 邊上的權(quán)值Sij表示節(jié)點(diǎn)i到節(jié)點(diǎn)j的相近度。在對(duì)未知功能蛋白質(zhì)提取注釋模式時(shí), 根據(jù)與未知功能的蛋白質(zhì)相鄰的已知功能的蛋白質(zhì)的功能來(lái)提該蛋白質(zhì)的注釋模式。

圖2 執(zhí)行隨機(jī)游走算法后蛋白質(zhì)相互作用網(wǎng)絡(luò)示意圖Fig.2 Diagram of the protein interaction network after random walk

圖2是鄰居模式轉(zhuǎn)換為注釋模式的過(guò)程, 圖2為隨機(jī)游走算法以蛋白質(zhì)4為起始點(diǎn)執(zhí)行的結(jié)果, 鄰居模式為(0.13, 0.04, 0.04)分別對(duì)應(yīng)(5, 9,11)號(hào)蛋白質(zhì), 蛋白質(zhì)5具有功能A、B, 蛋白質(zhì)11具有功能B、C, 蛋白質(zhì)9具有功能C、D。通過(guò)對(duì)這些功能對(duì)應(yīng)的權(quán)值進(jìn)行求和, 得到向量(0.13, 0.17, 0.08, 0.04), 分別對(duì)應(yīng)功能A,B,C,D。之后對(duì)得到的向量進(jìn)行歸一化, 得到蛋白質(zhì)4的功能注釋模式

在蛋白質(zhì)i的功能注釋模式中, 其中功能a所對(duì)應(yīng)的概率值為：

(4)

當(dāng)?shù)鞍踪|(zhì)j具有功能a時(shí),eja的值為1, 否則為0。

所有的功能類對(duì)應(yīng)的概率向量為：

(5)

4 多標(biāo)簽學(xué)習(xí)的K近鄰算法

該算法的思想是[11]：對(duì)于某一個(gè)測(cè)試樣本, 首先在訓(xùn)練集中找到它的k個(gè)最近鄰樣本點(diǎn)[12], 然后根據(jù)訓(xùn)練樣本集中的統(tǒng)計(jì)信息, 比如這k個(gè)最近鄰樣本屬于任意標(biāo)簽的樣本個(gè)數(shù), 以及在訓(xùn)練過(guò)程中這k個(gè)最近鄰樣本屬于任意標(biāo)簽的樣本個(gè)數(shù)和中心樣本點(diǎn)是不是含有該標(biāo)簽等, 把這些信息與條件概率知識(shí)及貝葉斯算法結(jié)合起來(lái), 從而預(yù)測(cè)待測(cè)樣本的標(biāo)簽集。

5 實(shí)驗(yàn)與結(jié)果分析

用已知功能的蛋白質(zhì)組成了一個(gè)小網(wǎng)絡(luò), 這個(gè)網(wǎng)絡(luò)用來(lái)驗(yàn)證使用。在這個(gè)小網(wǎng)絡(luò)中一共有52個(gè)蛋白質(zhì), 取出1/7蛋白質(zhì)作為未知的,用網(wǎng)絡(luò)中其它的已知功能的蛋白質(zhì)來(lái)預(yù)測(cè)這些蛋白質(zhì)的功能。 這1/7蛋白質(zhì)共有44個(gè)功能, 筆者首先實(shí)現(xiàn)了單標(biāo)簽K近鄰算法, 驗(yàn)證結(jié)果見(jiàn)圖3。

實(shí)現(xiàn)多標(biāo)簽的K近鄰算法, 并將其結(jié)果與單標(biāo)簽的結(jié)果進(jìn)行比較, 見(jiàn)圖4。 由圖4可見(jiàn), 多標(biāo)簽的K近鄰算法明顯優(yōu)于單標(biāo)簽的K近鄰算法。

圖3 不同k值預(yù)測(cè)出蛋白質(zhì)功能的個(gè)數(shù)Fig.3 Numbers of different k value to predict protein function

圖4 單標(biāo)簽K近鄰算法與多標(biāo)簽K近鄰算法的比較Fig.4 Comparison of single label and multiple labels K neighbor algorithm

在圖4中, 橫坐標(biāo)為k的取值, 縱坐標(biāo)為在k的取值下所預(yù)測(cè)出的蛋白質(zhì)的功能的個(gè)數(shù)。由圖4可見(jiàn)，當(dāng)k=10, 兩種算法預(yù)測(cè)出的功能個(gè)數(shù)都是最多的,因此在之后的實(shí)驗(yàn)中取值k=10。

用4組評(píng)價(jià)指標(biāo)判斷k在不同取值下對(duì)蛋白質(zhì)功能預(yù)測(cè)準(zhǔn)確性的影響,見(jiàn)圖5。

圖5 不同k值對(duì)算法性能的影響Fig.5 Influence of different k values

在提取注釋模式時(shí), 將此方法與傳統(tǒng)的方法進(jìn)行比較, 傳統(tǒng)的提取注釋模式的方法未考慮轉(zhuǎn)移概率對(duì)算法性能的影響, 只統(tǒng)計(jì)了與蛋白質(zhì)相關(guān)的已知蛋白質(zhì)的功能的個(gè)數(shù), 對(duì)比結(jié)果見(jiàn)圖6。

圖6 兩種提取注釋模式方法對(duì)比Fig.6 Comparison of two annotation methods

由圖6可見(jiàn)，所采用的提取注釋模式的方法要優(yōu)于傳統(tǒng)的方法。

在此算法中假設(shè)節(jié)點(diǎn)度數(shù)大的點(diǎn)在網(wǎng)絡(luò)中相對(duì)更重要一些, 也就是說(shuō)在網(wǎng)絡(luò)中如果這些相對(duì)重要的點(diǎn)為已知功能的蛋白質(zhì), 預(yù)測(cè)結(jié)果會(huì)更好。選擇了同樣大小的預(yù)測(cè)集, 只是在這個(gè)預(yù)測(cè)集中節(jié)點(diǎn)的度數(shù)都是相對(duì)較小的。原來(lái)的預(yù)測(cè)集是把節(jié)點(diǎn)的度數(shù)較大的點(diǎn)作為未知功能的蛋白質(zhì), 用這兩組預(yù)測(cè)集做實(shí)驗(yàn)進(jìn)行對(duì)比, 結(jié)果見(jiàn)圖7。

圖7 相同的網(wǎng)絡(luò)中不同的預(yù)測(cè)集結(jié)果對(duì)比Fig.7 Comparison of two different dataset in the same net

由圖7可見(jiàn)，換了預(yù)測(cè)集之后的結(jié)果要明顯優(yōu)于之前的結(jié)果。

用一型糖尿病構(gòu)建的網(wǎng)絡(luò)中實(shí)現(xiàn)本文算法, 在這個(gè)網(wǎng)絡(luò)中一共有911個(gè)蛋白質(zhì), 取出1/7蛋白質(zhì)做為未知的, 之后用網(wǎng)絡(luò)中其它的已知功能的蛋白質(zhì)來(lái)預(yù)測(cè)這些蛋白質(zhì)的功能。 這1/7蛋白質(zhì)共有2 960個(gè)功能, 用4組評(píng)價(jià)指標(biāo)判斷k在不同取值下對(duì)蛋白質(zhì)功能預(yù)測(cè)準(zhǔn)確性的影響，結(jié)果見(jiàn)圖8。

由圖8可見(jiàn)，當(dāng)k為400時(shí)各項(xiàng)指標(biāo)的值綜合表現(xiàn)最好。

圖8 不同k值對(duì)算法性能的影響Fig.8 Influence of different k values

大網(wǎng)絡(luò)上對(duì)多標(biāo)簽的K近鄰算法與單標(biāo)簽的算法進(jìn)行了比較, 見(jiàn)圖9。 從標(biāo)簽的K近鄰算法所得到的結(jié)果要明顯優(yōu)于單標(biāo)簽的K近鄰算法。 經(jīng)過(guò)實(shí)驗(yàn)驗(yàn)證, 證實(shí)本文算法能夠有效地預(yù)測(cè)出蛋白質(zhì)的功能。

圖9 單標(biāo)簽K近鄰算法與多標(biāo)簽K近鄰算法的比較Fig.9 Comparison of single label and multiple labels K neighbor algorithm

6 結(jié) 論

主要實(shí)現(xiàn)了對(duì)未知功能的蛋白質(zhì)的功能預(yù)測(cè), 在完成這項(xiàng)工作的過(guò)程中,整合多個(gè)相互作用數(shù)據(jù)庫(kù)中的數(shù)據(jù), 利用一型糖尿病通路數(shù)據(jù), 把相互作用數(shù)據(jù)庫(kù)中與一型糖尿病通路數(shù)據(jù)有互作關(guān)系的數(shù)據(jù)取出來(lái), 實(shí)現(xiàn)了隨機(jī)游走在蛋白質(zhì)互作網(wǎng)絡(luò)中的應(yīng)用, 以互作網(wǎng)絡(luò)中已知功能的蛋白質(zhì)為起始點(diǎn), 計(jì)算已知功能的蛋白質(zhì)與未知功能蛋白質(zhì)的關(guān)聯(lián)程度, 得到在穩(wěn)態(tài)分布下的概率向量, 即鄰居信息。把鄰居模式轉(zhuǎn)換成注釋模式, 利用已知功能的蛋白質(zhì)實(shí)現(xiàn)未知功能蛋白質(zhì)的功能的預(yù)測(cè)。

利用K近鄰算法, 把已知功能的蛋白質(zhì)的注釋模式分為訓(xùn)練樣本集, 未知功能的蛋白質(zhì)的注釋模式分為待測(cè)樣本集, 通過(guò)把待測(cè)樣本集中的注釋模式與訓(xùn)練樣本集中的進(jìn)行比較, 得到與之最近的k個(gè)。 利用多標(biāo)簽分類的KNN算法, 實(shí)現(xiàn)蛋白質(zhì)多標(biāo)簽的功能分類。

[1]Gavin A C, B?sche M, Krause R, et al.Functional organization of the yeast proteome by systematic analysis of protein complexes[J]. Nature, 2002, 415(6 868): 141-147.

[2]Vazquez A, Flammini A, Maritan A, et al.Global protein function prediction from protein-protein interaction networks[J]. Nature biotechnology, 2003, 21(6): 697-700.

[3]Borges H B, Nievola J C.Multi-Label Hierarchical Classification using a Competitive Neural Network for protein function prediction[C].Neural Networks (IJCNN), The 2012 International Joint Conference on，2012: 1-8.

[4] Jiang J Q, Mcquay L J. Predicting protein function by multi-label correlated semi-supervised learning[J]. Computational Biology and Bioinformatics, IEEE/ACM Transactions on, 2012, 9(4): 1 059-1 069.

[6] Chatr-aryamontri A, Breitkreutz B J, Heinicke S, et al. The Biogrid interaction database: 2013 update[J]. Nucleic acids research, 2013, 41(D1): D816-D823.

[7]Benso A, Di Carlo S, Politane G, et al. Combining homolog and motif similarity data with Gene Ontology relationships for protein function prediction[C].Bioinformatics and Biomedicine (BIBM), 2012 IEEE International Conference on. 2012: 1-4.

[8] Lei C, Ruan J. A random walk based approach for improving protein-protein interaction network and protein complex prediction[C]. Bioinformatics and Biomedicine (BIBM), 2012 IEEE International Conference on. 2012: 1-6.

[9] Li P, Heo L, Li M, et al. Protein function prediction using frequent patterns in protein-protein interaction networks[C].Fuzzy Systems and Knowledge Discovery (FSKD), 2011 Eighth International Conference on. 2011, 3: 1 616-1 620.

[10]Vazquez A, Flammini A, Maritan A, et al. Global protein function prediction from protein-protein interaction networks[J]. Nature biotechnology, 2003, 21(6): 697-700.

[11]Yu G, Rangwala H, Domeniconi C, et al.Protein Function Prediction using Multi-label Ensemble Classification[J]. IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), 2013, 10(4): 1-1.

[12]Kamakura N, Takahashi H, Nakamura K, et al. Protein function prediction based on k-cores of interaction networks[C].Bioinformatics and Biomedical Technology (ICBBT), 2010 International Conference on. 2010: 211-215.

Prediction of protein function based on random walk algorithm design and implementation

MA Ji-Quan1, JIA Cui-Cui1，ZHANG Jun-Jie2

(1.School of Computer Science and Technology,Heilongjiang University, Harbin 150080, China;2.Institute of Aerosprace Electronics Technology of Shandong,Yantai 264670,Shandong,China)

In the process of constructing the protein-protein interaction network is starting from the pathway data, data integration using pathway of protein interaction networks.A prediction method for protein function is presented based on random walk, in this algorithm, the proteins of known function as a starting point is provided, for the random walk in the protein interaction network of neighborhood information, annotation schema information is converted, and according to the known function protein function to extract the unknown function protein annotation mode.After, using the traditional KNN algorithm to find the unknown function protein theknearest neighbors from the training set.Last, combined with KNN algorithm for multi label classification, the maximum posteriori probability prediction function label unknown function protein is based.The experiments in which we construct protein interaction network, the results show that the proposed scheme can predict the protein function effectively.

prediction of protein function；protein-protein interaction networks；random walk；protein function annotation；KNN；multi-label classification

10.13524/j.2095-008x.2015.03.050

2015-08-16

黑龍江省自然科學(xué)基金資助項(xiàng)目(F201248)

馬吉權(quán)(1975-)，男，黑龍江伊春人，副教授，博士，碩士研究生導(dǎo)師，研究方向：計(jì)算機(jī)視覺(jué)、數(shù)字圖像處理和生物信息技術(shù)，Email: majiquan@hlju.edu.cn。

TP311.13

A

2095-008X(2015)03-0073-06