基于Memetic計(jì)算的生物網(wǎng)絡(luò)全局比對(duì)研究.pdf

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

2、題，但是這些被提出的算法往往因?yàn)闆](méi)有加入先驗(yàn)知識(shí)而搜索效率非常低下。
　　本文提出了一種Memetic算法，表示為MeAlign，用來(lái)解決生物網(wǎng)絡(luò)的比對(duì)問(wèn)題。MeAlign算法吸取了二步算法的思想，先利用已有的先驗(yàn)知識(shí)構(gòu)造一個(gè)粗糙的得分矩陣，再用這個(gè)得分矩陣來(lái)指導(dǎo)初始化；而在局部搜索算子的設(shè)計(jì)部分，吸取該領(lǐng)域經(jīng)典算法中的種子加擴(kuò)展方法思想，設(shè)計(jì)了一種高效的基于特定鄰域的局部搜索算子。該算子首先定義了單個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)的鄰域空間，然后在鄰

3、域空間中尋找對(duì)優(yōu)化模型有貢獻(xiàn)的匹配結(jié)點(diǎn)。為了更全面的分析說(shuō)明蛋白質(zhì)網(wǎng)絡(luò)的比對(duì)問(wèn)題和 MeAlign算法解決比對(duì)問(wèn)題的效果，本文通過(guò)兩條主線加以說(shuō)明：
　　1)通過(guò)優(yōu)化不同的網(wǎng)絡(luò)模型來(lái)說(shuō)明網(wǎng)絡(luò)模型的選取對(duì)比對(duì)結(jié)果的影響。先通過(guò)只優(yōu)化網(wǎng)絡(luò)的拓?fù)湎嗨菩阅Ｐ蛠?lái)得到比對(duì)結(jié)果，再通過(guò)分析比對(duì)結(jié)果指出這種模型的不足之處；然后在此基礎(chǔ)上提出優(yōu)化加權(quán)模型，就是同時(shí)優(yōu)化網(wǎng)絡(luò)的拓?fù)湎嗨菩院途W(wǎng)絡(luò)結(jié)點(diǎn)的序列相似性。通過(guò)分析加權(quán)模型優(yōu)化的比對(duì)結(jié)果，得出加權(quán)模