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.


The forbidden induced subgraphs for split graphs (2K2, C4, and C5) and for split cluster graphs (C4, C5, P5, necktie, and bowtie).
© Copyright Policy - open-access
Related In: Results  -  Collection

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

Fig2: The forbidden induced subgraphs for split graphs (2K2, C4, and C5) and for split cluster graphs (C4, C5, P5, necktie, and bowtie).

Mentions: Each connected component of the solution has to be a split graph. These graphs can be characterized by forbidden induced subgraphs (see Figure 2).Figure 2


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

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

The forbidden induced subgraphs for split graphs (2K2, C4, and C5) and for split cluster graphs (C4, C5, P5, necktie, and bowtie).
© Copyright Policy - open-access
Related In: Results  -  Collection

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

Fig2: The forbidden induced subgraphs for split graphs (2K2, C4, and C5) and for split cluster graphs (C4, C5, P5, necktie, and bowtie).
Mentions: Each connected component of the solution has to be a split graph. These graphs can be characterized by forbidden induced subgraphs (see Figure 2).Figure 2

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.