Sparse Networks-Based Speedup Technique for Proteins Betweenness Centrality Computation

Authors: Razvan Bocu, Dr Sabin Tabirca

Abstract:

The study of proteomics reached unexpected levels of interest, as a direct consequence of its discovered influence over some complex biological phenomena, such as problematic diseases like cancer. This paper presents the latest authors- achievements regarding the analysis of the networks of proteins (interactome networks), by computing more efficiently the betweenness centrality measure. The paper introduces the concept of betweenness centrality, and then describes how betweenness computation can help the interactome net- work analysis. Current sequential implementations for the between- ness computation do not perform satisfactory in terms of execution times. The paper-s main contribution is centered towards introducing a speedup technique for the betweenness computation, based on modified shortest path algorithms for sparse graphs. Three optimized generic algorithms for betweenness computation are described and implemented, and their performance tested against real biological data, which is part of the IntAct dataset.

Keywords: Betweenness centrality, interactome networks, protein-protein interactions, sub-communities, sparse networks, speedup tech-nique, IntAct.

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

References:

[1] R. Dunn et al., The use of node-clustering to investigate biological function in protein interaction networks. BMC Bioinformatics, 2004.
[2] D. Bader et al., Approximating betweenness centrality. Georgia Institute of Technology, 2007.
[3] D. Meunier and H. Paugam-Moisy, Cluster detection algorithm in neural networks. Institute for cognitive science, BRON, France, 2006.
[4] J. Yoon, A. Blumer and K. Lee, An algorithm for modularity analysis of directed and weighted biological networks based on edge-betweenness centrality. Bioinformatics, 2006.
[5] M.E.J. Newman, Shortest paths, weighted networks, and centrality. Phys- ical review, volume 64, 2001.
[6] M. Girvan and M.E.J. Newman, Community structure in social and biological networks. State University of New Jersey, 2002.
[7] P. Holme et al., Subnetwork hierarchies of biochemical pathways. Bioin- formatics, 2003.
[8] D. Ucar et al., Improving functional fodularity in protein-protein interactions graphs using hub-induced subgraphs. Ohio State University, 2007.
[9] K. Lehmann and M. Kaufmann, Decentralized algorithms for evaluating centrality in complex networks. IEEE, 2002.
[10] J. Griebsch et al., A fast algorithm for the iterative calculation of betweenness centrality. Technical University of Munchen, 2004.
[11] G.H. Traver et al., How complete are current yeast and human proteininteraction networks?. Genome biology, 2006.
[12] R. Bunescu et al., Consolidating the set of known human proteinprotein interactions in preparation for large-scale mapping of the human interactome. Genome biology, 2005.
[13] U. Brandes, A faster algorithm for betweenness centrality. University of Konstanz, 2001.
[14] B. Preiss, Data structures and algorithms with object-oriented design patterns in C++. John Wiley and sons, 1998.
[15] EMBL-EBI, The IntAct protein interactions database. URL: http://www.ebi.ac.uk/intact/site/index.jsf, 2009.
[16] C. Demetrescu et al., The Leonardo Library. URL: http://www.leonardo- vm.org/, 2003.
[17] University of California, The DIP protein interactions database. URL: http://dip.doe-mbi.ucla.edu/, 2009.
[18] Johns Hopkins University, The HPRD protein interactions database. URL: http://www.hprd.org/, 2009.
[19] R. Bocu and S. Tabirca, Betweenness Centrality Computation - A New Way for Analyzing the Biological Systems. Proceedings of the BSB 2009 conference, Leipzig, Germany, 2009.
[20] L.C. Freeman, A set of measures of centrality based on betweenness. Sociometry, Vol. 40, 35-41, 1977.