A Seed Expansion Graph Clustering Method for Protein Complexes Detection in Protein Interaction Networks

Area of Science:

• Computational Biology
• Bioinformatics
• Network Science

Background:

• Proteins function through interactions, forming complexes crucial for biological processes.
• Identifying protein complexes aids in understanding biological networks and predicting protein functions.
• Existing methods for protein complex detection in protein-protein interaction (PPI) networks have limitations.

Purpose of the Study:

• To introduce a novel nodal metric integrating local topological information for protein complex detection.
• To propose a seed-expansion graph clustering algorithm (SEGC) for enhanced protein complex identification.
• To improve the accuracy and coverage of protein complex detection in PPI networks.

Main Methods:

• Developed a new nodal metric reflecting a node's local neighborhood representability within a PPI network.
• Proposed the Seed-Expansion Graph Clustering (SEGC) algorithm using a roulette wheel strategy for seed selection.
• Defined a closeness metric (NC) combining cluster density and node-cluster connectivity for cluster expansion.

Main Results:

• The SEGC algorithm demonstrated superior performance compared to existing methods on Saccharomyces cerevisiae PPI networks.
• SEGC achieved higher F-measure and accuracy, particularly under full coverage scenarios.
• The proposed nodal metric effectively captures essential local topological information for complex detection.

Conclusions:

• SEGC is an effective algorithm for detecting protein complexes in protein-protein interaction networks.
• The novel nodal metric and seed-expansion strategy contribute to improved detection accuracy and coverage.
• This work advances computational approaches for understanding protein complex organization and function.