生物復(fù)雜網(wǎng)絡(luò)Motif發(fā)現(xiàn)的并行算法詳細(xì)資料概述

　　生物復(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ì)算效率低。針對這個(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ù)，利用動態(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)了基于動態(tài)規(guī)劃的負(fù)載均衡策略，其運(yùn)行時(shí)間比串行算法縮短了90%，并且該并行算法對不同類型不同規(guī)模的網(wǎng)絡(luò)都具有較強(qiáng)的適用性，有效地提高了網(wǎng)絡(luò)motif發(fā)現(xiàn)問題的計(jì)算效率。

　　生物網(wǎng)絡(luò)比對對網(wǎng)絡(luò)醫(yī)學(xué)和物種演化等領(lǐng)域的發(fā)展有著重大的意義”，其中，一項(xiàng)很重要的研究就是生物網(wǎng)絡(luò)motif發(fā)現(xiàn)。生物網(wǎng)絡(luò)motif發(fā)現(xiàn)是指在生物網(wǎng)絡(luò)中尋找所有特定大小、拓?fù)浣Y(jié)構(gòu)一致的子圖 ，它包括在生物網(wǎng)絡(luò)中枚舉子圖和計(jì)算子圖之間的同構(gòu)關(guān)系等問題。生物網(wǎng)絡(luò)motif是生物網(wǎng)絡(luò)的基本單元，它所表現(xiàn)的局部性質(zhì)與網(wǎng)絡(luò)的構(gòu)成機(jī)制密切相關(guān)，對它的研究可以加深對生物網(wǎng)絡(luò)的結(jié)構(gòu)和功能的理解，有助于揭示很多重要的生物學(xué)問題;然而精確識別網(wǎng)絡(luò)motif 是-個(gè)計(jì)算復(fù)雜度很高的問題，每-一個(gè)枚舉的子圖都需要執(zhí)行同構(gòu)比較，而子圖之間同構(gòu)關(guān)系的計(jì)算-直是NP（ Non-deterministic Polynomial）難問題，無法通過改進(jìn)算法來降低其時(shí)間復(fù)雜度。隨著生物網(wǎng)絡(luò)研究的規(guī)模和motif的大小不斷增大，參與枚舉和同構(gòu)比較的子圖數(shù)呈指數(shù)級別的增長，其計(jì)算量越來越大，給網(wǎng)絡(luò)motif的發(fā)現(xiàn)帶來了挑戰(zhàn)。