Protein Complex Detection by Seed-expansion Method Based on Random Walk with Restart

Abstract

Proteins form complexes to perform their functions in the living system. Many graph-based clustering methods have been used to detect complexes from protein-protein interaction networks (PPIs). However, it is difficult to find hundreds of complexes of various structures from large and disordered PPIs. This paper proposes a novel approach for complexes detection based on Random Walk with Restart (CDRWR) since RWR can find the global relevance similarity between nodes. CDRWR firstly uses the similarity to weight the edges of PPIs and expands the significant complex seeds from every node to ensure the complexes integrity. The external protein nodes are included by comparing the density, and a merging method is applied to confirm the final protein complexes. Experiments are conducted to compare CDRWR with existing methods on a few yeast PPIs datasets according to two evaluation criteria, F1-score and NMI (Normalized Mutual Information), and the results show that it has the best performance in accuracy.