復(fù)雜生物網(wǎng)絡(luò)最短路徑計算問題.pdf

1、生命體的組成、生命體活動都不是孤立的，伴隨數(shù)據(jù)庫技術(shù)的發(fā)展，反應(yīng)蛋白質(zhì)、代謝等生命系統(tǒng)組成元件之間相互關(guān)系的數(shù)據(jù)快速增長，這些數(shù)據(jù)關(guān)系由于節(jié)點眾多且節(jié)點連接呈現(xiàn)不規(guī)則特性被稱為復(fù)雜生物網(wǎng)絡(luò)。
　　生命活動的正常進行在分子層面是依賴于以蛋白質(zhì)為核心的物理相互作用和生化反應(yīng)。以美國國立衛(wèi)生研究院（National Institutes of Health，NIH）和歐洲生物信息研究所（European Bioinformatics I

2、nstitute，EBI）為核心的科研機構(gòu)針對蛋白質(zhì)的物理相互作用和生化反應(yīng)建立了一系列的生物醫(yī)學(xué)數(shù)據(jù)庫。這些數(shù)據(jù)庫主要包括生化反應(yīng)的HMDB（Human Metabolome Database）、Reactome等以及物理相互作用的HPRD（Human Protein Reference Database）、IntAct等。蛋白質(zhì)在這些數(shù)據(jù)庫中形成龐大復(fù)雜的相互作用網(wǎng)絡(luò)。這些以蛋白質(zhì)為核心的復(fù)雜網(wǎng)絡(luò)為科學(xué)研究提供了龐大的背景知識，然而

3、，針對具體的科研問題通常只涉及到小部分的蛋白質(zhì)，這小部分的蛋白質(zhì)往往難以構(gòu)成完整的相互作用網(wǎng)絡(luò)。為了在分子層面探索這部分蛋白質(zhì)完整的相互作用，進而需要在背景網(wǎng)絡(luò)上找到小部分蛋白的“橋接蛋白質(zhì)”。“橋接蛋白質(zhì)”的查找，原則上應(yīng)該以最短路徑為目的，最短路徑計算的經(jīng)典算法是Dijkstra。本文將Dijkstra算法應(yīng)用到HPRD、CORUM和Reactome數(shù)據(jù)庫中，計算任意兩個蛋白質(zhì)間的最短路徑，并給出復(fù)雜生物網(wǎng)絡(luò)的網(wǎng)絡(luò)特征：蛋白質(zhì)的度分