David A. Bader
IEEE Fellow
AAAS Fellow
Professor
College of Computing
Georgia Tech
Atlanta, GA 30332


 
 

 

A Graph-Theoretic Analysis of the Human Protein-Interaction Network Using Multi-core Parallel Algorithms

Protein-interaction network (PIN) analysis provides valuable insight into an organismís functional organization and evolutionary behavior. In this paper, we study a PIN formed by high-confidence human protein interactions obtained from various public interaction databases. This is the largest human PIN studied to date, comprising nearly 18,000 proteins and 44,000 interactions. A novel contribution of this paper is the computation of betweenness centrality, a graph-theoretic metric that is found to be positively correlated with the essentiality and evolutionary age of a protein. We observe that proteins with high betweenness centrality, but low connectivity are abundant in the human PIN. We have designed an efficient and portable parallel implementation for the calculation of this compute-intensive centrality metric. On the Sun Fire T2000 server with the UltraSparc T1 (Niagara) processor, we achieve a relative speedup of about 16 using 32 threads for a typical instance of betweenness centrality, reducing the running time from several minutes to 13 seconds.

Publication History

Versions of this paper appeared as:
  1. D.A. Bader and K. Madduri, ``A Graph-Theoretic Analysis of the Human Protein-Interaction Network Using Multi-core Parallel Algorithms,'' Sixth IEEE International Workshop on High Performance Computational Biology (HiCOMB), Long Beach, CA, March 26, 2007.

Download this report in Adobe PDF


 
 

Last updated: February 26, 2007

 




Computational Biology



Parallel Computing



Combinatorics