最小生成樹算法應(yīng)用于蛋白質(zhì)復(fù)合物識別實驗設(shè)計

梁 冰，張益嘉，呂嘉慶

（1.大連理工大學(xué) 創(chuàng)新創(chuàng)業(yè)學(xué)院，遼寧 大連 116024；2.大連理工大學(xué) 電子信息與電氣工程學(xué)部，遼寧 大連 116024）

算法基礎(chǔ)作為計算機(jī)專業(yè)的核心課程，是計算機(jī)專業(yè)人才培養(yǎng)的基石，從事計算機(jī)學(xué)科的信息處理、人工智能、數(shù)據(jù)庫、操作系統(tǒng)、圖形圖像等方面的研究，都離不開算法的應(yīng)用[1-2]。傳統(tǒng)的算法實驗課程內(nèi)容包括排序算法、樹的遍歷算法、圖的最短路算法等基礎(chǔ)算法[3-4]。

算法基礎(chǔ)是一門實踐性很強(qiáng)的課程，其教學(xué)不僅應(yīng)該注重學(xué)生對理論知識的理解，鍛煉學(xué)生的抽象思維和創(chuàng)造能力，還應(yīng)注重培養(yǎng)學(xué)生的實踐能力，而該課程實驗課是學(xué)生驗證、掌握和應(yīng)用算法理論的重要手段，也是影響整個課程教學(xué)質(zhì)量的重要因素。目前實驗課程存在的主要問題，一是傳統(tǒng)實驗的設(shè)計題目過于程式化，不能調(diào)動學(xué)生的主動性思維。一些學(xué)生僅僅是拿一些現(xiàn)成的程序來應(yīng)付實驗，不能達(dá)到實驗?zāi)康摹＞C合設(shè)計性和探索創(chuàng)新性實驗偏少，影響學(xué)生探討問題的積極性和創(chuàng)新能力培養(yǎng)，學(xué)生雖能完成實驗，但實踐工作量嚴(yán)重不足。二是理論和實際結(jié)合不緊密，學(xué)生在課堂上雖然掌握了很多概念和理論，但是涉及實際項目的設(shè)計開發(fā)，往往就不能將已學(xué)知識和實際問題聯(lián)系起來，對于算法設(shè)計和項目開發(fā)感到力不從心[5-7]。

根據(jù)前沿的研究熱點(diǎn)設(shè)計實驗內(nèi)容，能夠調(diào)動學(xué)生動手編程的熱情，還能使學(xué)生在學(xué)習(xí)經(jīng)典算法的同時，了解前沿研究熱點(diǎn)，擴(kuò)展知識面。

圖論是計算機(jī)科學(xué)中最重要的領(lǐng)域之一，很多實際問題都可以通過圖來建模，比如道路交通網(wǎng)、電網(wǎng)、通信網(wǎng)、水管網(wǎng)等。圖論中需要掌握的算法，包括：bellman-ford 算法、Dijkstra 算法和floyd-warshall 算法等3 種最短路算法；Prim 算法和Kruskal 算法2 種最小生成樹算法；Ford-Fulkerson 算法和Dinic 算法2 種網(wǎng)絡(luò)流算法；以及最小費(fèi)用最大流算法[8-9]等。掌握圖論的經(jīng)典算法，并能選擇和應(yīng)用其中的算法解決實際問題，是培養(yǎng)學(xué)生的主要目標(biāo)。本實驗項目就是為了實現(xiàn)這個目標(biāo)而設(shè)計的。

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

蛋白質(zhì)相互作用數(shù)據(jù)通常由蛋白質(zhì)-蛋白質(zhì)節(jié)點(diǎn)相互作用的蛋白質(zhì)網(wǎng)絡(luò)（protein-protein internet,PPI）表示，兩個節(jié)點(diǎn)之間的邊代表已知的兩種蛋白質(zhì)之間的相互作用。大多數(shù)蛋白質(zhì)只有作為蛋白質(zhì)復(fù)合物的一部分時，才具有生物活性。蛋白質(zhì)復(fù)合物是執(zhí)行復(fù)制、轉(zhuǎn)錄和基因表達(dá)等細(xì)胞功能的生物分子[10]。那么如何在PPI 網(wǎng)絡(luò)中定義哪一組蛋白質(zhì)屬于同一個蛋白質(zhì)的復(fù)合物，就成為一個問題。

近來人們花了很大精力去發(fā)現(xiàn)蛋白質(zhì)-蛋白質(zhì)相互作用中的蛋白質(zhì)復(fù)合物網(wǎng)絡(luò)，大規(guī)模費(fèi)時費(fèi)力地開展鑒定蛋白質(zhì)復(fù)合物實驗室實驗，如親和純化（AP）實驗和質(zhì)譜（MS）實驗[11]。為了減少實驗中繁瑣的試錯步驟，最近還出現(xiàn)了一些通過計算方法識別蛋白質(zhì)復(fù)合物的嘗試。這些研究方法大多依賴于這樣一種觀點(diǎn)，即同一復(fù)合物中的蛋白質(zhì)會有相對更多的相互作用。于是，這些研究方法根據(jù)不同的圖聚類算法，可以發(fā)現(xiàn)基于不同拓?fù)湫再|(zhì)，如密度、k 核、核附著生物分子的結(jié)構(gòu)和外圍等，目的是尋找PPI 網(wǎng)絡(luò)中的稠密子圖，這些方法給出了如何找到一個稠密子圖以及將節(jié)點(diǎn)聚集成稠密子圖的過程。因此，通過算法從網(wǎng)絡(luò)圖中識別蛋白質(zhì)復(fù)合物，是生物學(xué)與計算機(jī)交叉學(xué)科的研究熱點(diǎn)問題。

從蛋白質(zhì)相互作用關(guān)系網(wǎng)的定義可知，PPI 網(wǎng)絡(luò)完全符合圖論中無向圖（邊沒有方向的圖稱為無向圖）的定義，因此，如何選擇和應(yīng)用圖論中經(jīng)典算法解決蛋白質(zhì)復(fù)合物識別問題的實驗項目，具有前沿性和創(chuàng)新性，能夠培養(yǎng)學(xué)生科學(xué)研究的能力和解決實際問題的能力。

值得說明的是,不同分析方法基于不同的蛋白質(zhì)拓?fù)湫再|(zhì)，對同一種蛋白質(zhì)網(wǎng)絡(luò)使用不同分析方法會得到不同的分析結(jié)論，不同的分析方法也具有各自的分析特色。

2 蛋白質(zhì)關(guān)系網(wǎng)絡(luò)的拓?fù)涮卣?/h2>

蛋白質(zhì)相互作用網(wǎng)絡(luò)與其他生物實體一樣，缺乏自頂向下的設(shè)計。生物進(jìn)化的選擇性通過隨機(jī)事件，如個別基因的突變和基因復(fù)制，形成了蛋白質(zhì)網(wǎng)絡(luò)。因此，蛋白質(zhì)之間的聯(lián)系具有很大程度的隨機(jī)性，但有些聯(lián)系則是由進(jìn)化或功能設(shè)計原則和限制而產(chǎn)生的，具有非隨機(jī)性。

本文提出的應(yīng)用圖論中最小生成樹Prim 算法識別蛋白質(zhì)復(fù)合物的研究方法，是利用了蛋白質(zhì)相互作用網(wǎng)絡(luò)拓?fù)鋵W(xué)的以下3 個非隨機(jī)性特征。

2.1 網(wǎng)路節(jié)點(diǎn)的度

PPI 網(wǎng)絡(luò)的第一個非隨機(jī)拓?fù)涮卣魇枪?jié)點(diǎn)的度，有時也稱為連接度，即在給定的蛋白質(zhì)網(wǎng)絡(luò)中直接連接蛋白質(zhì)的數(shù)量。

雖然大多數(shù)蛋白質(zhì)與其他蛋白質(zhì)只有少量的相互作用，但也存在具有大量直接連接的蛋白質(zhì)節(jié)點(diǎn)，我們稱之為“樞紐”。這種網(wǎng)絡(luò)中連接最多的節(jié)點(diǎn)的度通常比網(wǎng)絡(luò)中節(jié)點(diǎn)的平均度大幾個數(shù)量級。 參與簡單任務(wù)的蛋白質(zhì)可能只需要幾個相互作用的伙伴，而那些蛋白質(zhì)“樞紐”則是用于更復(fù)雜和全局性任務(wù)的。

2.2 網(wǎng)絡(luò)直徑

蛋白質(zhì)相互作用網(wǎng)絡(luò)圖中，任意兩個節(jié)點(diǎn)之間距離的最大值叫做網(wǎng)絡(luò)直徑，而任意兩點(diǎn)之間的距離為這兩個節(jié)點(diǎn)的最短路徑的長度。

這里還涉及連通圖和非連通圖的概念。如果蛋白質(zhì)網(wǎng)絡(luò)圖中的任意一對頂點(diǎn)都是連通的，則稱此網(wǎng)絡(luò)圖叫做連通圖，反之則叫做非連通圖。

因為非連通圖的網(wǎng)絡(luò)直徑為所有連通子圖的網(wǎng)絡(luò)直徑的最大值，因此非連通圖的網(wǎng)絡(luò)直徑是無窮大的。

2.3 特征路徑長度

蛋白質(zhì)相互作用網(wǎng)絡(luò)圖中，所有最短路徑長度的平均值稱為特征路徑長度。

特征路徑長度描述了網(wǎng)絡(luò)中節(jié)點(diǎn)的分離程度，且0≤特征路徑長度≤1。當(dāng)特征路徑長度為1 時，表示該P(yáng)PI 為連通圖，當(dāng)為0 時表示該P(yáng)PI 圖是完全離散的，特征路徑長度越接近1，表示PPI 的連通性越好。

3 圖論最小生成樹Prim 算法

本研究基于蛋白質(zhì)相互作用網(wǎng)絡(luò)的非隨機(jī)拓?fù)涮卣鳎瑧?yīng)用圖論中最小生成樹Prim 算法進(jìn)行蛋白質(zhì)復(fù)合物識別。本研究方法的最大特點(diǎn)是能有效提升蛋白質(zhì)復(fù)合物識別的性能。

那么什么是最小生成樹呢？給定一個無向圖,如蛋白質(zhì)PPI 圖，如果其某個子圖中任意兩個節(jié)點(diǎn)都互相連通，并且呈現(xiàn)一棵樹的結(jié)構(gòu)，那么這個PPI 圖就稱為具有生成樹結(jié)構(gòu)。生成樹是一種重要的非線性數(shù)據(jù)結(jié)構(gòu)，它是數(shù)據(jù)元素按分支關(guān)系組織起來的結(jié)構(gòu)。如果兩節(jié)點(diǎn)之間的邊有權(quán)值，那么這些邊權(quán)之和最小的生成樹就叫做最小生成樹。

最小生成樹Prim 算法是圖論中最小生成樹的一種算法，可在加權(quán)連通圖里搜索最小生成樹。由此算法搜索到的邊的子集所構(gòu)成的樹中，不但包括了連通圖里的所有頂點(diǎn)，且其所有邊的權(quán)值之和為最小。

從進(jìn)化角度理解蛋白質(zhì)復(fù)合物的形成，認(rèn)為蛋白質(zhì)復(fù)合物應(yīng)該由一個具有關(guān)鍵功能的核心蛋白質(zhì)開始擴(kuò)展。核心蛋白質(zhì)與某些蛋白質(zhì)產(chǎn)生聯(lián)系，形成蛋白質(zhì)復(fù)合物，這個蛋白質(zhì)復(fù)合物又繼續(xù)與一些蛋白質(zhì)產(chǎn)生聯(lián)系，使復(fù)合物逐漸變大。在不斷擴(kuò)展的過程中，蛋白質(zhì)復(fù)合物內(nèi)部蛋白質(zhì)之間的聯(lián)系逐漸變得更加緊密。因此應(yīng)用Prim 算法識別蛋白質(zhì)的步驟為：

（1）首先進(jìn)行初始化操作，將所有蛋白質(zhì)節(jié)點(diǎn)入優(yōu)先隊列。優(yōu)先隊列是指，當(dāng)訪問元素時，具有最高優(yōu)先級的元素最先刪除的一種數(shù)據(jù)結(jié)構(gòu)。

（2）取隊列頂端的點(diǎn)，并找到所有與它相鄰且不在樹中的頂端的點(diǎn)，逐步進(jìn)行優(yōu)選。

（3）重復(fù)（2）的操作，直至隊列為空。

（4）得到了兩個數(shù)組，一個是表示樹中連接節(jié)點(diǎn)的最小權(quán)值邊的權(quán)值，一個是連接節(jié)點(diǎn)的上一級節(jié)點(diǎn)。

通過以上4 個步驟，使得“樞紐”蛋白質(zhì)節(jié)點(diǎn)與其他相連接的蛋白質(zhì)節(jié)點(diǎn)逐步形成蛋白質(zhì)復(fù)合物。

實現(xiàn)Prim 算法的偽代碼如圖1 所示。

圖1 實現(xiàn)Prim 算法的偽代碼

4 實驗設(shè)計與分析

4.1 基于Prim 算法的蛋白質(zhì)復(fù)合物的具體識別

從圖論角度來理解，把每個點(diǎn)的所有帶權(quán)邊的權(quán)值之和作為其是否為關(guān)鍵蛋白質(zhì)的指標(biāo)。

首先，使用Prim 生成樹的算法實現(xiàn)，以生成樹的過程去擴(kuò)展蛋白質(zhì)，每次擴(kuò)展后，使用ClusterONE 算法[12]中提出的內(nèi)聚性算法，判斷蛋白質(zhì)的內(nèi)聚性。蛋白質(zhì)復(fù)合物C 的內(nèi)聚性由下式給出：

其中，Win是完全包含在C 中的邊的權(quán)重之和，Wout是將屬于C 的蛋白質(zhì)連接到網(wǎng)絡(luò)其余部分的邊緣權(quán)重之和，m 用來反映蛋白質(zhì)相互作用網(wǎng)絡(luò)的不確定性。該指標(biāo)用來反映復(fù)合物內(nèi)部是否具有強(qiáng)連接，并與外部分離良好。

若蛋白質(zhì)內(nèi)聚性增加，則繼續(xù)擴(kuò)展。若蛋白質(zhì)內(nèi)聚性減小，則認(rèn)為此次擴(kuò)展不正確，撤回此次擴(kuò)展，并將此次擴(kuò)展前的蛋白質(zhì)復(fù)合物放入結(jié)果中。對于每一個已經(jīng)被加入過某個蛋白質(zhì)復(fù)合物的蛋白質(zhì)，均做標(biāo)記，不再將其加入任何蛋白質(zhì)，從而避免蛋白質(zhì)重疊問題。

基于Prim 算法的蛋白質(zhì)復(fù)合物識別核心Python代碼如圖2 所示。

圖2 基于Prim 算法的蛋白質(zhì)復(fù)合物識別核心Python 代碼

4.2 實驗評價標(biāo)準(zhǔn)

為了驗證本算法的性能，我們用了4 個評價標(biāo)準(zhǔn)或稱評價指標(biāo)：F 值、陽性預(yù)測值PPV、精準(zhǔn)率ACC和最大匹配率MMR。這4 個指標(biāo)能夠從不同側(cè)面反映蛋白質(zhì)復(fù)合物識別的準(zhǔn)確性，指標(biāo)得分越高，表示識別的準(zhǔn)確性越好。由于篇幅所限，且這4 個指標(biāo)為業(yè)內(nèi)所周知，這里不對其具體計算詳細(xì)展開。

4.3 實驗結(jié)果及分析

以下對本研究基于Prim 算法的蛋白質(zhì)復(fù)合物識別方法與其他6 種基于網(wǎng)絡(luò)拓?fù)涮卣鞯牡鞍踪|(zhì)復(fù)合物識別方法進(jìn)行比較。其他6 種方法分別為：MCL[13]，CMC[14]，RRW[15]，ClusterONE[12]，MCODE[16]，COACH[10]。比較結(jié)果見表1。

表1 不同蛋白質(zhì)復(fù)合物識別算法的性能對比

本實驗選取的標(biāo)準(zhǔn)蛋白質(zhì)復(fù)合物來自于MIPS[17]，過濾掉標(biāo)準(zhǔn)蛋白質(zhì)復(fù)合物中包含蛋白質(zhì)個數(shù)小于3 的蛋白質(zhì)復(fù)合物之后，共有203 個標(biāo)準(zhǔn)蛋白質(zhì)復(fù)合物。

從表1 可知，本實驗基于Prim 算法的蛋白質(zhì)復(fù)合物識別方法的準(zhǔn)確率雖然超過其他6 種算法（匹配率更高），但是預(yù)測數(shù)較低，因此本方法更偏向于精準(zhǔn)預(yù)測，即雖然識別出的數(shù)量較少，但是正確率較高，為53.9%。

5 結(jié)語

算法基礎(chǔ)是一門實踐性課程，是計算機(jī)專業(yè)培養(yǎng)學(xué)生編程能力和算法設(shè)計能力的基礎(chǔ)課程。通過在實驗項目中引入前沿?zé)狳c(diǎn)內(nèi)容，鼓勵學(xué)生進(jìn)行獨(dú)特的創(chuàng)新性設(shè)計并嘗試新穎算法，能夠激發(fā)學(xué)生的動手實踐熱情和編寫程序的積極性。將所學(xué)算法用于解決實際問題，能夠提升學(xué)生的創(chuàng)造力、實踐力及科學(xué)研究的綜合素質(zhì)，符合創(chuàng)新型卓越工程科技人才的培養(yǎng)目標(biāo)。