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

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

1、一種基于層次圖聚類的蛋白質(zhì)復合體檢測算法楊貴山西大學計算機與信息技術學院蛋白質(zhì)復合物在生物生命活動屮扮演著重要作用，棊于蛋Q質(zhì)互作用(PPI,Protein-ProteinInteraction)網(wǎng)絡進行復合物檢測是當前的一個研光熱點.針對此，提出了一種基于層次圖聚類的蛋白質(zhì)復合物檢測算法，其中結合網(wǎng)絡拓撲結構和蛋白質(zhì)復合物信息，給出一種網(wǎng)絡結點的權重定義方式;邊在蛋白質(zhì)互作用網(wǎng)絡的拓撲屬性與層次圖聚類算法相結合，提出了一種基于層次圖聚類算法的蛋內(nèi)質(zhì)復合體識別算法IIGCD(HierarchyGraphClusteringbasedmethodforProteinComplexesDisc

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

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

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

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

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

7、rity圖2HGCD算法在Karate和benchmark網(wǎng)絡上的聚類結果Fig.2TheclusteringresultsofIIGCDalgorithmonKarateandbenchmarknetworks卜載原圖選擇較大的網(wǎng)絡benchmark網(wǎng)絡進行實驗，該算法將網(wǎng)絡分成了4類并在平臺上對其進行可視化結果如圖2(b)所示.在Uetz釀灑酵母蛋白質(zhì)互作用網(wǎng)絡上的分類結果如圖3所示，由于該網(wǎng)絡是非連通圖，且連通分支較多，所以聚類個數(shù)較多.4結論基于網(wǎng)絡拓撲結構在蛋白質(zhì)互作用網(wǎng)絡中進行網(wǎng)絡復合體檢測是復雜網(wǎng)絡領域的研究熱點之一，網(wǎng)絡邊的關鍵性與其拓撲結構特征密切相關，定義合理的邊拓撲屬

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