PC2P

PC2P predicts protein complexes in protein-protein interaction networks (PPINs) by partitioning networks into biclique spanned subgraphs to capture both sparse and dense complex structures.

Key Features:

• Network clustering for PPINs: Operates on protein-protein interaction networks to detect candidate protein complexes.
• Biclique spanned subgraph modeling: Formalizes protein complexes as biclique spanned subgraphs rather than solely dense subgraphs.
• Coherent partition via minimum-edge removal: Partitions the network by removing the minimum number of edges required to achieve a coherent partition into biclique spanned subgraphs.
• Parameter-free greedy approximation algorithm: Uses a parameter-free greedy approximation algorithm to address the computational intractability of finding an optimal coherent partition.
• Handles sparse and dense structures: Explicitly accounts for both sparse and dense subgraph structures present in known complexes.
• Modular structure identification: Identifies modular structures within networks as a prerequisite for complex prediction.
• Benchmark performance on yeast and human gold standards: Demonstrated improved performance relative to other methods on analyzed PPI networks and gold standards, with reported gains on 75% of yeast and 100% of human cases.
• Functional coherence assessment: Maintains high Gene Ontology (GO) semantic similarity and enrichment scores for predicted complexes.

Scientific Applications:

• Protein complex prediction: Predicts candidate protein complexes from PPINs for downstream biological analysis.
• PPI network structure analysis: Analyzes modular and biclique-based substructures in yeast and human PPI networks and gold standards.
• Functional validation of predicted complexes: Supports evaluation of predicted complexes using GO semantic similarity and enrichment metrics.

Methodology:

Partition the network into biclique spanned subgraphs by removing the minimum number of edges to obtain a coherent partition, and approximate the intractable optimal partition using a parameter-free greedy algorithm that leverages properties of biclique spanned subgraphs.