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

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

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

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

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

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

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

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

0 引 言

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

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

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

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

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

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

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

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

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條相互作用對。

筆者認(rèn)為互作網(wǎng)絡(luò)中數(shù)據(jù)源Data 1中的蛋白質(zhì)是已知功能的蛋白質(zhì), 而數(shù)據(jù)源Data 2中的蛋白質(zhì)是未知功能的, 在GO網(wǎng)站下載到了所有物種的功能注釋文件, 對數(shù)據(jù)源Data 1中的蛋白質(zhì)到GO下載到的注釋文件中查找它們的功能并且對其功能進(jìn)行了統(tǒng)計(jì), 取出了它們共同擁有的功能最多的前16個(gè)。根據(jù)這些功能類, 對數(shù)據(jù)源Data 2中數(shù)據(jù)進(jìn)行了處理, 留下有互作關(guān)系的兩個(gè)蛋白質(zhì)都至少有16個(gè)功能類中的一個(gè)互作關(guān)系, 并且對Data2中各個(gè)功能類中注釋信息所包含的蛋白質(zhì)數(shù)量進(jìn)行了分析統(tǒng)計(jì), 見圖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)開始游走一張圖, 從任意一個(gè)起始點(diǎn)開始, 以一定的概率pt通過邊隨機(jī)的移動到這個(gè)頂點(diǎn)的鄰居頂點(diǎn)上, 每次游走后得出一個(gè)概率分布pt+1,pt+1體現(xiàn)了圖中起始點(diǎn)隨機(jī)的移動到與它相鄰的各頂點(diǎn)的概率, 然后把pt+1的值賦給pt當(dāng)作下一次隨機(jī)移動的輸入并且重復(fù)執(zhí)行這個(gè)經(jīng)過。在符合特殊的條件時(shí),pt與pt+1的變化值會趨于收斂的狀態(tài), 在這個(gè)狀態(tài)下得到一個(gè)穩(wěn)定的概率分布。

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

(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間沒有互作關(guān)系。

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

(2)

r表示粒子每次游走時(shí)回到初始位置的概率。越接近 0, 隨機(jī)游走過程越能體現(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)過第t+1次游走后,粒子在各個(gè)蛋白質(zhì)處出現(xiàn)的概率。經(jīng)過多次游走, 粒子在各蛋白質(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ù)測

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

提取注釋模式可分為：①在構(gòu)建的蛋白質(zhì)相互作用網(wǎng)絡(luò)上執(zhí)行隨機(jī)游走算法, 經(jīng)過多次迭代后得到最終的穩(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)向量來表示蛋白質(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ò)見圖2, 白色的圓表示未知功能的蛋白質(zhì), 藍(lán)色的圓表示已知功能的蛋白質(zhì), 方框中為蛋白質(zhì)所具有的功能, 邊上的權(quán)值Sij表示節(jié)點(diǎn)i到節(jié)點(diǎn)j的相近度。在對未知功能蛋白質(zhì)提取注釋模式時(shí), 根據(jù)與未知功能的蛋白質(zhì)相鄰的已知功能的蛋白質(zhì)的功能來提該蛋白質(zhì)的注釋模式。

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

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

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

(4)

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

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

(5)

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

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

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

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

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

圖3 不同k值預(yù)測出蛋白質(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ù)測出的蛋白質(zhì)的功能的個(gè)數(shù)。由圖4可見，當(dāng)k=10, 兩種算法預(yù)測出的功能個(gè)數(shù)都是最多的,因此在之后的實(shí)驗(yàn)中取值k=10。

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

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

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

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

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

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

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

由圖7可見，換了預(yù)測集之后的結(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ì)來預(yù)測這些蛋白質(zhì)的功能。 這1/7蛋白質(zhì)共有2 960個(gè)功能, 用4組評價(jià)指標(biāo)判斷k在不同取值下對蛋白質(zhì)功能預(yù)測準(zhǔn)確性的影響，結(jié)果見圖8。

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

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

大網(wǎng)絡(luò)上對多標(biāo)簽的K近鄰算法與單標(biāo)簽的算法進(jìn)行了比較, 見圖9。 從標(biāo)簽的K近鄰算法所得到的結(jié)果要明顯優(yōu)于單標(biāo)簽的K近鄰算法。 經(jīng)過實(shí)驗(yàn)驗(yàn)證, 證實(shí)本文算法能夠有效地預(yù)測出蛋白質(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)了對未知功能的蛋白質(zhì)的功能預(yù)測, 在完成這項(xiàng)工作的過程中,整合多個(gè)相互作用數(shù)據(jù)庫中的數(shù)據(jù), 利用一型糖尿病通路數(shù)據(jù), 把相互作用數(shù)據(jù)庫中與一型糖尿病通路數(shù)據(jù)有互作關(guān)系的數(shù)據(jù)取出來, 實(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ù)測。

利用K近鄰算法, 把已知功能的蛋白質(zhì)的注釋模式分為訓(xùn)練樣本集, 未知功能的蛋白質(zhì)的注釋模式分為待測樣本集, 通過把待測樣本集中的注釋模式與訓(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ī)視覺、數(shù)字圖像處理和生物信息技術(shù)，Email: majiquan@hlju.edu.cn。

TP311.13

A

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