Limits...
Concurrent conditional clustering of multiple networks: COCONETS.

Kleessen S, Klie S, Nikoloski Z - PLoS ONE (2014)

Bottom Line: We present theoretical results for special classes of networks to demonstrate the implications of conditionality captured by the COCONETS formulation.We demonstrate that the investigation of the differences between the clustering based on all networks with that obtained from a subset of networks can be used to quantify the specificity of biological responses.Therefore, the comparison of multiple networks based on concurrent conditional clustering offers a novel venue for detection and investigation of preserved network substructures.

View Article: PubMed Central - PubMed

Affiliation: Systems Biology and Mathematical Modeling Group, Max Planck Institute of Molecular Plant Physiology, Potsdam-Golm, Germany.

ABSTRACT
The accumulation of high-throughput data from different experiments has facilitated the extraction of condition-specific networks over the same set of biological entities. Comparing and contrasting of such multiple biological networks is in the center of differential network biology, aiming at determining general and condition-specific responses captured in the network structure (i.e., included associations between the network components). We provide a novel way for comparison of multiple networks based on determining network clustering (i.e., partition into communities) which is optimal across the set of networks with respect to a given cluster quality measure. To this end, we formulate the optimization-based problem of concurrent conditional clustering of multiple networks, termed COCONETS, based on the modularity. The solution to this problem is a clustering which depends on all considered networks and pinpoints their preserved substructures. We present theoretical results for special classes of networks to demonstrate the implications of conditionality captured by the COCONETS formulation. As the problem can be shown to be intractable, we extend an existing efficient greedy heuristic and applied it to determine concurrent conditional clusters on coexpression networks extracted from publically available time-resolved transcriptomics data of Escherichia coli under five stresses as well as on metabolite correlation networks from metabolomics data set from Arabidopsis thaliana exposed to eight environmental conditions. We demonstrate that the investigation of the differences between the clustering based on all networks with that obtained from a subset of networks can be used to quantify the specificity of biological responses. While a comparison of the Escherichia coli coexpression networks based on seminal properties does not pinpoint biologically relevant differences, the common network substructures extracted by COCONETS are supported by existing experimental evidence. Therefore, the comparison of multiple networks based on concurrent conditional clustering offers a novel venue for detection and investigation of preserved network substructures.

Show MeSH

Related in: MedlinePlus

Illustration of COCONETS.Given are three networks in the top row. The clusters in the optimal clustering for each network are marked in different colors (red and blue). The optimal concurrent conditional clustering of the two networks given in the middle row is of value 0 and is suboptimal for the network to the left. The optimal clusterings for any of the two networks shown in the bottom row are suboptimal concurrent conditional clustering; the shown clustering yields a value of −0.24, while the optimal clustering is of value 0, whereby all nodes form a single cluster (not shown).
© Copyright Policy
Related In: Results  -  Collection

License
getmorefigures.php?uid=PMC4126743&req=5

pone-0103637-g002: Illustration of COCONETS.Given are three networks in the top row. The clusters in the optimal clustering for each network are marked in different colors (red and blue). The optimal concurrent conditional clustering of the two networks given in the middle row is of value 0 and is suboptimal for the network to the left. The optimal clusterings for any of the two networks shown in the bottom row are suboptimal concurrent conditional clustering; the shown clustering yields a value of −0.24, while the optimal clustering is of value 0, whereby all nodes form a single cluster (not shown).

Mentions: For instance, consider the case of three networks: , a cycle on nodes, , a star on the same number of nodes with the node labeled 1 as its center, and , a cycle with permuted labels. It can readily be checked that the clustering of maximum modularity for contains two clusters: one containing two neighboring nodes, and the other the rest of the nodes, yielding a value of 0.08. The same argument holds for (accounting for the permutation). The optimal clustering for includes all nodes, yielding a value of 0 for the modularity. The clustering maximizing the sum of modularities for and coincides with the clustering for , yielding also a value of 0; this clustering is suboptimal for , but optimal in . The clustering maximizing the sum of modularities for and includes all nodes, resulting in a value of 0; moreover, it is suboptimal in both and , exhibiting value greater than 0 for the respective optimal clusterings (Figure 2).


Concurrent conditional clustering of multiple networks: COCONETS.

Kleessen S, Klie S, Nikoloski Z - PLoS ONE (2014)

Illustration of COCONETS.Given are three networks in the top row. The clusters in the optimal clustering for each network are marked in different colors (red and blue). The optimal concurrent conditional clustering of the two networks given in the middle row is of value 0 and is suboptimal for the network to the left. The optimal clusterings for any of the two networks shown in the bottom row are suboptimal concurrent conditional clustering; the shown clustering yields a value of −0.24, while the optimal clustering is of value 0, whereby all nodes form a single cluster (not shown).
© Copyright Policy
Related In: Results  -  Collection

License
Show All Figures
getmorefigures.php?uid=PMC4126743&req=5

pone-0103637-g002: Illustration of COCONETS.Given are three networks in the top row. The clusters in the optimal clustering for each network are marked in different colors (red and blue). The optimal concurrent conditional clustering of the two networks given in the middle row is of value 0 and is suboptimal for the network to the left. The optimal clusterings for any of the two networks shown in the bottom row are suboptimal concurrent conditional clustering; the shown clustering yields a value of −0.24, while the optimal clustering is of value 0, whereby all nodes form a single cluster (not shown).
Mentions: For instance, consider the case of three networks: , a cycle on nodes, , a star on the same number of nodes with the node labeled 1 as its center, and , a cycle with permuted labels. It can readily be checked that the clustering of maximum modularity for contains two clusters: one containing two neighboring nodes, and the other the rest of the nodes, yielding a value of 0.08. The same argument holds for (accounting for the permutation). The optimal clustering for includes all nodes, yielding a value of 0 for the modularity. The clustering maximizing the sum of modularities for and coincides with the clustering for , yielding also a value of 0; this clustering is suboptimal for , but optimal in . The clustering maximizing the sum of modularities for and includes all nodes, resulting in a value of 0; moreover, it is suboptimal in both and , exhibiting value greater than 0 for the respective optimal clusterings (Figure 2).

Bottom Line: We present theoretical results for special classes of networks to demonstrate the implications of conditionality captured by the COCONETS formulation.We demonstrate that the investigation of the differences between the clustering based on all networks with that obtained from a subset of networks can be used to quantify the specificity of biological responses.Therefore, the comparison of multiple networks based on concurrent conditional clustering offers a novel venue for detection and investigation of preserved network substructures.

View Article: PubMed Central - PubMed

Affiliation: Systems Biology and Mathematical Modeling Group, Max Planck Institute of Molecular Plant Physiology, Potsdam-Golm, Germany.

ABSTRACT
The accumulation of high-throughput data from different experiments has facilitated the extraction of condition-specific networks over the same set of biological entities. Comparing and contrasting of such multiple biological networks is in the center of differential network biology, aiming at determining general and condition-specific responses captured in the network structure (i.e., included associations between the network components). We provide a novel way for comparison of multiple networks based on determining network clustering (i.e., partition into communities) which is optimal across the set of networks with respect to a given cluster quality measure. To this end, we formulate the optimization-based problem of concurrent conditional clustering of multiple networks, termed COCONETS, based on the modularity. The solution to this problem is a clustering which depends on all considered networks and pinpoints their preserved substructures. We present theoretical results for special classes of networks to demonstrate the implications of conditionality captured by the COCONETS formulation. As the problem can be shown to be intractable, we extend an existing efficient greedy heuristic and applied it to determine concurrent conditional clusters on coexpression networks extracted from publically available time-resolved transcriptomics data of Escherichia coli under five stresses as well as on metabolite correlation networks from metabolomics data set from Arabidopsis thaliana exposed to eight environmental conditions. We demonstrate that the investigation of the differences between the clustering based on all networks with that obtained from a subset of networks can be used to quantify the specificity of biological responses. While a comparison of the Escherichia coli coexpression networks based on seminal properties does not pinpoint biologically relevant differences, the common network substructures extracted by COCONETS are supported by existing experimental evidence. Therefore, the comparison of multiple networks based on concurrent conditional clustering offers a novel venue for detection and investigation of preserved network substructures.

Show MeSH
Related in: MedlinePlus