一種基于層次圖聚類的蛋白質(zhì)復(fù)合體檢測(cè)算法

《一種基于層次圖聚類的蛋白質(zhì)復(fù)合體檢測(cè)算法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫(kù)。

1、一種基于層次圖聚類的蛋白質(zhì)復(fù)合體檢測(cè)算法楊貴山西大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院蛋白質(zhì)復(fù)合物在生物生命活動(dòng)屮扮演著重要作用，棊于蛋Q質(zhì)互作用(PPI,Protein-ProteinInteraction)網(wǎng)絡(luò)進(jìn)行復(fù)合物檢測(cè)是當(dāng)前的一個(gè)研光熱點(diǎn).針對(duì)此，提出了一種基于層次圖聚類的蛋白質(zhì)復(fù)合物檢測(cè)算法，其中結(jié)合網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和蛋白質(zhì)復(fù)合物信息，給出一種網(wǎng)絡(luò)結(jié)點(diǎn)的權(quán)重定義方式;邊在蛋白質(zhì)互作用網(wǎng)絡(luò)的拓?fù)鋵傩耘c層次圖聚類算法相結(jié)合，提出了一種基于層次圖聚類算法的蛋內(nèi)質(zhì)復(fù)合體識(shí)別算法IIGCD(HierarchyGraphClusteringbasedmethodforProteinComplexesDisc

2、overy).在Utez釀酒酵母PPI網(wǎng)絡(luò)中進(jìn)行蛋白質(zhì)復(fù)合物識(shí)別結(jié)果表明，HGCD算法可以發(fā)現(xiàn)網(wǎng)絡(luò)中的蛋白質(zhì)復(fù)合體.關(guān)鍵詞：蛋白質(zhì)互作用網(wǎng)絡(luò);層次圖聚類;蛋白質(zhì)復(fù)合體;（v）定義為Nc（v）={u

3、（V，u）EE}，簡(jiǎn)記為Nv，其屮，ueNG（v）稱為v的相鄰節(jié)點(diǎn).結(jié)點(diǎn)的度記為kv.令，用[UL表示G的頂點(diǎn)子集U的導(dǎo)出子圖[9],在不發(fā)生混淆時(shí)，記為[U].節(jié)點(diǎn)v的k鄰域表示與節(jié)點(diǎn)v最短路徑長(zhǎng)度不大于k的節(jié)點(diǎn)子集，即2基于層次圖聚類的蛋白質(zhì)復(fù)合體檢測(cè)算法HGCD2.1網(wǎng)絡(luò)邊權(quán)重定義計(jì)算網(wǎng)絡(luò)閣中每條邊的權(quán)重是發(fā)現(xiàn)初始社區(qū)的基礎(chǔ)，使用公式（1）為網(wǎng)絡(luò)閣每條邊賦予權(quán)重：其屮，N,和比分別是結(jié)點(diǎn)i

4、和結(jié)點(diǎn)j的鄰居結(jié)點(diǎn)的集合，可以看出WnN」是結(jié)點(diǎn)i和結(jié)點(diǎn)j的公共鄰接點(diǎn).通過(guò)迭代更新邊權(quán)重，以使其充分反映鄰域拓?fù)浣Y(jié)構(gòu)的信息.根據(jù)公式（1），得到節(jié)點(diǎn)v的初始權(quán)重定義如公式（2）:第t次迭代過(guò)程中，邊（i，j）權(quán)重與節(jié)點(diǎn)v權(quán)重的計(jì)算方式為計(jì)算邊權(quán)重的算法流程如下：算法1:權(quán)重計(jì)算過(guò)程Weighing2.2發(fā)現(xiàn)初始社區(qū)完成計(jì)算邊權(quán)重W的工作之后，開(kāi)始進(jìn)行初始社區(qū)發(fā)現(xiàn)，發(fā)現(xiàn)初始社區(qū)算法流程如下：算法2:初始社區(qū)發(fā)現(xiàn)過(guò)程這里以Karate（跆拳道倶樂(lè)部）網(wǎng)絡(luò)為例，運(yùn)行初始社區(qū)發(fā)現(xiàn)過(guò)程，劃分了24個(gè)初始社區(qū)，如圖1所示.圖1貽拳道倶樂(lè)部初始社區(qū)發(fā)現(xiàn)結(jié)果Fig.1Theinitialcommunit

5、yfindingresultsofTaekwondoClub2.3合并初始社區(qū)對(duì)于初始社區(qū)，接下來(lái)根據(jù)最大的模塊性的目標(biāo)合并子社區(qū).公式（4）所示其中，EjQEi分別為社區(qū)CJnCj社區(qū)內(nèi)部邊的數(shù)量，m是圖中所有邊的數(shù)量，Ext：和Ext」分別表示連接到社區(qū)Cl和社區(qū)Cj的外部邊，Eij表示的是連接子社區(qū)Ci和子社區(qū)q之間的邊的數(shù)量.利用公式（4）判斷哪兩個(gè)社區(qū)合并將會(huì)增大模塊性.合并初始社區(qū)算法過(guò)程如下：算法3:合并初始社區(qū)過(guò)程3實(shí)驗(yàn)結(jié)果與分析將本文算法11GCD在Karate（貽拳道網(wǎng)絡(luò)）、dolphins（海豚網(wǎng)絡(luò)）、Benchmark（基準(zhǔn)圖網(wǎng)絡(luò)）上進(jìn)行社區(qū)發(fā)現(xiàn)，表1給出了實(shí)驗(yàn)數(shù)據(jù)

6、的基本信息，其中n表示網(wǎng)絡(luò)的結(jié)點(diǎn)數(shù)，modularity表示網(wǎng)纟各模塊性.在圖2給出了木文算法在跆拳道網(wǎng)絡(luò)和基準(zhǔn)圖網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果圖，可以看出該算法將Karate（跆拳道倶樂(lè)部）網(wǎng)絡(luò)分為了4個(gè)社區(qū)，每個(gè)社區(qū)的結(jié)點(diǎn)用不同的顏色顯示，算法將Karate（跆拳道俱樂(lè)部）劃分的4個(gè)社區(qū)的結(jié)果分別是:第0類:11個(gè)結(jié)點(diǎn)為1，2,3，4,8，12，13，14，18，20，22第1類：10個(gè)結(jié)點(diǎn)為9,10,15,16,19,21,23，31,33，34第2類:5個(gè)結(jié)點(diǎn)為5,6，7,11,17第3類:8個(gè)結(jié)點(diǎn)為24,25，26，27,28,29，30，32表1網(wǎng)絡(luò)模塊性Tab.1Networkmodula

7、rity圖2HGCD算法在Karate和benchmark網(wǎng)絡(luò)上的聚類結(jié)果Fig.2TheclusteringresultsofIIGCDalgorithmonKarateandbenchmarknetworks卜載原圖選擇較大的網(wǎng)絡(luò)benchmark網(wǎng)絡(luò)進(jìn)行實(shí)驗(yàn)，該算法將網(wǎng)絡(luò)分成了4類并在平臺(tái)上對(duì)其進(jìn)行可視化結(jié)果如圖2(b)所示.在Uetz釀灑酵母蛋白質(zhì)互作用網(wǎng)絡(luò)上的分類結(jié)果如圖3所示，由于該網(wǎng)絡(luò)是非連通圖，且連通分支較多，所以聚類個(gè)數(shù)較多.4結(jié)論基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)在蛋白質(zhì)互作用網(wǎng)絡(luò)中進(jìn)行網(wǎng)絡(luò)復(fù)合體檢測(cè)是復(fù)雜網(wǎng)絡(luò)領(lǐng)域的研究熱點(diǎn)之一，網(wǎng)絡(luò)邊的關(guān)鍵性與其拓?fù)浣Y(jié)構(gòu)特征密切相關(guān)，定義合理的邊拓?fù)鋵?/p>

8、性可以為復(fù)合物識(shí)別提供重要參考.本文提出Y網(wǎng)絡(luò)邊的鄰域重要度權(quán)重ELN,定義了網(wǎng)絡(luò)中相鄰節(jié)點(diǎn)對(duì)指定邊的重要性作為網(wǎng)絡(luò)邊權(quán)重的一個(gè)指標(biāo).利用層次圖聚類方法，在PPI網(wǎng)絡(luò)中進(jìn)行復(fù)合體檢測(cè)，可以有效的發(fā)現(xiàn)物種蛋白質(zhì)網(wǎng)絡(luò)中關(guān)于復(fù)合體的有用信息和結(jié)構(gòu).結(jié)合復(fù)雜網(wǎng)絡(luò)拓?fù)湫畔⑴c層次圖聚類方法，可以提高復(fù)合體識(shí)別的效率，針對(duì)此本文綜合考慮蛋白質(zhì)互作用網(wǎng)絡(luò)中的蛋白質(zhì)作用拓?fù)湫畔⒆R(shí)別其屮的蛋白質(zhì)復(fù)合物，提出丫棊于層次圖聚類的蛋白質(zhì)復(fù)合體識(shí)別