Enumeration of condition-dependent dense modules in protein interaction networks

Area of Science:

• Systems biology
• Computational biology
• Bioinformatics

Background:

• Cellular functions rely on protein complexes, whose composition varies with cellular conditions.
• Discovering these functional complexes from protein interaction data is a significant computational challenge.
• Existing methods often approximate dense module extraction, limiting accuracy.

Purpose of the Study:

• To develop an exact algorithm for enumerating dense protein modules (complexes).
• To integrate multi-omics data (gene expression, phenotype, phylogenetic profiles) for condition-specific complex discovery.
• To provide a computationally feasible method for identifying biologically meaningful protein complexes.

Main Methods:

• Developed an exact algorithm for dense module enumeration based on a user-defined density threshold.
• Employed a reverse search strategy for efficient exploitation of the density criterion.
• Integrated gene expression, phenotype, and phylogenetic data with protein interaction networks.

Main Results:

• The method exactly enumerates all protein sets meeting the density threshold.
• Experiments demonstrate feasibility and biological relevance, outperforming existing methods in yeast complex prediction.
• Identified condition-dependent protein complex variants in yeast and human networks by integrating multi-omics data.

Conclusions:

• The novel algorithm precisely identifies protein complexes and their condition-specific variations.
• This approach advances systems biology by enabling systematic mining of functional modules.
• The method offers a powerful tool for understanding dynamic cellular processes and protein interactions.