基于Memetic計算的生物網絡全局比對研究.pdf

1、隨著高通量篩選技術和計算機技術的飛速發(fā)展，現在已經能夠獲得越來越多的生物數據，其中很重要的一類數據就是蛋白質間的相互作用數據。有了這些數據，就可以從系統的角度來分析生命的活動過程。通常將蛋白質間相互作用數據抽象成網絡模型進行分析，而網絡比對方法是一種在研究生物網絡數據時常用的系統分析方法。對蛋白質網絡數據的比對分析能夠幫助我們發(fā)現未知生物網絡中的保守功能子圖并且加深對不同物種進化軌跡的認識。一些進化算法已經被提出來解決蛋白質網絡的比對問

2、題，但是這些被提出的算法往往因為沒有加入先驗知識而搜索效率非常低下。
　　本文提出了一種Memetic算法，表示為MeAlign，用來解決生物網絡的比對問題。MeAlign算法吸取了二步算法的思想，先利用已有的先驗知識構造一個粗糙的得分矩陣，再用這個得分矩陣來指導初始化；而在局部搜索算子的設計部分，吸取該領域經典算法中的種子加擴展方法思想，設計了一種高效的基于特定鄰域的局部搜索算子。該算子首先定義了單個網絡節(jié)點的鄰域空間，然后在鄰

3、域空間中尋找對優(yōu)化模型有貢獻的匹配結點。為了更全面的分析說明蛋白質網絡的比對問題和 MeAlign算法解決比對問題的效果，本文通過兩條主線加以說明：
　　1)通過優(yōu)化不同的網絡模型來說明網絡模型的選取對比對結果的影響。先通過只優(yōu)化網絡的拓撲相似性模型來得到比對結果，再通過分析比對結果指出這種模型的不足之處；然后在此基礎上提出優(yōu)化加權模型，就是同時優(yōu)化網絡的拓撲相似性和網絡結點的序列相似性。通過分析加權模型優(yōu)化的比對結果，得出加權模