Not AU protein complexes exhibit dense structures in S. cerevisiae PPI network

Various algorithms have been proposed to identify protein complexes from PPI networks, based on the assumption that protein complexes are densely connected subgraphs. In this study, we conclude that most known protein complexes do not exhibit dense structures in S. cerevisiae PPI network, but maintain starlike structures in the network. Moreover, vertices of protein complexes are not sparsely connected with the rest components of the network. Many vertices tend to have more outgoing interactions than they have within protein complexes. Based on starlike properties of known protein complexes, we propose a random-star algorithm to identify protein complexes in PPI networks. Predictions are evaluated in terms of the average f-score. After excluding similar clusters, we finally obtained 744 predictions with the average f-score at 0.51.