不確定生物網(wǎng)絡(luò)比對算法研究.pdf

1、不斷發(fā)展的生物實驗測定技術(shù)產(chǎn)生了越來越多的生物網(wǎng)絡(luò)數(shù)據(jù)，比如蛋白質(zhì)相互作用網(wǎng)絡(luò)、基因轉(zhuǎn)錄調(diào)控網(wǎng)絡(luò)等，這些數(shù)據(jù)中蘊含了大量的關(guān)于各種有機體之間相互影響和相互作用關(guān)系的信息。如何解釋和分析此類生物網(wǎng)絡(luò)數(shù)據(jù)，已經(jīng)成為當前生物信息學領(lǐng)域的一個亟待解決的問題。其中，有一類重要的研究工作就是生物網(wǎng)絡(luò)數(shù)據(jù)的比較，即生物網(wǎng)絡(luò)比對。生物網(wǎng)絡(luò)比對，簡言之就是要尋找兩個（或多個）生物網(wǎng)絡(luò)頂點之間的一組映射關(guān)系，使得生物網(wǎng)絡(luò)之間的相似性得分最高。
　　值

2、得注意的是，由于一些原因，比如生物網(wǎng)絡(luò)中相互作用模塊的規(guī)模、密度、冗余度以及模塊間的距離，甚至生物實驗的誤差，都會導致測量得到的數(shù)據(jù)不完全準確，使得其中含有許多不確定事件（概率事件），比如蛋白質(zhì)相互作用網(wǎng)絡(luò)中的邊是以一定概率存在的，基因轉(zhuǎn)錄調(diào)控網(wǎng)絡(luò)中的DNA也是以一定概率被轉(zhuǎn)錄成為RNA的。因此，在生物網(wǎng)絡(luò)比對過程中，充分考慮和利用不確定信息，使用不確定圖結(jié)構(gòu)刻畫原始網(wǎng)絡(luò)，可以更準確地對現(xiàn)實情況進行建模，從而得到更準確的比對結(jié)果。然而，

3、由于不確定圖的概率特性，這些不確定信息在提高比對結(jié)果準確性的同時，也提高了算法的復(fù)雜度。目前絕大多數(shù)的生物網(wǎng)絡(luò)比對算法都是針對確定生物網(wǎng)絡(luò)比對問題而設(shè)計的，僅有極少數(shù)的算法可以處理不確定生物網(wǎng)絡(luò)數(shù)據(jù)。因此，本論文針對不確定生物網(wǎng)絡(luò)比對進行了研究，主要工作包括:
　　1、本文提出了一種改進的不確定生物網(wǎng)絡(luò)比對算法PBNA(Probabilistic BiologicalNetwork Alignment)。在確定生物網(wǎng)絡(luò)比對算法Is

4、oRank的基本框架之上，PBNA將不確定生物網(wǎng)絡(luò)信息納入到頂點相似性矩陣構(gòu)建過程中，允許參與比對的兩個網(wǎng)絡(luò)中有一個為不確定網(wǎng)絡(luò)，之后應(yīng)用鄰居二分圖(NBG)和貢獻者(Contributor)改進了相似性矩陣計算公式，從而提高了頂點相似性計算的精度，并應(yīng)用概率母函數(shù)降低了求解矩陣內(nèi)每個元素期望的復(fù)雜度。實驗驗證了PBNA能夠得到現(xiàn)有的確定生物網(wǎng)絡(luò)比對算法得不到的比對結(jié)果，并以我們所知的現(xiàn)存唯一的不確定比對算法Prob為參考標準，驗證了P

5、BNA可以在更短的時間內(nèi)得到更具生物意義的比對結(jié)果。
　　2、現(xiàn)有的Prob算法和PBNA算法僅能夠利用到一個生物網(wǎng)絡(luò)中的不確定信息，即只允許參與比對的兩個網(wǎng)絡(luò)其中一個是不確定網(wǎng)絡(luò)。因此，本文進一步提出了“完全的不確定網(wǎng)絡(luò)比對(Complete Probabilistic Alignment)”概念，并將現(xiàn)有的Prob算法與PBNA算法分別改進為完全不確定比對算法Prob CP與PBNA CP。兩種改進的算法分別在原算法的基礎(chǔ)之上