Sparse Networks-Based Speedup Technique for Proteins Betweenness Centrality Computation

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.

Authors:

• Razvan Bocu
• Dr Sabin Tabirca

Keywords:

• Betweenness centrality
• interactome networks
• protein-protein interactions
• sub-communities
• sparse networks
• speedup tech-nique
• IntAct.

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.