Entropy-Based Clustering Algorithm For Module Detection In PPI Networks

Accumulating evidence suggests that biological systems are composed ofinteracting, separable, functional modules—groups of vertices within whichconnections are dense but between which they are sparse.Identification of functional modules in protein-protein interaction (PPI) networksis the first step in understanding the organization and dynamics of cell functions. In thisresearch, we further evaluate a general criterion to define and measure a functionalmodule. Entropy is often used to measure the amount of “disorder” of a system, thelower the entropy, the more stable the system. We hope that each functional module hasa lower entropy because vertices in the same functional module should look similar, andthe functional module is more stabile. This paper proposes an efficient algorithm basedon minimum weighted similarity entropy criterion for the functional modules detectionin PPI networks. Using this criterion, we transform the topology similarity intosimilarity entropy, both of which can be defined by us. That is, the larger the topologysimilarity, the lower the entropy similarity. From this, we use the similarity entropycriterion to cluster vertices into functional modules which has a minimum weightedsimilarity entropy. We test our algorithm in yeast PPI networks. The result suggests thatmost of modules available have good biological significance in the function annotationand prediction, which outperforms other classical algorithms in two aspects-genematches and p-value. Further, we also test our method in artificial networks and socialnetworks, whose results demonstrate that our algorithm has good reliability androbustness.