智能優化算法及其在PPI網絡中的應用研究

唐高陽

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

關鍵詞：PPI網絡 蛋白質 群智能優化算法 布谷鳥搜索算法

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

1群智能優化算法的基本內容

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

1.1布谷鳥算法

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

= +a×Levy（λ）

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

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

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

1.1.1趨向性操作

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

1.1.2復制操作

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

1.1.3遷徙操作

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

2 PPI網絡中群智能優化算法的應用路徑分析

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

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

2.1涉及知識

2.1.1蛋白質結點相同之處

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

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代表蛋白質a與蛋白質b的相似度，而Xab則代表Xa與Xb的乘積。在本次實驗當中，需要充分結合上述提出的相似度定義，并進一步提出演化推算后的新相似度定義，其表達式為：

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

Sab=1-Dab

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

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

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

2.1.2目標函數

在PPI網絡中結點K的定義主要表示與蛋白質結點的連接邊數量，而結點的加權度則表示該蛋白質結點相連的全部邊權重總和。結點加權聚集度代表與結點相連的任意兩個結點的權重和，具體公式為：

WKv= wuk

其中WKv代表結點加權度。而結點的加權聚集系數WCv則需根據以下公式進行計算：

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

由此可知，網絡綜合特征值需要根據以上兩種公式結合計算，即：

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

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

WDv= wuk

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

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

fitc=? value（j）/n

其中c表示聚類結果中的任意模塊，n代表蛋白質個數，fitc是指網絡綜合特征數值，其數值越高，證明聚類結果越優良。

2.2算法描述

2.2.1處理數據、選取中心點

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

2.2.2算法步驟

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

2.2.3聚類過程

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

2.3性能探究與仿真實驗

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

3 結語

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

參考文獻

[1]胡健，朱海灣，毛伊敏.基于時序加權PPI網絡的關鍵蛋白質識別[J].計算機工程與應用，2019，55（23）：150-162.

[2]楊書新，魯紀華，湯達榮.基于動態加權PPI網絡的關鍵蛋白質識別算法[J].計算機應用研究，2019，36（2）：367-370，379.

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

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

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

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

sdjzdx202203231615