Mining Protein Complexes from PPI Networks Using the Minimum Vertex Cut  

作　　者：Xiaojun Ding Weiping Wang Xiaoqing Peng Jianxin Wang 

机构地区：[1]School of Information Science and Engineering, Central South University, Changsha 410083, China [2]Department of Computer Science, Georgia State University, Atlanta, GA 30302, USA

出　　处：《Tsinghua Science and Technology》2012年第6期674-681,共8页清华大学学报（自然科学版（英文版）

基　　金：Supported in part by the National Natural Science Foundation of China (Nos.61232001 and 61073036)

摘　　要：Evidence shows that biological systems are composed of separable functional modules. Identifying protein complexes is essential for understanding the principles of cellular functions. Many methods have been proposed to mine protein complexes from protein-protein interaction networks. However, the performances of these algorithms are not good enough since the protein-protein interactions detected from experiments are not complete and have noise. This paper presents an analysis of the topological properties of protein complexes to show that although proteins from the same complex are more highly connected than proteins from different complexes, many protein complexes are not very dense （density ≥0.8）. A method is then given to mine protein complexes that are relatively dense （density ≥0.4）. In the first step, a topology property is used to identify proteins that are probably in a same complex. Then, a possible boundary is calculated based on a minimum vertex cut for the protein complex. The final complex is formed by the proteins within the boundary. The method is validated on a yeast protein-protein interaction network. The results show that this method has better performance in terms of sensitivity and specificity compared with other methods. The functional consistency is also good.Evidence shows that biological systems are composed of separable functional modules. Identifying protein complexes is essential for understanding the principles of cellular functions. Many methods have been proposed to mine protein complexes from protein-protein interaction networks. However, the performances of these algorithms are not good enough since the protein-protein interactions detected from experiments are not complete and have noise. This paper presents an analysis of the topological properties of protein complexes to show that although proteins from the same complex are more highly connected than proteins from different complexes, many protein complexes are not very dense （density ≥0.8）. A method is then given to mine protein complexes that are relatively dense （density ≥0.4）. In the first step, a topology property is used to identify proteins that are probably in a same complex. Then, a possible boundary is calculated based on a minimum vertex cut for the protein complex. The final complex is formed by the proteins within the boundary. The method is validated on a yeast protein-protein interaction network. The results show that this method has better performance in terms of sensitivity and specificity compared with other methods. The functional consistency is also good.

关 键 词：protein complex protein-protein interaction network minimum vertex cut 

分 类 号：Q510.1[生物学—生物化学] S511.01[农业科学—作物学]