Restructuring protein interaction networks to reveal structural hubs and functional organizations

Protein interaction networks are significant resources for functional knowledge discovery. However, efficient analysis of the networks has been challenging because of complex connectivity. Protein interaction networks have been characterized by intrinsic features, such as modularity and existence of hubs. The concepts of modules and hubs, extending from specific (local) to general (global), suggest hierarchical structures hidden in the complex networks. Retrieving a protein interaction network into the hierarchical structure is thus a crucial process for better understanding of functional organizations. We present a novel approach for restructuring a protein interaction network to reveal hierarchically organized functional modules and hubs. Our algorithm measures functional similarity between proteins based on the path strength model, and dynamically convert a protein interaction network into a hub-oriented tree structure using the definition of centrality. We identify structural hubs and potential functional modules from the tree structure generated by our algorithm. The experimental results demonstrate that the proteins selected as structural hubs are essential for performing functions. In network topology, they have a role in bridging different modules. Furthermore, our approach has higher accuracy in identifying functional modules than other hierarchical clustering methods.