生物學網(wǎng)絡中完全子網(wǎng)的抽取及網(wǎng)絡間關系映射.pdf

1、隨著各種實驗手段和技術的發(fā)展，我們可以獲得大量的分子生物學網(wǎng)絡。這些網(wǎng)絡中的拓撲結構對于我們研究分子結構、功能團和進化保守性有著重要的指導意義；而完全子網(wǎng)是我們研究網(wǎng)絡拓撲中最重要的結構之一，它最有可能揭示我們所感興趣的問題。雖然通過圖論知識，我們知道尋找最大完全子網(wǎng)問題是NP-完全問題，但是，我們根據(jù)生物學網(wǎng)絡的無尺度特點，并且利用了動態(tài)規(guī)劃算法的思想，采用了兩個有針對性的算法，從而可以快速的抽取出網(wǎng)絡中的全部完全子網(wǎng)；之后完成這些子

2、網(wǎng)間的匹配關系并建立了映射關系。我們針對DIP(Database of Interacting Proteins)數(shù)據(jù)庫中提供的啤酒酵母(Saccharomyces cerevisiae)蛋白質(zhì)互作分子生物學網(wǎng)絡(2007/4/1版本)，抽取出了全部的完全子網(wǎng)，其中最大規(guī)模的完全子網(wǎng)含有10個蛋白質(zhì)節(jié)點。根據(jù)映射關系，我們預測了8個新的重要互作關系，并在BioGrid數(shù)據(jù)集(2007/6/1版本)和其它文獻中得到了證實，從而將最大完全子

3、網(wǎng)規(guī)模擴大到14個節(jié)點，同時完善了DIP數(shù)據(jù)集(2007/6/3版本數(shù)據(jù)集仍然不包含我們預測的互作關系)。我們得到的完全子網(wǎng)，可以通過KEGG(Kyoto Encyclopedia of Genes and Genomes)來進行功能等方面的進一步分析研究和結果解釋。對于同一物種的兩個生物學網(wǎng)絡，抽取出來的完全子網(wǎng)，可以發(fā)現(xiàn)網(wǎng)絡特征、蛋白復合物或預測基因功能等；對于不同物種的兩個生物學網(wǎng)絡，匹配和映射后的完全子網(wǎng)，可以從系統(tǒng)進化的層面上