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

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

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

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

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

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