由蛋白質交互網路中探勘可重疊之密集子網路

近來有許多高輸出的實驗可以幫我們偵測蛋白質之間的互動關係，利用這些資料，生物學家可以建立起蛋白質交互網路。如果可以從這些網路中找出蛋白質複合體將有助於我們瞭解生物的運作機制；因此，本論文提出了一個新的方法，這個方法包含了四個步驟。首先，我們計算網路中每個節點的加權連線數，並且選擇最高的那個節點當成種子；在第二個步驟，我們利用貪婪演算法找到一個密集的子網路；在第三個步驟裡，我們調整網路中連線的權重並且重新計算各個節點的加權連線數以及加權連線數的比例；在最後一個步驟，我們重複第一到第三步驟直到我們找不出任何密集的子網路為止。在我們的方法中，我們並不移除網路中任何的節點與連線，因此我們可以找出比CODENSE方法更多的重疊子網路，除此之外，實驗結果亦說明我們可以比CODENSE找到更多的蛋白質複合體。

關鍵字

蛋白質交互網路；蛋白質複合體；貪婪演算法；重疊的密集子網路

並列摘要

Many high throughput experiments have been used to detect protein interactions which can be used to a protein-protein interaction network. To recognize the protein complexes in a protein-protein interaction network can help us understand the mechanisms of the biological processes. In this thesis, we proposed a novel method with four phases to mine the protein complexes in the protein-protein interaction network. First, we calculate the weighted degree for each vertex in the network and pick the vertex with the highest weighted degree as the seed vertex. Second, we find a dense subgraph based on the greedy algorithm. Third, we modify the edge weights in the network and compute the weighted degree and the ratio of weighted degree for each vertex in the network. Finally, we repeat the above phases until no more dense subgraph can be found. Our proposed method does not remove any vertex and edge as a subgraph has been found. Therefore our method can mine more overlapping subgraphs than the CODENSE method. The experiment results show that our proposed method can find more protein complexes than the CODENSE method.

並列關鍵字

protein-protein interaction network ； protein complex ； greedy algorithm ； overlapping dense subgraph

參考文獻

[1] Asahiro, Y., Iwama, K., Yamaki, H. and Tokuyama, T., “Greedily finding a dense subgraph,” Journal of Algorithms, Vol. 34, pp. 203-221, 2000.

[2] Bader, G.D. and Hogue, C.W., “An automated method for finding molecular complexes in large protein interaction networks,” BMC Bioinformatics, Vol. 4, No. 2, 2003.

[3] Barabasi, A.L. and Oltvai, Z.N., “Network biology: understanding the cell’s functional organization,” Nature Reviews Genetics, Vol. 5, pp. 101-113, 2004.

[4] Barrat, A., Barthelemy, M., Pastor-Satorras, R. and Vespignani, A., “The architecture of complex weighted networks,” Proceedings of the National Academy of Sciences of the United States of America, Vol. 101, pp. 3747-3752, 2004.

[5] Charikar, M., “Greedy approximation algorithms for finding dense components in a graph,” Lecture Notes in Computer Science, Vol. 1913, pp. 139-152, 2000.

國際替代計量

由蛋白質交互網路中探勘可重疊之密集子網路

全文下載

主題瀏覽