不確定生物網絡比對算法研究.pdf

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

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

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

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

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