An Improved Graph Entropy-based Method for Identifying Protein Complexes

Protein complexes are essential entities that per form the major cellular processes and biological functions in live organisms. The identification of component proteins in a complex from protein-protein interaction (PPI) networks is an important step to understand the organization and interaction of gene products. In existing literature, methods for identifying protein complexes typically start from a selected seed, commonly a vertex (a single protein), in a PPI network. However, in many circumstances, a single protein seed is not enough to generate a meaningful complex, or more than one protein is known in a complex. In this paper, we present an improved seed-growth style algorithm to identify protein complexes from PPI networks based on the concept of graph entropy. Different from existing methods, the seed is assumed to be a clique (e.g., a vertex, an edge, a triangle) in a PPI network. The computational experiments have been conducted on PPI network of S. cerevisiae. The results have shown that the larger cliques are considered as seeds, the better the presented method performs in terms off-score. In particular, up to K₃-cliques are included as seeds, the average f-score is 57.32%, which is better than that of existing methods.