Topological structure analysis of the protein-protein interaction network in budding yeast

Abstract

Interaction detection methods have led to the discovery of thousands of interactions between proteins, and discerning relevance within large-scale data sets is important to present-day biology. Here, a spectral method derived from graph theory was introduced to uncover hidden topological structures (i.e. quasi-cliques and quasi-bipartites) of complicated protein-protein interaction networks. Our analyses suggest that these hidden topological structures consist of biologically relevant functional groups. This result motivates a new method to predict the function of uncharacterized proteins based on the classification of known proteins within topological structures. Using this spectral analysis method, 48 quasi-cliques and six quasi-bipartites were isolated from a network involving 11,855 interactions among 2617 proteins in budding yeast, and 76 uncharacterized proteins were assigned functions.

Figure 1

The topological structures of protein–protein interaction networks. In a quasi-clique, proteins tend to interact with each other (a), while in a quasi-bipartite, proteins between sets have denser interactions than those within sets (b).

Figure 2

The percentage of functional classes of the 48 quasi-cliques. Distribution of the following three classes: main function, percentage of the proteins that have the main function; unknown function, percentage of the uncharacterized proteins; and discordant function, percentage of the proteins that have discordant functions.

Figure 3

Comparison between function prediction and experimental annotation for small subunit (SSU) processome. (A) SSU processome that is supported by experimental evidence (the yellow and the green proteins); (B) our predictions based on quasi-clique 3 (the red proteins and the yellow proteins). The yellow ones are the overlap of (A) and (B). This suggests that our prediction is partly consistent with the experimental evidence (31).

Figure 4

Comparison of different visual representations with and without topological structure. The original protein–protein interaction network is rather miscellaneous and difficult to assimilate (a). The spectral analysis revealed a hidden topological structure underlying the miscellaneous network (b).