Limits...
A graph modification approach for finding core-periphery structures in protein interaction networks.

Bruckner S, Hüffner F, Komusiewicz C - Algorithms Mol Biol (2015)

Bottom Line: In one model each cluster has its own periphery, and in the other the periphery is shared.We first analyze both models from a theoretical point of view, showing their NP-hardness.Then, we devise efficient exact and heuristic algorithms for both models and finally perform an evaluation on subnetworks of the S. cerevisiae PPI network.

View Article: PubMed Central - PubMed

Affiliation: International Max Planck Research School for Computational Biology and Scientific Computing, Ihnestr. 63-73, Berlin, 14195 Germany.

ABSTRACT
The core-periphery model for protein interaction (PPI) networks assumes that protein complexes in these networks consist of a dense core and a possibly sparse periphery that is adjacent to vertices in the core of the complex. In this work, we aim at uncovering a global core-periphery structure for a given PPI network. We propose two exact graph-theoretic formulations for this task, which aim to fit the input network to a hypothetical ground truth network by a minimum number of edge modifications. In one model each cluster has its own periphery, and in the other the periphery is shared. We first analyze both models from a theoretical point of view, showing their NP-hardness. Then, we devise efficient exact and heuristic algorithms for both models and finally perform an evaluation on subnetworks of the S. cerevisiae PPI network.

No MeSH data available.


An example input and optimal solutions to CLUSTER EDITING, SPLIT CLUSTER EDITING, and MONOPOLAR EDITING. Dashed edges are edge deletions, bold edges are edge insertions. CLUSTER EDITING and SPLIT CLUSTER EDITING produce the same two clusters but SPLIT CLUSTER EDITING assigns the blue vertex of the size-four cluster to the periphery. In an optimal solution to MONOPOLAR EDITING the two blue vertices are in the periphery which is shared between two clusters. Note that the number of necessary edge modifications decreases from CLUSTER EDITING to SPLIT CLUSTER EDITING to MONOPOLAR EDITING.
© Copyright Policy - open-access
Related In: Results  -  Collection

License 1 - License 2
getmorefigures.php?uid=PMC4440566&req=5

Fig1: An example input and optimal solutions to CLUSTER EDITING, SPLIT CLUSTER EDITING, and MONOPOLAR EDITING. Dashed edges are edge deletions, bold edges are edge insertions. CLUSTER EDITING and SPLIT CLUSTER EDITING produce the same two clusters but SPLIT CLUSTER EDITING assigns the blue vertex of the size-four cluster to the periphery. In an optimal solution to MONOPOLAR EDITING the two blue vertices are in the periphery which is shared between two clusters. Note that the number of necessary edge modifications decreases from CLUSTER EDITING to SPLIT CLUSTER EDITING to MONOPOLAR EDITING.

Mentions: Figure 1 shows an example graph along with optimal solutions for SPLIT CLUSTER EDITING and MONOPOLAR EDITING and, for comparison, CLUSTER EDITING. Clearly, the models behind SPLIT CLUSTER EDITING and MONOPOLAR EDITING are simplistic and cannot completely reflect biological reality. For example, subunits of protein complexes consisting of two proteins that first interact with each other and subsequently with the core of a protein complex are supported by neither of our models. Nevertheless, our models are less simplistic than pure clustering models that attempt to divide protein interaction networks into disjoint dense clusters. Furthermore, there is a clear trade-off between model complexity, algorithmic feasibility of models, and interpretability.Figure 1


A graph modification approach for finding core-periphery structures in protein interaction networks.

Bruckner S, Hüffner F, Komusiewicz C - Algorithms Mol Biol (2015)

An example input and optimal solutions to CLUSTER EDITING, SPLIT CLUSTER EDITING, and MONOPOLAR EDITING. Dashed edges are edge deletions, bold edges are edge insertions. CLUSTER EDITING and SPLIT CLUSTER EDITING produce the same two clusters but SPLIT CLUSTER EDITING assigns the blue vertex of the size-four cluster to the periphery. In an optimal solution to MONOPOLAR EDITING the two blue vertices are in the periphery which is shared between two clusters. Note that the number of necessary edge modifications decreases from CLUSTER EDITING to SPLIT CLUSTER EDITING to MONOPOLAR EDITING.
© Copyright Policy - open-access
Related In: Results  -  Collection

License 1 - License 2
Show All Figures
getmorefigures.php?uid=PMC4440566&req=5

Fig1: An example input and optimal solutions to CLUSTER EDITING, SPLIT CLUSTER EDITING, and MONOPOLAR EDITING. Dashed edges are edge deletions, bold edges are edge insertions. CLUSTER EDITING and SPLIT CLUSTER EDITING produce the same two clusters but SPLIT CLUSTER EDITING assigns the blue vertex of the size-four cluster to the periphery. In an optimal solution to MONOPOLAR EDITING the two blue vertices are in the periphery which is shared between two clusters. Note that the number of necessary edge modifications decreases from CLUSTER EDITING to SPLIT CLUSTER EDITING to MONOPOLAR EDITING.
Mentions: Figure 1 shows an example graph along with optimal solutions for SPLIT CLUSTER EDITING and MONOPOLAR EDITING and, for comparison, CLUSTER EDITING. Clearly, the models behind SPLIT CLUSTER EDITING and MONOPOLAR EDITING are simplistic and cannot completely reflect biological reality. For example, subunits of protein complexes consisting of two proteins that first interact with each other and subsequently with the core of a protein complex are supported by neither of our models. Nevertheless, our models are less simplistic than pure clustering models that attempt to divide protein interaction networks into disjoint dense clusters. Furthermore, there is a clear trade-off between model complexity, algorithmic feasibility of models, and interpretability.Figure 1

Bottom Line: In one model each cluster has its own periphery, and in the other the periphery is shared.We first analyze both models from a theoretical point of view, showing their NP-hardness.Then, we devise efficient exact and heuristic algorithms for both models and finally perform an evaluation on subnetworks of the S. cerevisiae PPI network.

View Article: PubMed Central - PubMed

Affiliation: International Max Planck Research School for Computational Biology and Scientific Computing, Ihnestr. 63-73, Berlin, 14195 Germany.

ABSTRACT
The core-periphery model for protein interaction (PPI) networks assumes that protein complexes in these networks consist of a dense core and a possibly sparse periphery that is adjacent to vertices in the core of the complex. In this work, we aim at uncovering a global core-periphery structure for a given PPI network. We propose two exact graph-theoretic formulations for this task, which aim to fit the input network to a hypothetical ground truth network by a minimum number of edge modifications. In one model each cluster has its own periphery, and in the other the periphery is shared. We first analyze both models from a theoretical point of view, showing their NP-hardness. Then, we devise efficient exact and heuristic algorithms for both models and finally perform an evaluation on subnetworks of the S. cerevisiae PPI network.

No MeSH data available.