智能優(yōu)化算法及其在PPI網(wǎng)絡(luò)中的應(yīng)用研究

唐高陽

摘要：本文將圍繞群智能優(yōu)化算法的基本內(nèi)容進行分析討論，提出在PPI網(wǎng)絡(luò)中群智能優(yōu)化算法的具體應(yīng)用路徑，以布谷鳥搜索算法作為分析對象，切實保證聚類結(jié)果準確，借助網(wǎng)絡(luò)形式更全面地反映蛋白質(zhì)之間的關(guān)系，幫助科學家充分探究蛋白質(zhì)的實際作用與功能，以此加強疾病防治效率，幫助人們保持身體健康，避免疾病造成嚴重危害。

關(guān)鍵詞：PPI網(wǎng)絡(luò) 蛋白質(zhì) 群智能優(yōu)化算法 布谷鳥搜索算法

Intelligent Optimization Algorithm and Its Application in PPI Network

TANG Gaoyang

（ShenYang Ligong Uiversity ， Liaoning，Shenyang Province， 110158 China）

Abstract： This paper will discuss the basic content of group intelligent optimization algorithm， put forward the specific application path of group intelligent optimization algorithm in PPI network， with cuckoo search algorithm as the analysis object， to ensure the accurate clustering results， with the form of more comprehensive reflect the relationship between protein， help scientists fully explore the actual role and function of protein， so as to strengthen the efficiency of disease prevention and control， help people maintain health and avoid serious harm from disease.

Key Words： PPI network; Protein; Group intelligent optimization algorithm; Cuckoo search algorithm

PPI是指蛋白質(zhì)之間的相互作用，描述多個蛋白質(zhì)分子利用非共價鍵形成復合體的過程，加強對PPI網(wǎng)絡(luò)的研究不僅能實現(xiàn)疾病診斷的順利開展，還能幫助人們更準確地認識到未知蛋白質(zhì)的具體功能，明確分子機制，從而采取針對性的治療手段。為了保證群智能優(yōu)化算法在PPI網(wǎng)絡(luò)中得到有效運用，首先要對其基本內(nèi)容進行深入了解。

1群智能優(yōu)化算法的基本內(nèi)容

群智能是指昆蟲的集體行為，通過將群居昆蟲協(xié)作過程中反映的復雜行為特征作為研究基礎(chǔ)，演化全新的算法技術(shù)。

1.1布谷鳥算法

布谷鳥算法的主要依據(jù)包括：布谷鳥繁殖行為，布谷鳥通常會將巢寄生作為主要繁殖方式，當其處在繁殖期時會積極找尋與自身孵化期相似、卵形相近的宿主，之后將卵寄放在宿主巢內(nèi)，由其代替自己進行孵化;萊維飛行，屬于隨機行走的一部分，行走步長能夠體現(xiàn)重尾的大致分布，行走過程中可以實現(xiàn)短距離探索。在運用智能優(yōu)化算法時，可以借助萊維飛行進一步提升探索區(qū)域，保證種群多元化，達到全局最佳的目的。布谷鳥算法能夠根據(jù)布谷鳥實際繁殖行為以及萊維飛行理論進行布谷鳥搜尋宿主巢的過程模擬，若想保證設(shè)計算法有效運用，還要達到以下3種理想狀態(tài)：第一，布谷鳥每次只產(chǎn)下一個卵，依照隨機擇選的方式找尋窩來孵化;第二，在多個隨機找尋的鳥窩中會將最優(yōu)的一個會保留至下一代;第三，鳥窩數(shù)量基本恒定不變，將鳥窩實際主人發(fā)現(xiàn)外來鳥蛋的幾率記為PA，其數(shù)值在0～1之間。在滿足3種理想狀態(tài)后，布谷鳥找尋路徑與具體位置公式可記作：

= +a×Levy（λ）

其中 、 代表第i個鳥巢在m代以及m+1代時第j個位置，Levy（λ）表示Levy的飛行跳躍路徑，其方向以及長度具有隨機性。

布谷鳥算法的應(yīng)用步驟可細分為：（1）首先要確立目標函數(shù)f（x），其中x=（x1，x2，x3……xd）T，之后進行群體初始化，最后隨機生成多個鳥窩位置，即xi，并設(shè)置好位置參數(shù);（2）計算鳥窩目標函數(shù)，記錄最優(yōu)解;（3）保留最優(yōu)鳥窩位置，并依照 = +a×Levy（λ）公式進行其余鳥窩位置的更新;（4）進行當前鳥窩與上一代鳥窩的位置比對，若發(fā)現(xiàn)現(xiàn)有鳥窩更加優(yōu)良便可記作最佳位置;（5）利用隨機數(shù)R當作鳥窩實際主人發(fā)現(xiàn)布谷鳥鳥蛋的可能性，之后與PA進行對比，當出現(xiàn)R高于PA的狀況，則需改變鳥窩現(xiàn)有位置，重新找尋鳥窩;（6）當未滿足結(jié)束條件時，需要從第二個步驟開始重復操作;（7）完成全局最優(yōu)1.2細菌覓食算法。

細菌的生存法則符合“優(yōu)勝劣汰”的理論，若所處區(qū)域的食物相對豐富，便會進行分裂，形成全新個體，當所處環(huán)境較為惡劣，則細菌會進行遷徙，甚至選擇死亡。以大腸桿菌為例，該細菌主要通過鞭毛進行游動以此獲取食物，當細菌所在區(qū)域食物稀缺時，便會隨機選擇方向進行游動，若發(fā)現(xiàn)新環(huán)境食物足夠滿足自身生存需要，便會持續(xù)游動至步數(shù)閥值。細菌覓食算法最初是由Passino科學家以大腸桿菌的吞噬行為作為依據(jù)，提出的仿生算法，該算法的操作步驟可細化為以下3點。

1.1.1趨向性操作

趨向性操作是指細菌向營養(yǎng)豐富的區(qū)域移動的行為，在此過程中，細菌主要是依靠游動或者旋轉(zhuǎn)實現(xiàn)聚集，若細菌在旋轉(zhuǎn)后所處的環(huán)境得到顯著改善便會停止移動，反之則會重新選擇方向進行移動，直到環(huán)境能夠滿足其生存需求，亦或是達到移動步數(shù)臨界點。

1.1.2復制操作

復制操作主要是指在食物相對豐富的區(qū)域內(nèi)，細菌的生命周期結(jié)束或者達到臨界趨化值，將進行繁殖行為，細菌所采取的繁殖方式為分裂，能夠形成與自身覓食能力完全一致的新個體，在分裂時需要與細菌本身的適應(yīng)值累加和作為判斷標準，如果覓食能力不佳，低于平均水平便會有半數(shù)細菌死亡，而覓食能力較強的半數(shù)細菌則會進行復制操作，以及提升營養(yǎng)環(huán)境的搜尋速度。

1.1.3遷徙操作

遷徙操作是指細菌所處的環(huán)境食物相對匱乏，或者環(huán)境正朝著劣化的方向發(fā)展，此時細菌個體隨時可能面臨死亡的風險，因此細菌為了繼續(xù)生存繁殖，會選擇生成一個全新個體，借助遷徙操作生成的個體更加趨近于全局最優(yōu)解，這樣便可有效避免局部最優(yōu)解的產(chǎn)生[1]。

2 PPI網(wǎng)絡(luò)中群智能優(yōu)化算法的應(yīng)用路徑分析

PPI網(wǎng)絡(luò)本身屬于真實網(wǎng)絡(luò)，與傳統(tǒng)的規(guī)則網(wǎng)絡(luò)以及隨機網(wǎng)絡(luò)不同，其結(jié)構(gòu)組成更為復雜，可以定義為無向簡單圖，主要由頂點集與邊集組成，邊集中的每條邊都有相應(yīng)的頂點，并且頂點可以表示網(wǎng)絡(luò)中的真實個體，而每條邊則代表一對個體存在的相互作用，在蛋白質(zhì)網(wǎng)絡(luò)中，每個頂點都可作為一個個體蛋白質(zhì)，并且隨著對網(wǎng)絡(luò)拓撲結(jié)構(gòu)深入分析，人們逐漸發(fā)現(xiàn)復雜網(wǎng)絡(luò)中存在模塊化結(jié)構(gòu)，且每個模塊都存在結(jié)點連接。除此之外，PPI網(wǎng)絡(luò)還具有以下2種特征：一是小世界網(wǎng)絡(luò)，該特性是由WATTS科學家首次提出，通過以k階規(guī)則網(wǎng)絡(luò)作為分析基礎(chǔ)，依照一定概率完成端點斷開，在重新連接后新的端點能夠從網(wǎng)絡(luò)中任意結(jié)點被隨機選擇，當網(wǎng)絡(luò)屬于規(guī)則網(wǎng)絡(luò)時，概率為0，如果網(wǎng)絡(luò)屬于隨機網(wǎng)絡(luò)則概率為1;二是無尺度屬性，該特征是由barabasi科學家最先發(fā)現(xiàn)，主要體現(xiàn)在真實網(wǎng)絡(luò)結(jié)點度滿足冪率分布規(guī)律時，當度的結(jié)點概率小于k-r時，證明網(wǎng)絡(luò)結(jié)點度相對較小，但存在的部分結(jié)點度仍高于網(wǎng)絡(luò)的平均水平，此時這些具有大量連接的結(jié)點可定義為集散結(jié)點，由其組成的網(wǎng)絡(luò)即可成為無尺度網(wǎng)絡(luò)。

在20世紀末，群智能算法得到大范圍推廣，比如蟻群算法、遺傳算法等，這些算法都是借助模擬生物行為或者部分自然現(xiàn)象來實現(xiàn)問題的最優(yōu)化處理，這種方法也是近年來算法設(shè)計與分析領(lǐng)域中的熱點課題。為了確保PPI網(wǎng)絡(luò)中群智能優(yōu)化算法的應(yīng)用的科學、合理，能夠保持良好的適用性與可行性，本文將以布谷鳥算法作為研究對象，該算法本身具有高效、操作便捷的優(yōu)勢，并且隨機選取的路徑均為最優(yōu)解。

2.1涉及知識

2.1.1蛋白質(zhì)結(jié)點相同之處

在PPI網(wǎng)絡(luò)當中，需要采用一個a行、b列的向量元素Xab用于表示a個蛋白質(zhì)與b個蛋白質(zhì)之間存在的相互作用，并且向量Xab中的各項參數(shù)能夠表示不同蛋白質(zhì)之間的作用大小，若蛋白質(zhì)之間切實存在相互作用，則作用大小可定義為權(quán)重值，如果蛋白質(zhì)之間屬于彼此孤立存在的狀態(tài)，不存在相互作用，則權(quán)重值為0。由于不同蛋白質(zhì)之間的定義過于多樣化，為了更好地實現(xiàn)區(qū)分，需要使用相似度衡量標準進行相似性判斷，其具體內(nèi)容為：

Bader法：Sab=Xab2/（Xaa×Xbb）

Dice法：Sab=2Xab/（Xaa+Xbb）

Simpson法：Sab=Xab/min（Xaa，Xbb）

Bridge法：Sab=1/2×（Xab/Xaa+Xab/Xbb）

Jaccard法：Sab=Xab/（Xab+Xbb-Xaa）

其中Xab代表蛋白質(zhì)a與蛋白質(zhì)b的相似度，而Xab則代表Xa與Xb的乘積。在本次實驗當中，需要充分結(jié)合上述提出的相似度定義，并進一步提出演化推算后的新相似度定義，其表達式為：

Dab=（Xab-Xaa）×（Xab-Xbb）/Xab×Xbb

Sab=1-Dab

之后將上述2個公式進行簡化可得出

Sab=Xab（Xab+Xbb-Xaa）/（Xaa×Xbb）

其中Sab表示結(jié)點a處的周邊結(jié)點結(jié)合，之后要驗證其數(shù)值是否介于0～1之間。證明過程為：Xaa本質(zhì)意義屬于結(jié)點a的周邊個數(shù)，因此Xbb也可理解為結(jié)點b周邊個數(shù)，而Xab則代表結(jié)點a與b的交集數(shù)量。因此Xaa-Xab必然高于0，并且Xbb-Xab的數(shù)值也處在0～Xbb之間，而（Xab-Xaa）×（Xab-Xbb）的值則低于Xaa×Xbb，可以確定Dab的值處在0～1之間，之后根據(jù)公式Sab=1-Dab可知，Sab同樣處于0～1之間。因此可以將Dab作為衡量PPI網(wǎng)絡(luò)中的結(jié)點距離標準[2]。

2.1.2目標函數(shù)

在PPI網(wǎng)絡(luò)中結(jié)點K的定義主要表示與蛋白質(zhì)結(jié)點的連接邊數(shù)量，而結(jié)點的加權(quán)度則表示該蛋白質(zhì)結(jié)點相連的全部邊權(quán)重總和。結(jié)點加權(quán)聚集度代表與結(jié)點相連的任意兩個結(jié)點的權(quán)重和，具體公式為：

WKv= wuk

其中WKv代表結(jié)點加權(quán)度。而結(jié)點的加權(quán)聚集系數(shù)WCv則需根據(jù)以下公式進行計算：

WCv=2×WKv/Kv×（Kv-1）

由此可知，網(wǎng)絡(luò)綜合特征值需要根據(jù)以上兩種公式結(jié)合計算，即：

Valuev=a×WCv+（1-a）×WKv/N

其中，u、k代表與蛋白質(zhì)相連的任意2個結(jié)點，并且u、k之間存在邊，Wuk表示邊的實際權(quán)重值，a則代表0～1之間的隨機變量，通常取0.5。N表示PPI中的結(jié)點個數(shù)。以上3個公式能夠證明網(wǎng)絡(luò)特征值可以充分反映不同結(jié)點之間的連接強度，同時也能體現(xiàn)結(jié)點局部區(qū)域的連接密度，為了確保結(jié)點特征得到更準確地描述，需要進一步引入加權(quán)度，其公式為：

WDv= wuk

Valuev=a×WCv+（1-a）×WDv/N

其中u屬于結(jié)點v的相鄰結(jié)點，Wuv是指兩結(jié)點邊的權(quán)重，而WDv則表示結(jié)點v的實際加權(quán)度。在帶權(quán)中的PPI作用網(wǎng)絡(luò)下，網(wǎng)絡(luò)的特征值可以從形態(tài)或組成上看出，不僅需要將模塊中不同蛋白質(zhì)的連接關(guān)系進行全面考慮，還要充分掌握彼此之間的連接權(quán)度值，利用隨機變量實現(xiàn)比重調(diào)節(jié)，因此用以衡量PPI網(wǎng)絡(luò)聚類結(jié)果的目標函數(shù)可表示為：

fitc=? value（j）/n

其中c表示聚類結(jié)果中的任意模塊，n代表蛋白質(zhì)個數(shù)，fitc是指網(wǎng)絡(luò)綜合特征數(shù)值，其數(shù)值越高，證明聚類結(jié)果越優(yōu)良。

2.2算法描述

2.2.1處理數(shù)據(jù)、選取中心點

為了確保數(shù)據(jù)得到預先處理，需要將蛋白質(zhì)名稱與數(shù)字相互對應(yīng)，為蛋白質(zhì)賦予代碼編號，這樣便可在運行程序時更便捷地開展數(shù)據(jù)比較與計算，以此達到提升算法運行速度與運行效率的目的。在初始化聚類中心時，要依照網(wǎng)絡(luò)結(jié)點與邊所蘊含的信息，使利用度與特征值閥值能夠選擇最優(yōu)的中心點。若某結(jié)點度與特征值高于給定閥值，則此結(jié)點需要記作聚類中心。同時為了進一步提高收斂速度，實現(xiàn)種群多元化，還要提前擇選a組聚類中心，保證每組聚類中心具有一定的差異性，但組件可以實現(xiàn)聚類中心的重合[3]。

2.2.2算法步驟

首先，數(shù)據(jù)處理需要依照度與特征值閥值完成聚類中心的候選，初始化記作cluster，參數(shù)度閥值設(shè)置為threshold，特征值閥值記作com-threshold，相似度閥值則為sim-threshold，最大迭代次數(shù)為maxter，而訪問表示則為visit。其次，要根據(jù)萊維飛行從候選聚類中心中隨機選出a組鳥窩，要求每組包含b個聚類中心，如果兩組鳥窩數(shù)量一致，則需在整體中重新選取，進行重疊組的替代。之后依照相似度對a組鳥窩進行聚類處理，從而獲得a組的聚類結(jié)果。最后，要將a組聚類結(jié)果以及初始化數(shù)值依照適應(yīng)度值進行排列，記錄最優(yōu)一組，將其作為cluster。同時要使用各組適應(yīng)值最高的模塊以及cluster中適應(yīng)度最小的聚類中心進行比較，若二者一致，則使用適應(yīng)值加高的模塊進行替換，若聚類中心不一致，則使用適應(yīng)度最小的模塊進行代替，并保留最優(yōu)聚類結(jié)果至下一代。此外，要遵循t=t+1的計算原則，若t小于最大迭代次數(shù)，則從聚類結(jié)果的計算重新開始推演算法，若t高于最大迭代次數(shù)，則輸出最優(yōu)解cluster，并進行結(jié)果評價[4]。

2.2.3聚類過程

第一，在聚類開始階段需要依照聚類中心層層遞進的原則進行比較，與傳統(tǒng)的統(tǒng)一集中比較不同，分層開展的方式能夠更好地保證聚類結(jié)果的準確性，降低誤差的形成幾率。第二，由于鳥窩的數(shù)量屬于恒定不變，因此需要在實現(xiàn)聚類時將周邊結(jié)點以及中心點進行適當調(diào)整，使其滿足相似度閥值，同時要取消中心點作為聚類中心的權(quán)限，并從候選中心中擇選未曾訪問過的結(jié)點，確保該結(jié)點與原聚類中心不存在重疊關(guān)系，能夠有效填補空缺。第三，各組聚類結(jié)果需要依次實現(xiàn)與最優(yōu)組的結(jié)果對比，判斷聚類中心是否為最優(yōu)組的成員之一，如果是，則找出其所在位置記作loc，反之，則將其與排序后的元素進行比對[5]。

2.3性能探究與仿真實驗

布谷鳥算法的代價都線性主要體現(xiàn)在結(jié)點數(shù)上，最差狀況表現(xiàn)為無噪聲點，要求對PPI網(wǎng)絡(luò)中的各個結(jié)點都采取遍歷處理。該算法的主要優(yōu)勢可細分為：（1）中心點選取更加高效、準確，能夠充分符合PPI網(wǎng)絡(luò)的小世界特征，所選擇的中心點都較大，具有無尺度特點，在將其作為中心聚類的過程中主要依照廠度實現(xiàn)優(yōu)先遍歷，以此達到防止全部結(jié)點都與中心點完成比較付出過大代價的目的;（2）在完成遍歷時，需要將其與未訪問的中心點記作普通中心點，當滿足預定閥值后，將其歸屬到相應(yīng)類當中，防止后期模塊合并產(chǎn)生不必要的消耗[6]。

3 結(jié)語

綜上所述，通過對群智能優(yōu)化算法的基本內(nèi)容進行分析討論，提出PPI網(wǎng)絡(luò)中群智能優(yōu)化算法的具體應(yīng)用路徑，以此充分發(fā)揮該算法的概率搜索作用，準確完成目標函數(shù)的輸出，確保大量數(shù)據(jù)得到及時處理，更好地為生物研究提供切實可行的參考對象。

參考文獻

[1]胡健，朱海灣，毛伊敏.基于時序加權(quán)PPI網(wǎng)絡(luò)的關(guān)鍵蛋白質(zhì)識別[J].計算機工程與應(yīng)用，2019，55（23）：150-162.

[2]楊書新，魯紀華，湯達榮.基于動態(tài)加權(quán)PPI網(wǎng)絡(luò)的關(guān)鍵蛋白質(zhì)識別算法[J].計算機應(yīng)用研究，2019，36（2）：367-370，379.

[3]楊書佺，舒勤，何川.改進的果蠅算法及其在PPI網(wǎng)絡(luò)中的應(yīng)用[J].計算機應(yīng)用與軟件，2020，31（12）：291-294.

[4]雷秀娟，黃旭，吳爽.基于連接強度的PPI網(wǎng)絡(luò)蟻群優(yōu)化聚類算法[J].電子學報，2020，40（4）：695-702.

[5]唐家琪，吳璟莉.基于PPI網(wǎng)絡(luò)與機器學習的蛋白質(zhì)功能預測方法[J].計算機應(yīng)用，2020，38（3）：722-727.

[6]胡慶生，雷秀娟.PPI網(wǎng)絡(luò)的改進馬爾科夫聚類算法[J].計算機科學，2020，42（7）：108-113.

sdjzdx202203231615