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

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

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

【部分圖文】：

ESU算法示意圖Fig．1SchematicdiagramofESUalgorithm

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

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

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



本文編號(hào)：3450569