梁 冰，張益嘉，呂嘉慶

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

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

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

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

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

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

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

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

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

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

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

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

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

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

PPI 網(wǎng)絡(luò)的第一個(gè)非隨機(jī)拓?fù)涮卣魇枪?jié)點(diǎn)的度，有時(shí)也稱為連接度，即在給定的蛋白質(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)的平均度大幾個(gè)數(shù)量級(jí)。 參與簡(jiǎn)單任務(wù)的蛋白質(zhì)可能只需要幾個(gè)相互作用的伙伴，而那些蛋白質(zhì)“樞紐”則是用于更復(fù)雜和全局性任務(wù)的。

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

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

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

因?yàn)榉沁B通圖的網(wǎng)絡(luò)直徑為所有連通子圖的網(wǎng)絡(luò)直徑的最大值，因此非連通圖的網(wǎng)絡(luò)直徑是無(wú)窮大的。

2.3 特征路徑長(zhǎng)度

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

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

3 圖論最小生成樹(shù)Prim 算法

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

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

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

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)設(shè)計(jì)與分析

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

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

首先，使用Prim 生成樹(shù)的算法實(shí)現(xiàn)，以生成樹(shù)的過(guò)程去擴(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 用來(lái)反映蛋白質(zhì)相互作用網(wǎng)絡(luò)的不確定性。該指標(biāo)用來(lái)反映復(fù)合物內(nèi)部是否具有強(qiáng)連接，并與外部分離良好。

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

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

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

4.2 實(shí)驗(yàn)評(píng)價(jià)標(biāo)準(zhǔn)

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

4.3 實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

5 結(jié)語(yǔ)

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