Complex discovery from weighted PPI networks

被引:375
作者
Liu, Guimei [1 ]
Wong, Limsoon [1 ]
Chua, Hon Nian [2 ]
机构
[1] Natl Univ Singapore, Sch Comp, Singapore 117548, Singapore
[2] Inst Infocomm Res, Singapore, Singapore
基金
新加坡国家研究基金会;
关键词
PROTEIN-INTERACTION NETWORKS; ALGORITHM; CLIQUES;
D O I
10.1093/bioinformatics/btp311
中图分类号
Q5 [生物化学];
学科分类号
071010 ; 081704 ;
摘要
Motivation: Protein complexes are important for understanding principles of cellular organization and function. High-throughput experimental techniques have produced a large amount of protein interactions, which makes it possible to predict protein complexes from protein-protein interaction (PPI) networks. However, protein interaction data produced by high-throughput experiments are often associated with high false positive and false negative rates, which makes it difficult to predict complexes accurately. Results: We use an iterative scoring method to assign weight to protein pairs, and the weight of a protein pair indicates the reliability of the interaction between the two proteins. We develop an algorithm called CMC (clustering-based on maximal cliques) to discover complexes from the weighted PPI network. CMC first generates all the maximal cliques from the PPI networks, and then removes or merges highly overlapped clusters based on their interconnectivity. We studied the performance of CMC and the impact of our iterative scoring method on CMC. Our results show that: (i) the iterative scoring method can improve the performance of CMC considerably; (ii) the iterative scoring method can effectively reduce the impact of random noise on the performance of CMC; (iii) the iterative scoring method can also improve the performance of other protein complex prediction methods and reduce the impact of random noise on their performance; and (iv) CMC is an effective approach to protein complex prediction from protein interaction network.
引用
收藏
页码:1891 / 1897
页数:7
相关论文
共 34 条
[1]   CFinder:: locating cliques and overlapping modules in biological networks [J].
Adamcsek, B ;
Palla, G ;
Farkas, IJ ;
Derényi, I ;
Vicsek, T .
BIOINFORMATICS, 2006, 22 (08) :1021-1023
[2]   Structure-based assembly of protein complexes in yeast [J].
Aloy, P ;
Böttcher, B ;
Ceulemans, H ;
Leutwein, C ;
Mellwig, C ;
Fischer, S ;
Gavin, AC ;
Bork, P ;
Superti-Furga, G ;
Serrano, L ;
Russell, RB .
SCIENCE, 2004, 303 (5666) :2026-2029
[3]   Development and implementation of an algorithm for detection of protein complexes in large interaction networks [J].
Altaf-Ul-Amin, Md ;
Shinbo, Yoko ;
Mihara, Kenji ;
Kurokawa, Ken ;
Kanaya, Shigehiko .
BMC BIOINFORMATICS, 2006, 7 (1)
[4]   Gene Ontology: tool for the unification of biology [J].
Ashburner, M ;
Ball, CA ;
Blake, JA ;
Botstein, D ;
Butler, H ;
Cherry, JM ;
Davis, AP ;
Dolinski, K ;
Dwight, SS ;
Eppig, JT ;
Harris, MA ;
Hill, DP ;
Issel-Tarver, L ;
Kasarskis, A ;
Lewis, S ;
Matese, JC ;
Richardson, JE ;
Ringwald, M ;
Rubin, GM ;
Sherlock, G .
NATURE GENETICS, 2000, 25 (01) :25-29
[5]   An automated method for finding molecular complexes in large protein interaction networks [J].
Bader, GD ;
Hogue, CW .
BMC BIOINFORMATICS, 2003, 4 (1)
[6]   Evaluation of clustering algorithms for protein-protein interaction networks [J].
Brohee, Sylvain ;
van Helden, Jacques .
BMC BIOINFORMATICS, 2006, 7 (1)
[7]   Functional classification of proteins for the prediction of cellular function from a protein-protein interaction network [J].
Christine Brun ;
François Chevenet ;
David Martin ;
Jérôme Wojcik ;
Alain Guénoche ;
Bernard Jacq .
Genome Biology, 5 (1)
[8]   Discovering reliable protein interactions from high-throughput experimental data using network topology [J].
Chen, J ;
Hsu, W ;
Lee, ML ;
Ng, SK .
ARTIFICIAL INTELLIGENCE IN MEDICINE, 2005, 35 (1-2) :37-47
[9]  
Chen Jin, 2006, Genome Inform, V17, P284
[10]  
Chua Hon Nian, 2008, Journal of Bioinformatics and Computational Biology, V6, P435, DOI 10.1142/S0219720008003497