基于離散粒子群優(yōu)化的生物網(wǎng)絡(luò)全局比對(duì)研究.pdf

1、生物網(wǎng)絡(luò)比對(duì)旨在通過(guò)比較分析的方法來(lái)識(shí)別不同分子相互作用網(wǎng)絡(luò)中的相似模塊。生物網(wǎng)絡(luò)比對(duì)對(duì)理解網(wǎng)絡(luò)之間的進(jìn)化關(guān)系、預(yù)測(cè)未知節(jié)點(diǎn)的功能、分析人類(lèi)疾病的機(jī)理等具有重要的意義。生物網(wǎng)絡(luò)比對(duì)問(wèn)題是一個(gè)NP-hard問(wèn)題，因而近似優(yōu)化算法，例如粒子群優(yōu)化算法，是用來(lái)有效求解網(wǎng)絡(luò)比對(duì)問(wèn)題的很好選擇。粒子群優(yōu)化（Particle Swarm Optimization）是一種模擬鳥(niǎo)群協(xié)作覓食行為的群智能方法。粒子群優(yōu)化有實(shí)現(xiàn)簡(jiǎn)單、收斂速度快、不需要問(wèn)題領(lǐng)

2、域知識(shí)等特點(diǎn)。本文利用生物網(wǎng)絡(luò)的特性和粒子群優(yōu)化的優(yōu)點(diǎn)，來(lái)優(yōu)化生物網(wǎng)絡(luò)比對(duì)。本文的主要工作可歸納如下：
　　（1）研究了粒子群優(yōu)化方法的基本理論，提出了基于3-Opt的離散粒子群優(yōu)化算法用來(lái)優(yōu)化生物網(wǎng)絡(luò)比對(duì)。在這個(gè)算法中，針對(duì)網(wǎng)絡(luò)比對(duì)問(wèn)題，設(shè)計(jì)了一種基于排列的粒子群狀態(tài)離散方法；利用了生物網(wǎng)絡(luò)中的樞紐節(jié)點(diǎn)在保持網(wǎng)絡(luò)結(jié)構(gòu)和功能具有重要作用這一特性，提出了一種基于節(jié)點(diǎn)度的初始化方法；分析了生物網(wǎng)絡(luò)比對(duì)中每對(duì)匹配的可交換特性，設(shè)計(jì)了基于

3、3-Opt的局部搜索方法，用來(lái)加快算法的收斂速度。該算法所得的網(wǎng)絡(luò)比對(duì)具有較好的拓?fù)滟|(zhì)量，能夠識(shí)別出較大的最大公共連接子圖。
　?。?）根據(jù)生物不同網(wǎng)絡(luò)中存在一定的具有同源關(guān)系的節(jié)點(diǎn)，以及對(duì)于網(wǎng)絡(luò)比對(duì)匹配網(wǎng)絡(luò)的邊能夠彌補(bǔ)節(jié)點(diǎn)低相似度匹配的不足。提出了一種的基于播種-擴(kuò)展（seed-and-extend）的網(wǎng)絡(luò)相似度分步優(yōu)化策略。應(yīng)用其于粒子群優(yōu)化，設(shè)計(jì)了一種基于播種-擴(kuò)展的離散粒子群優(yōu)化算法用來(lái)優(yōu)化生物網(wǎng)絡(luò)比對(duì)。在該算法中提出了一