Graph-Theoretical Comparison Reveals Structural Divergence of Human Protein Interaction Networks

Matthias E. Futschik[1] (
Anna Tschaut[2] (
Gautam Chaurasia[1][3] (
Hanspeter Herzel[1] (

[1]Institute for Theoretical Biology, Charite, Humboldt-Universitat, Berlin,Germany
[2]Department of Educational Science and Psychology, Freie Universitat, Berlin, Germany
[3]Max-Delbruck-Center for Molecular Medicine, Berlin-Buch, Berlin, Germany


Protein interactions constitute the backbone of the cellular machinery in living systems. Their biological importance has led to systematic assemblies of large-scale protein-protein interaction maps for various organisms. Recently, the focus of such interactome projects has shifted towards the elucidation of the human interaction network. Several strategies have been employed to gain comprehensive maps of protein interactions occurring in the human body. For their efficient analysis, graph theory has become a favourite tool. It can identify characteristic features of interaction networks which can give us important insights into the general structure of the underlying molecular networks. Although such graph-theoretical analyses have delivered us a variety of interesting results, their general validity remains to be demonstrated. We therefore examined whether independently assembled human interaction networks show common structural features. Remarkably, while some general graph-theoretical features were found, we detected a strong dependency of network structures on the method used to generate the network. Our study strongly indicates that graph-theoretical analysis can be severely compromised by the observed structural divergence and reassessment of earlier results might be warranted.

[ Full-text PDF | Table of Contents ]

Japanese Society for Bioinformatics