An efficient protein complex mining algorithm based on Multistage Kernel Extension.

Area of Science:

• Bioinformatics
• Computational Biology
• Systems Biology

Background:

• Protein complex identification is crucial for understanding cellular functions.
• Existing algorithms like Clique Percolation Method (CPM) and Markov Clustering (MCL) focus on dense subgraphs, neglecting internal organizational structures.
• Protein-protein interaction (PPI) networks require novel mining approaches that leverage topological information.

Purpose of the Study:

• To develop a new algorithm for mining protein complexes from PPI networks.
• To incorporate edge topological information and critical protein recognition into complex mining.
• To address the limitations of existing methods in capturing the inherent organization of protein complexes.

Main Methods:

• Propose the Multistage Kernel Extension (MKE) algorithm, inspired by social network clique formation and centrality-lethality rules.
• MKE identifies high-degree nodes as initial kernels and iteratively expands them by incorporating weighted neighbors.
• Overlapping complexes are merged to generate the final set of identified protein complexes.

Main Results:

• The MKE algorithm demonstrates superior accuracy compared to CPM and MCL.
• MKE shows improved performance over CPM in Gene Ontology semantic similarity and co-localization enrichment analyses.
• The algorithm effectively identifies biologically significant protein complexes within PPI networks.

Conclusions:

• MKE offers a novel approach to protein complex mining by utilizing edge topological information.
• The algorithm's ability to recognize critical proteins enhances its accuracy and biological relevance.
• MKE provides a valuable tool for dissecting complex biological systems through PPI network analysis.