生物復(fù)雜網(wǎng)絡(luò)motif發(fā)現(xiàn)是一種研究生物網(wǎng)絡(luò)的重要方法,它基于復(fù)雜網(wǎng)絡(luò)的理論研究,以新的視角來研究生命現(xiàn)象和生命機(jī)制,但是在處理較大的網(wǎng)絡(luò)規(guī)�；蛘咝柰诰蜉^大的motif時計算效率低。針對這個問題,在現(xiàn)有串行網(wǎng)絡(luò)motif發(fā)現(xiàn)算法ESU的基礎(chǔ)上,提出一種基于消息傳遞接口（MPI）的并行化ESU算法。該方法在ESU計算過程中優(yōu)化了節(jié)點值以解決節(jié)點值依賴問題,并以ESU算法的子圖發(fā)現(xiàn)策略統(tǒng)計各節(jié)點子圖數(shù),利用動態(tài)規(guī)劃策略尋找最佳節(jié)點分配策略以解決負(fù)載不均衡問題。模擬網(wǎng)絡(luò)數(shù)據(jù)和真實生物網(wǎng)絡(luò)數(shù)據(jù)的實驗結(jié)果表明,并行化ESU算法優(yōu)化了節(jié)點值依賴問題,實現(xiàn)了基于動態(tài)規(guī)劃的負(fù)載均衡策略,其運行時間比串行算法縮短了90%,并且該并行算法對不同類型不同規(guī)模的網(wǎng)絡(luò)都具有較強(qiáng)的適用性,有效地提高了網(wǎng)絡(luò)motif發(fā)現(xiàn)問題的計算效率。 

【文章來源】：計算機(jī)應(yīng)用. 2019,39(01)北大核心CSCD

【文章頁數(shù)】：6 頁

【部分圖文】：

ESU算法示意圖Fig．1SchematicdiagramofESUalgorithm

饈?條件下的測試結(jié)果進(jìn)行描述，測試條件為酵母菌蛋白質(zhì)網(wǎng)絡(luò)的motif大小為6，并行核數(shù)為8，測試結(jié)果如圖4所描述。圖4中，節(jié)點分配策略是在不計算子圖數(shù)的前提下進(jìn)行節(jié)點分配，子圖分配策略是指計算子圖數(shù)，根據(jù)子圖數(shù)對節(jié)點分配，子圖動態(tài)規(guī)劃則為本文提出的節(jié)點分配策略，旨在計算出子圖數(shù)后，根據(jù)子圖數(shù)動態(tài)規(guī)劃節(jié)點與進(jìn)程號之間的關(guān)系。從圖中可以得出，使用基于動態(tài)規(guī)劃的節(jié)點分配策略明顯優(yōu)于不使用動態(tài)規(guī)劃的節(jié)點分配策略，而且各個進(jìn)程所計算的時間基本相當(dāng)，滿足了負(fù)載均衡的要求。圖43種節(jié)點分配策略的各個進(jìn)程計算時間Fig．4Calculationtimeforeachprocessofthreenodeallocationstrategies3．3．3不同平均節(jié)點度的模擬網(wǎng)絡(luò)的實驗結(jié)果在這個實驗中，本文對前文提到的3類網(wǎng)絡(luò)模型進(jìn)行測試，分別是無標(biāo)度網(wǎng)絡(luò)模型、小世界網(wǎng)絡(luò)模型和規(guī)則網(wǎng)絡(luò)模型，每種網(wǎng)絡(luò)模型都使用motif大小固定為4的并行ESU算法來測試并行性能，測試結(jié)果取10個網(wǎng)絡(luò)結(jié)果的平均值，3類網(wǎng)絡(luò)模型的測試結(jié)果如圖5所示。圖5(a)、(b)、(c)描述了平均節(jié)點度為5、10和15的三種模擬網(wǎng)絡(luò)，分別是無標(biāo)度網(wǎng)絡(luò)、小世界網(wǎng)絡(luò)和規(guī)則網(wǎng)絡(luò)使用并行化ESU算法的并行性能，分析圖5的實驗結(jié)果，網(wǎng)絡(luò)的平均節(jié)點度的變化對并行化ESU的加速比幾乎不影響，3種不同平均節(jié)點度的網(wǎng)絡(luò)的加速比曲線幾乎重合，而且各種不同類型的網(wǎng)絡(luò)之間的加速比變化也很小，加速比曲線幾乎接近線性關(guān)系。結(jié)果表明，本文的并行化ESU算法適用于各種不同類型不同稀疏程度的網(wǎng)絡(luò)。3．3．4生物網(wǎng)絡(luò)的實驗結(jié)果生物網(wǎng)絡(luò)是一種同時具有無標(biāo)度和小世界特性的復(fù)雜網(wǎng)絡(luò)［18

用動態(tài)規(guī)劃的節(jié)點分配策略，而且各個進(jìn)程所計算的時間基本相當(dāng)，滿足了負(fù)載均衡的要求。圖43種節(jié)點分配策略的各個進(jìn)程計算時間Fig．4Calculationtimeforeachprocessofthreenodeallocationstrategies3．3．3不同平均節(jié)點度的模擬網(wǎng)絡(luò)的實驗結(jié)果在這個實驗中，本文對前文提到的3類網(wǎng)絡(luò)模型進(jìn)行測試，分別是無標(biāo)度網(wǎng)絡(luò)模型、小世界網(wǎng)絡(luò)模型和規(guī)則網(wǎng)絡(luò)模型，每種網(wǎng)絡(luò)模型都使用motif大小固定為4的并行ESU算法來測試并行性能，測試結(jié)果取10個網(wǎng)絡(luò)結(jié)果的平均值，3類網(wǎng)絡(luò)模型的測試結(jié)果如圖5所示。圖5(a)、(b)、(c)描述了平均節(jié)點度為5、10和15的三種模擬網(wǎng)絡(luò)，分別是無標(biāo)度網(wǎng)絡(luò)、小世界網(wǎng)絡(luò)和規(guī)則網(wǎng)絡(luò)使用并行化ESU算法的并行性能，分析圖5的實驗結(jié)果，網(wǎng)絡(luò)的平均節(jié)點度的變化對并行化ESU的加速比幾乎不影響，3種不同平均節(jié)點度的網(wǎng)絡(luò)的加速比曲線幾乎重合，而且各種不同類型的網(wǎng)絡(luò)之間的加速比變化也很小，加速比曲線幾乎接近線性關(guān)系。結(jié)果表明，本文的并行化ESU算法適用于各種不同類型不同稀疏程度的網(wǎng)絡(luò)。3．3．4生物網(wǎng)絡(luò)的實驗結(jié)果生物網(wǎng)絡(luò)是一種同時具有無標(biāo)度和小世界特性的復(fù)雜網(wǎng)絡(luò)［18］，同時生物網(wǎng)絡(luò)也是稀疏網(wǎng)絡(luò)的一種。在前一節(jié)，本文的并行算法在各類模擬網(wǎng)絡(luò)上表現(xiàn)良好。為了驗證本文的并行算法在真實生物網(wǎng)絡(luò)上是否同樣表現(xiàn)良好，本文對前文提到的3類不同節(jié)點數(shù)不同邊數(shù)的真實生物網(wǎng)絡(luò)進(jìn)行測試，測試使用的motif大小為6，每個生物網(wǎng)絡(luò)均進(jìn)行了10次測試，測試結(jié)果取其平均值以降低誤差，測試結(jié)果如表3和圖6所示。圖5各種不同條件的模擬網(wǎng)絡(luò)的并行性能Fig．5Pa

【參考文獻(xiàn)】：
期刊論文
[1]HashESU:一種生物網(wǎng)絡(luò)模體識別高效方法[J]. 趙靜,鐘誠.  小型微型計算機(jī)系統(tǒng). 2015(09)
[2]生物網(wǎng)絡(luò)模體發(fā)現(xiàn)算法研究綜述[J]. 覃桂敏,高琳,呼加璐.  電子學(xué)報. 2009(10)



本文編號：3450569