Efficient and robust prediction algorithms for protein complexes using Gomory-Hu trees.

Area of Science:

• Bioinformatics
• Systems Biology
• Computational Biology

Background:

• Protein-protein interaction (PPI) data, particularly from Two-Hybrid (Y2H) methods, are prone to high rates of false positives and false negatives.
• This data noise presents a significant challenge for accurately identifying protein complexes within PPI networks.

Purpose of the Study:

• To develop an efficient and robust computational approach for identifying protein complexes from noisy Y2H PPI data.
• To overcome the limitations of traditional edge-based connectivity measures in PPI network analysis.

Main Methods:

• The study proposes a novel method that measures protein connectivity using edge-disjoint paths instead of direct edges.
• This connectivity is modeled as a network flow problem and represented efficiently using a Gomory-Hu tree.
• The Gomory-Hu tree is manipulated to isolate groups of proteins with high internal connectivity, representing putative protein complexes.

Main Results:

• The algorithm's performance was evaluated using Variation of Information and Separation measures, demonstrating robustness against increased false positive and false negative rates.
• The approach was successfully applied to Y2H PPI networks from yeast, mouse, worm, and human.
• In the yeast network, 38 statistically significant protein clusters were identified, with 20 corresponding to known protein complexes and 16 to functional modules.

Conclusions:

• The proposed edge-disjoint path method offers an effective strategy for robust protein complex detection in noisy PPI networks.
• This approach significantly improves the accuracy of identifying protein complexes and functional modules compared to traditional methods.
• The technique shows broad applicability across different species' PPI networks, highlighting its potential in systems biology research.