A Proposal for Graph Theoretic Analysis of Protein- Protein Interaction (PPI) Networks

Protein-Protein Interaction (PPI) networks are commonly represented as undirected graphs with nodes corresponding to proteins and unit-weight edges representing the interactions between two proteins. In an on-going research, we intend to improve the knowledge-base of PPI networks by conducting the following graph theoretic analysis studies: (i) We propose to take an intersection of the PPI network graphs for specific commonly-studied organisms extracted from a set of well-known databases and evaluate properties such as degree distribution, diameter and clustering coefficient of the intersection graph, which will retain only interactions reported in all the databases. (ii) We propose to analyze the correlation between the properties observed for the intersection graph and the functionality of the proteins constituting the different PPI components. (iii) We will develop heuristics to search for different graphlets (connected subnetworks with a smaller number of nodes) in the PPI networks and conduct a frequency distribution analysis of these graphlets to capture the structural similarities in the different PPI networks.