Detecting Community Structure in Amino Acid Interaction Networks

Authors: Omar GACI, Stefan BALEV, Antoine DUTOT

Abstract:

In this paper we introduce the notion of protein interaction network. This is a graph whose vertices are the protein-s amino acids and whose edges are the interactions between them. Using a graph theory approach, we observe that according to their structural roles, the nodes interact differently. By leading a community structure detection, we confirm this specific behavior and describe thecommunities composition to finally propose a new approach to fold a protein interaction network.

Keywords: interaction network, protein structure, community structure detection.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1057125

References:

[1] R. Albert, H. Jeong, and A.-L. Barab'asi. The diameter of the world wide web. Nature, 401:130-131, 1999.
[2] A. R. Atilgan, P. Akan, and C. Baysal. Small-world communication of residues and significance for protein dynamics. Biophys J, 86(1 Pt 1):85-91, January 2004.
[3] R. Beatson and L. Greengard. A short course on fast multipole methods.
[4] H. M. Berman, J. Westbrook, Z. Feng, G. Gilliland, T. N. Bhat, H. Weissig, I. N. Shindyalov, and P. E. Bourne. The protein data bank. Nucleic Acids Research, 28:235-242, 2000.
[5] C. Branden and J. Tooze. Introduction to protein structure. Garland Publishing, 1999.
[6] K. V. Brinda and S. Vishveshwara. A network representation of protein structures: implications for protein stability. Biophys J, 89(6):4159- 4170, December 2005.
[7] A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, and J. Wiener. Graph structure in the Web. Computer Networks, 33(1-6):309-320, 2000.
[8] Aaron Clauset, M. E. J. Newman, and Cristopher Moore. Finding community structure in very large networks. Physical Review E, 70:066111, 2004.
[9] N. V. Dokholyan, L. Li, F. Ding, and E. I. Shakhnovich. Topological determinants of protein folding. Proc Natl Acad Sci U S A, 99(13):8637- 8641, June 2002.
[10] Thomas M. J. Fruchterman and Edward M. Reingold. Graph drawing by force-directed placement. Software - Practice and Experience, 21(11):1129-1164, 1991.
[11] O. Gaci and S. Balev. Hubs identification in amino acids interaction networks. In Proceedings of the 7th ACS/IEEE International Conference on Computer Systems and Applications, 2009. 7 pages.
[12] O. Gaci and S. Balev. The small-world model for amino acid interaction networks. In Proceedings of the IEEE AINA 2009, workshop on Bioinformatics and Life Science Modeling and Computing, 2009. 6 pages.
[13] A. Ghosh, K. V. Brinda, and S. Vishveshwara. Dynamics of lysozyme structure network: probing the process of unfolding. Biophys J, 92(7):2523-2535, April 2007.
[14] L. Greengard and V. Rokhlin. A fast algorithm for particle simulations. J. Comput. Phys., 73(2):325-348, 1987.
[15] H. Jeong, B. Tombor, R. Albert, Z. N. Oltvai, and A.-L. Barab'asi. The large-scale organization of metabolic networks. Nature, 407(6804):651- 654, October 2000.
[16] U. K. Muppirala and Z. Li. A simple approach for protein structure discrimination based on the network pattern of conserved hydrophobic residues. Protein Eng Des Sel, 19(6):265-275, June 2006.
[17] M. E. J. Newman. Fast algorithm for detecting community structure in networks. Physical Review E, 69:066133, 2004.
[18] John P. Scott. Social Network Analysis: A Handbook. SAGE Publications, January 2000.
[19] S. Wasserman and K. Faust. Social network analysis : methods and applications , volume 8 of Structural analysis in the social sciences. Cambridge University Press, Cambridge, 1994.
[20] D. J. Watts and S. H. Strogatz. Collective dynamics of -small-world- networks. Nature., 393:440-442, 1998.
[21] Bo Yang and Da You Liu. Incremental algorithm for detecting community structure in dynamic networks. In proceedings of the 4th International Conference on Machine Learning and Cybernetics, pages 2284-2290, August 2005.