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 network comparison based on community structure.Shown are three networks, , , and . Nodes belonging to the same community in each network are marked by the same color. Networks  and  differ in 11 edges, while networks  and  do not share 4 edges. Nevertheless, the community structures between  and  are equivalent, while this is not the case for the community structures in  and .
© Copyright Policy
Related In: Results  -  Collection

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

pone-0103637-g001: Illustration of network comparison based on community structure.Shown are three networks, , , and . Nodes belonging to the same community in each network are marked by the same color. Networks and differ in 11 edges, while networks and do not share 4 edges. Nevertheless, the community structures between and are equivalent, while this is not the case for the community structures in and .

Mentions: Here we focus on comparison of multiple networks over the same set of components, and explore a conceptually different way for multiple network comparison based on differences between their clusteredness, i.e., their network community structure. The idea is based on the observation that classical network operations, e.g., intersection and difference, stress the absolute (dis)agreement between the edge-sets in two compared networks, although the community structure of the two networks may not be drastically altered with removal and/or addition of subset of edges. A motivating example includes three networks, , , and : although and share fewer edges in comparison to and , the given community structures of and are closer than the community structures of and (Figure 1).


Concurrent conditional clustering of multiple networks: COCONETS.

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

Illustration of network comparison based on community structure.Shown are three networks, , , and . Nodes belonging to the same community in each network are marked by the same color. Networks  and  differ in 11 edges, while networks  and  do not share 4 edges. Nevertheless, the community structures between  and  are equivalent, while this is not the case for the community structures in  and .
© Copyright Policy
Related In: Results  -  Collection

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

pone-0103637-g001: Illustration of network comparison based on community structure.Shown are three networks, , , and . Nodes belonging to the same community in each network are marked by the same color. Networks and differ in 11 edges, while networks and do not share 4 edges. Nevertheless, the community structures between and are equivalent, while this is not the case for the community structures in and .
Mentions: Here we focus on comparison of multiple networks over the same set of components, and explore a conceptually different way for multiple network comparison based on differences between their clusteredness, i.e., their network community structure. The idea is based on the observation that classical network operations, e.g., intersection and difference, stress the absolute (dis)agreement between the edge-sets in two compared networks, although the community structure of the two networks may not be drastically altered with removal and/or addition of subset of edges. A motivating example includes three networks, , , and : although and share fewer edges in comparison to and , the given community structures of and are closer than the community structures of and (Figure 1).

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