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.


Running times of the best ILP formulations, of the two heuristics, and of LUO and SCAN for the PPI subnetworks.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

Fig5: Running times of the best ILP formulations, of the two heuristics, and of LUO and SCAN for the PPI subnetworks.

Mentions: Figure 5 shows the running times for the fastest ILP approaches, that is, the partition variable ILPs with cuts, and the heuristics for both problems. Also shown are the running times of SCAN, LUO, and the ILP for CE. For the majority of the instances, the ILP approaches for SCE and ME are much slower than all other methods including the ILP for CE. SCAN and the ME heuristic are the fastest methods, solving each instance in less than a minute and most instances within a second. The SCE heuristic is substantially slower than the ME heuristic; this behavior is consistent with the observations for the ILP approaches. Finally, LUO is comparable with the SCE heuristic: it is faster than the exact ILP approaches but substantially slower than SCAN and the ME heuristic.Figure 5


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

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

Running times of the best ILP formulations, of the two heuristics, and of LUO and SCAN for the PPI subnetworks.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

Fig5: Running times of the best ILP formulations, of the two heuristics, and of LUO and SCAN for the PPI subnetworks.
Mentions: Figure 5 shows the running times for the fastest ILP approaches, that is, the partition variable ILPs with cuts, and the heuristics for both problems. Also shown are the running times of SCAN, LUO, and the ILP for CE. For the majority of the instances, the ILP approaches for SCE and ME are much slower than all other methods including the ILP for CE. SCAN and the ME heuristic are the fastest methods, solving each instance in less than a minute and most instances within a second. The SCE heuristic is substantially slower than the ME heuristic; this behavior is consistent with the observations for the ILP approaches. Finally, LUO is comparable with the SCE heuristic: it is faster than the exact ILP approaches but substantially slower than SCAN and the ME heuristic.Figure 5

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.