PLW: Probabilistic Local Walks for detecting protein complexes from protein interaction networks

Area of Science:

• Bioinformatics
• Computational Biology
• Systems Biology

Background:

• Protein complexes are crucial for biological processes.
• Experimental detection of protein complexes is limited.
• Computational methods using protein-protein interaction (PPI) networks are vital alternatives.

Purpose of the Study:

• To develop a novel computational method for detecting protein complexes in PPI networks.
• To address limitations in existing algorithms regarding seed selection and functional homogeneity.
• To improve the precision and efficiency of protein complex identification.

Main Methods:

• Developed Probabilistic Local Walks (PLW), a clustering algorithm for PPI networks.
• Implemented a seed selection strategy prioritizing nodes with dense neighborhoods.
• Defined 'common neighbor similarity' to estimate functional similarity between proteins.

Main Results:

• PLW achieved high precision and efficiency in identifying protein complex cores.
• The algorithm runs in O(|V| log |V| + |E|) time.
• The seed selection strategy enhanced precision when applied to other protein complex mining techniques.

Conclusions:

• PLW significantly outperformed 11 state-of-the-art methods on yeast PPI data, achieving the highest F-measure.
• The proposed seed selection strategy demonstrably improved algorithm precision.
• PLW offers a precise and efficient approach to computational protein complex detection.