Abstract
The availability of large volumes of protein-protein interaction data has allowed the study of biological networks to unveil the complex structure and organization in the cell. It has been recognized by biologists that proteins interacting with each other often participate in the same biological processes, and that protein modules may be often associated with specific biological functions. Thus the detection of protein complexes is an important research problem in systems biology. In this review, recent graph-based approaches to clustering protein interaction networks are described and classified with respect to common peculiarities. The goal is that of providing a useful guide and reference for both computer scientists and biologists.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
- Community Detection
- Protein Interaction Network
- Complex Detection
- Protein Interaction Data
- Dense Subgraph
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Adamcsek, B., Palla, G., Farkas, I.J., Dernyi, I., Vicsek, T.: Cfinder: locating cliques and overlapping modules in biological networks. Bioinformatics 22(8), 1021–1023 (2006)
Aittokallio, B., Schwikowski, B.: Graph-based methods for analyzing networks in cell biology. Briefing in Bioinformatics 7(3), 243–255 (2006)
Altaf-Ul-Amin, M., Shinbo, Y., Mihara, K., Kurokawa, K., Kanaya, S.: Development and implementation of an algorithm for detection of protein complexes in large interaction networks. BMC Bioinformatics 7(207) (2006)
Arnau, V., Mars, S., Marìn, I.: Iterative cluster analysis of protein interaction data. Bioinformatics 21(3), 364–378 (2005)
Asburner, S., Ball, C.A., Blake, J.A., Botstein, D., Butler, H., et al.: Gene ontology: tool for the unification of biology. the gene ontology consortium. Nature Genetics 25, 25–29 (2000)
Bader, G., Hogue, H.: An automated method for finding molecular complexes in large protein-protein interaction networks. BMC Bioinformatics 4(2) (2003)
Blatt, M., Wiseman, S., Domany, E.: Superparamagnetic clustering of data. Phisical Review Letters 76(18), 3251–3254 (1996)
Brohèe, S., van Helden, J.: Evaluation of clustering algorithms for protein-protein interaction networks. BMC Bioinformatics 7, 488 (2006)
Ceol, A., et al.: Mint, the molecular interaction database: 2009 update. Nucleic Acids Research 38(Database issue), D532–D539 (2010)
Cho, Y.-R., Hwang, W., Zhang, A.: Identification of overlapping functional modules in protein interaction networks: Information flow-based approach. In: Proc. of the Sixth Int. Conf. on Data Mining-Workshops, ICDMW 2006 (2006)
Chua, H.N., Ning, K., Sung, W.K., Leong, H.W., Wong, L.: Using indirect protein-protein interactions for protein complex prediction. In: Proceedings of Computational Systems Bioinformatics Conference (CSB 2007), pp. 97–109 (2007)
Derenyi, I., Palla, G., Vicsek, T.: Clique percolation in random networks. Physical Review Letters 94(16), 160–202 (2005)
Enright, A.J., Dongen, S.V., Ouzounis, C.A.: An efficient algorithm for large-scale detection of protein families. Nucleic Acids Research 30(7), 1575–1584 (2002)
Farutin, V., Robinson, K., Lightcap, E., Dancik, V., Ruttenberg, A., Letovsky, S., Pradines, J.: Edge-count probabilities for the identification of local protein communities and their organization. Proteins: Structure, Function, and Bioinformatics 62, 800–818 (2006)
Fortunato, S.: Community detection in graphs. Physics Reports 486, 75–174 (2010)
Georgii, E., Dietmann, S., Uno, T., Pagel, P., Tsuda, K.: Enumeration of condition-dependent dense modules in protein interaction networks. Bioinformatics 25(7), 933–940 (2009)
Girvan, M., Newman, M.E.J.: Community structure in social and biological networks. Proc. National. Academy of Science USA 99, 7821–7826 (2002)
Hartwell, L.H., Hopfield, J.J., Leibler, S., Murray, A.W.: Clustering algorithm based graph connectivity. Nature 402, C47–C52 (1999)
Hwang, W., Cho, Y.-R., Zhang, A., Ramanathan, M.: A novel functional module detection algorithm for protein-protein interaction networks. Algorithms for Molecular Biology 1(24) (2006)
Jain, R.D.A.: Algorithms for Clustering Data. Prentice-Hall (1988)
Jancura, P., Marchiori, E.: Detecting high quality complexes in a PPI network by edge deletion and node expansion. In: CIBB (2011)
Jancura, P., Mavridou, E., Carrillo-De Santa Pau, E., Marchiori, E.: A methodology for detecting the orthology signal in a ppi network at a functional complex level. BMC Bioinformatics (2011) (accepted for publication)
Jiang, P., Singh, M.: SPICi: a fast clustering algorithm for large biological networks. Bioinformatics 26(8), 1105–1111 (2010)
King, A.D., Przulj, N., Jurisica, I.: Protein complex prediction via cost-based clustering. Bioinformatics 20(17), 3013–3020 (2004)
Kovacs, I.A., Palotai, R., Szalay, M.S., Csermely, P.: Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics. PLoS ONE 5(9) (2010)
Li, X.L., Foo, C.S., Ng, S.K.: Discovering protein complexes in dense reliable neighborhoods of protein interaction networks. In: Proceedings of Computational Systems Bioinformatics Conference (CSB 2007), pp. 157–168 (2007)
Li, X.L., Wu, M., Kwoh, C.K., Ng, S.K.: Computational approaches for detecting protein complexes from protein interaction network: a survey. BMC Bioinformatics 9 (2010)
Lin, C., Cho, Y., Hwang, W., Pei, P., Zhang, A.: Clustering methods in protein-protein interaction network. In: Knowledge Discovery in Bioinformatics: Techniques, Methods and Application. John Wiley & Sons, Inc., (2006)
Liu, H., Liu, J.: Clustering Protein Interaction Data Through Chaotic Genetic Algorithm. In: Wang, T.-D., Li, X., Chen, S.-H., Wang, X., Abbass, H.A., Iba, H., Chen, G.-L., Yao, X. (eds.) SEAL 2006. LNCS, vol. 4247, pp. 858–864. Springer, Heidelberg (2006)
Lubovac, Z., Gamalielsson, J., Olsson, B.: Combining functional and topological properties to identify core modules in protein interaction networks. Proteins: Structure, Function, and Bioinformatics 64, 948–959 (2006)
Macropol, K., Can, T., Singh, A.: Rrw: repeated random walks on genome-scale protein networks for local cluster discovery. BMC Bioinformatics 10(1), 283 (2009)
Madeira, S.C., Oliveira, A.L.: Biclustering algorithms for biological data analysis: A survey. IEEE Trans. on Comp. Biol. and Bioinf. 1(1), 24–45 (2004)
Palla, G., Derenyi, I., Farkas, I., Vicsek, T.: Uncovering the overlapping community structure of complex networks in nature and society. Nature 435, 814–818 (2005)
Pavlopoulos, G.A., Secrier, M., Moschopoulos, C.N., Soldatos, T.G., Kossida, S., Aert, J., Schneider, R., Bagos, P.G.: Using graph theory to analyze biological networks. BioData Mining 4(10) (2011)
Pei, P., Zhang, A.: A two-step approach for clustering proteins based on protein interaction profiles. In: IEEE Int. Symposium on Bioinformatics and Bioengeneering (BIBE 2005), pp. 201–209 (2005)
Pereira, J.B., Enright, A.J., Ouzounis, C.A.: Detection of functional modules from protein interaction networks. Proteins: Structure, Fuctions, and Bioinformatics (20), 49–57 (2004)
Pizzuti, C.: GA-Net: A Genetic Algorithm for Community Detection in Social Networks. In: Rudolph, G., Jansen, T., Lucas, S., Poloni, C., Beume, N. (eds.) PPSN 2008. LNCS, vol. 5199, pp. 1081–1090. Springer, Heidelberg (2008)
Pizzuti, C., Rombo, S.E.: PINCoC: A Co-clustering Based Approach to Analyze Protein-Protein Interaction Networks. In: Yin, H., Tino, P., Corchado, E., Byrne, W., Yao, X. (eds.) IDEAL 2007. LNCS, vol. 4881, pp. 821–830. Springer, Heidelberg (2007)
Pizzuti, C., Rombo, S.E.: Multi-functional protein clustering in ppi networks. In: Proc. of the 2nd Int. Conf. on Bioinf. Res. and Dev. (BIRD 2008), pp. 318–330 (2008)
Pizzuti, C., Rombo, S.E.: Discovering Protein Complexes in Protein Interaction Networks in Biological Data Mining in Protein Interaction Networks. In: Li, X.-L., Ng, S.-K. (eds.) IGI Global- Medical Inf. Science Ref. (2009)
Przulj, N.: Functional topology in a network of protein interactions. In: Jurisica, I., Wigle, D. (eds.) Knowledge Discovery in Proteomics. CRC Press (2005)
Ravaee, H., Masoudi-Nejad, A., Omidi, S., Moeini, A.: Improved immune genetic algorithm for clustering protein-protein interaction network. In: Proceedings of the 2010 IEEE International Conference on Bioinformatics and Bioengineering, BIBE 2010, pp. 174–179. IEEE Computer Society (2010)
Rives, A.W., Galitski, T.: Modular organization of cellular networks. Proc. of the National Academy of Science 100(3), 1128–1133 (2003)
Ruan, J., Zhang, W.: Identifying network communities with a high resolution. Physical Review E 77(1) (January 2008)
Samantha, M.P., Liang, S.: Predicting protein functions from redundancies in large-scale protein interaction networks. Proc. of the National Academy of Science 100(22), 12579–12583 (2003)
Tasgin, M., Bingol, H.: Community detection in complex networks using genetic algorithm. arXiv:0711.0491, 2007 (2007)
Tornw, S., Mewes, H.W.: Functional modules by relating protein interaction networks and gene expression. Nucleic Acids Research 31(21), 6283–6289 (2003)
von Mering, D., Krause, C., et al.: Comparative assessment of a large-scale data sets of protein-protein interactions. Nature 31, 399–403 (2002)
Wang, J., Li, M., Deng, Y., Pan, Y.: Recent advances in clustering methods for protein interaction networks. BMC Genomics 11(S10) (2010)
Zhang, S., Chen, H., Liu, K., Sun, Z.: Inferring protein function by domain context similarities in protein-protein interaction networks. BMC Bioinformatics 10, 395 (2009)
Zhao, Y., Levina, E., Zhu, J.: Community extraction for social networks. Proceedings of the National Academy of Sciences 108(18), 7321–7326 (2011)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Pizzuti, C., Rombo, S.E., Marchiori, E. (2012). Complex Detection in Protein-Protein Interaction Networks: A Compact Overview for Researchers and Practitioners. In: Giacobini, M., Vanneschi, L., Bush, W.S. (eds) Evolutionary Computation, Machine Learning and Data Mining in Bioinformatics. EvoBIO 2012. Lecture Notes in Computer Science, vol 7246. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-29066-4_19
Download citation
DOI: https://doi.org/10.1007/978-3-642-29066-4_19
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-29065-7
Online ISBN: 978-3-642-29066-4
eBook Packages: Computer ScienceComputer Science (R0)