李瑞庭臺灣大學：資訊管理學研究所許家銘Hsu, Chia-MingChia-MingHsu2007-11-262018-06-292007-11-262018-06-292007http://ntur.lib.ntu.edu.tw//handle/246246/54233近來有許多高輸出的實驗可以幫我們偵測蛋白質之間的互動關係，利用這些資料，生物學家可以建立起蛋白質交互網路。如果可以從這些網路中找出蛋白質複合體將有助於我們瞭解生物的運作機制；因此，本論文提出了一個新的方法，這個方法包含了四個步驟。首先，我們計算網路中每個節點的加權連線數，並且選擇最高的那個節點當成種子；在第二個步驟，我們利用貪婪演算法找到一個密集的子網路；在第三個步驟裡，我們調整網路中連線的權重並且重新計算各個節點的加權連線數以及加權連線數的比例；在最後一個步驟，我們重複第一到第三步驟直到我們找不出任何密集的子網路為止。在我們的方法中，我們並不移除網路中任何的節點與連線，因此我們可以找出比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.Tables of Contents i List of Figures ii List of Tables iii Chapter 1 Introduction 1 Chapter 2 Preliminaries and Problem Definitions 4 Chapter 3 Our Proposed Method 7 3.1 The procedure of finding a dense subgraph 7 3.2 The procedure of choosing a seed vertex 7 3.3 The procedure of growing a subgraph 9 3.4 Weight modification 11 3.5 The ratio of weighted degree 12 3.6 The proposed method 13 3.7 An example 14 Chapter 4 Performance Analysis 17 4.1 Dataset and parameter settings 17 4.2 Performance evaluation for the first experiment 18 4.3 Performance evaluation for the second experiment 21 4.4 Discovering biological function modules 22 Chapter 5 Concluding Remarks 24 References 25415420 bytesapplication/pdfen-US蛋白質交互網路蛋白質複合體貪婪演算法重疊的密集子網路protein-protein interaction networkprotein complexgreedy algorithmoverlapping dense subgraphotherhttp://ntur.lib.ntu.edu.tw/bitstream/246246/54233/1/ntu-96-R94725031-1.pdf