Complex cellular processes are accomplished by the concerted action of hierarchically organized functional modules. Protein complexes are major components which act as highly specialized molecular machines. Here we present a statistical procedure to find insightful substructures in protein complexes based on large-scale protein complex data: we identify statistically significant common protein subcomplexes (SCs) contained in different protein complexes. We analyze recently published data of the two model organisms Saccharomyces cerevisiae (four different data sets) and Escherichia coli, as well as human protein complex data. Our method identifies well-characterized protein assemblies with known functions which act as own functional entities in the cell. In addition, we also identified hitherto unknown functional entities that should be studied experimentally in future. We discuss two typical properties of protein subcomplexes: 1) subcomplexes are enriched with essential proteins (which implies that the whole SCs may be strongly conserved) and 2) SCs are functionally and spatially more homogeneous than the experimentally found protein assemblies. The latter property is exploited to propose functions for so far unknown proteins of S. cerevisiae.
