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

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

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

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