生物網(wǎng)絡(luò)中概率模體發(fā)現(xiàn)算法的研究.pdf

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

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

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