生物網絡中概率模體發(fā)現算法的研究.pdf

1、隨著生物技術的發(fā)展，產生了大量的生物網絡數據。如何從這些生物網絡數據中發(fā)現一些具有生物功能的拓撲結構成為生物信息學的一個研究熱點。大量實驗表明，模體是這些生物網絡中有生物功能的基本模塊。目前模體的研究主要側重于識別精確模體，事實上，由于目前的測量手段的不準確性或者實驗方法的不完整性，這些已經得到的生物網絡數據往往是有噪聲的或者不完整的。另外，生命過程本身也是一個動態(tài)變化的過程，因此概率模體更能體現生命的動態(tài)變化過程和生物網絡的功能意義。

2、概率模體發(fā)現算法的主要瓶頸在于非樹形子圖的挖掘和在得分函數最大化的過程中得分函數值的計算。其中后者需要進行多圖比對，并且需要建立在任意兩個子圖的兩兩最小錯配的基礎上。當要發(fā)現的概率模體規(guī)模增大的時候，計算任意兩個子圖的最小錯配所需時間也急劇增長。
　　 因此，論文的主要工作如下：
　　 1.論文首先提出了一種基于劃分的非樹形子圖搜索算法，與已有的非樹形子圖搜索算法相比，具有更高的時間效率。
　　 2.論文利用子圖

3、同構是子圖最小錯配的特殊化，求解子圖同構比求解子圖的最小錯配更有效率這一優(yōu)勢，提出先利用同構來對子圖分組，屬于同一個同構組的任意兩個子圖其最小錯配為零，之后再對不同構的子圖進行最小錯配的求解。這樣在減少了求解任意兩個子圖最小錯配時間的同時，也縮小了之后利用智能優(yōu)化算法對得分函數求解的解空間。
　　 3.論文將一種基于模擬退火算法和遺傳算法的混合算法應用于得分函數的求解過程，這與已有的只利用模擬退火算法進行求解相比，能以相對較快的