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

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