Limits...
A new computational method to split large biochemical networks into coherent subnets.

Verwoerd WS - BMC Syst Biol (2011)

Bottom Line: Compared to more general networks, biochemical networks have some special features: while generally sparse, there are a small number of highly connected metabolite nodes; and metabolite nodes can also be divided into two classes: internal nodes with associated mass balance constraints and external ones without.A quantitative quality measure called efficacy is constructed and shows that the new method gives improved partitioning for several metabolic networks, including bacterial, plant and mammal species.In addition, the user can interactively control which metabolite nodes are selected for cutting and when to stop further partitioning as the desired granularity has been reached.

View Article: PubMed Central - HTML - PubMed

Affiliation: Centre for Advanced Computational Solutions, Dept WF & Molecular Bioscience, Lincoln University, Ellesmere Junction Road, Christchurch, New Zealand. wynand.verwoerd@lincoln.ac.nz

ABSTRACT

Background: Compared to more general networks, biochemical networks have some special features: while generally sparse, there are a small number of highly connected metabolite nodes; and metabolite nodes can also be divided into two classes: internal nodes with associated mass balance constraints and external ones without. Based on these features, reclassifying selected internal nodes (separators) to external ones can be used to divide a large complex metabolic network into simpler subnetworks. Selection of separators based on node connectivity is commonly used but affords little detailed control and tends to produce excessive fragmentation.The method proposed here (Netsplitter) allows the user to control separator selection. It combines local connection degree partitioning with global connectivity derived from random walks on the network, to produce a more even distribution of subnetwork sizes. Partitioning is performed progressively and the interactive visual matrix presentation used allows the user considerable control over the process, while incorporating special strategies to maintain the network integrity and minimise the information loss due to partitioning.

Results: Partitioning of a genome scale network of 1348 metabolites and 1468 reactions for Arabidopsis thaliana encapsulates 66% of the network into 10 medium sized subnets. Applied to the flavonoid subnetwork extracted in this way, it is shown that Netsplitter separates this naturally into four subnets with recognisable functionality, namely synthesis of lignin precursors, flavonoids, coumarin and benzenoids. A quantitative quality measure called efficacy is constructed and shows that the new method gives improved partitioning for several metabolic networks, including bacterial, plant and mammal species.

Conclusions: For the examples studied the Netsplitter method is a considerable improvement on the performance of connection degree partitioning, giving a better balance of subnet sizes with the removal of fewer mass balance constraints. In addition, the user can interactively control which metabolite nodes are selected for cutting and when to stop further partitioning as the desired granularity has been reached. Finally, the blocking transformation at the heart of the procedure provides a powerful visual display of network structure that may be useful for its exploration independent of whether partitioning is required.

Show MeSH

Related in: MedlinePlus

DAG matrix for demo network. Non-zero columns of the DAG matrix (a) with only structural externals recognised (b) after reclassifying 4 high connectivity internals as external. Colour scaling expresses random walk probabilities between source nodes (rows) and sink nodes (columns) of the network; comparison of (a) and (b) shows how connectivity structure is revealed by an appropriate high connectivity cutoff.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

Figure 1: DAG matrix for demo network. Non-zero columns of the DAG matrix (a) with only structural externals recognised (b) after reclassifying 4 high connectivity internals as external. Colour scaling expresses random walk probabilities between source nodes (rows) and sink nodes (columns) of the network; comparison of (a) and (b) shows how connectivity structure is revealed by an appropriate high connectivity cutoff.

Mentions: Figure 1(a) shows the DAG matrix for this network using a colour scale to represent numerical values of the matrix elements. Of the original 137 metabolites, 66 have been identified as a structural external (i.e. it acts uniquely as either a substrate or a product in all reactions in which it participates) and eliminated. The remaining 71 internals are found to separate into 16 sinks and 55 source nodes.


A new computational method to split large biochemical networks into coherent subnets.

Verwoerd WS - BMC Syst Biol (2011)

DAG matrix for demo network. Non-zero columns of the DAG matrix (a) with only structural externals recognised (b) after reclassifying 4 high connectivity internals as external. Colour scaling expresses random walk probabilities between source nodes (rows) and sink nodes (columns) of the network; comparison of (a) and (b) shows how connectivity structure is revealed by an appropriate high connectivity cutoff.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

Figure 1: DAG matrix for demo network. Non-zero columns of the DAG matrix (a) with only structural externals recognised (b) after reclassifying 4 high connectivity internals as external. Colour scaling expresses random walk probabilities between source nodes (rows) and sink nodes (columns) of the network; comparison of (a) and (b) shows how connectivity structure is revealed by an appropriate high connectivity cutoff.
Mentions: Figure 1(a) shows the DAG matrix for this network using a colour scale to represent numerical values of the matrix elements. Of the original 137 metabolites, 66 have been identified as a structural external (i.e. it acts uniquely as either a substrate or a product in all reactions in which it participates) and eliminated. The remaining 71 internals are found to separate into 16 sinks and 55 source nodes.

Bottom Line: Compared to more general networks, biochemical networks have some special features: while generally sparse, there are a small number of highly connected metabolite nodes; and metabolite nodes can also be divided into two classes: internal nodes with associated mass balance constraints and external ones without.A quantitative quality measure called efficacy is constructed and shows that the new method gives improved partitioning for several metabolic networks, including bacterial, plant and mammal species.In addition, the user can interactively control which metabolite nodes are selected for cutting and when to stop further partitioning as the desired granularity has been reached.

View Article: PubMed Central - HTML - PubMed

Affiliation: Centre for Advanced Computational Solutions, Dept WF & Molecular Bioscience, Lincoln University, Ellesmere Junction Road, Christchurch, New Zealand. wynand.verwoerd@lincoln.ac.nz

ABSTRACT

Background: Compared to more general networks, biochemical networks have some special features: while generally sparse, there are a small number of highly connected metabolite nodes; and metabolite nodes can also be divided into two classes: internal nodes with associated mass balance constraints and external ones without. Based on these features, reclassifying selected internal nodes (separators) to external ones can be used to divide a large complex metabolic network into simpler subnetworks. Selection of separators based on node connectivity is commonly used but affords little detailed control and tends to produce excessive fragmentation.The method proposed here (Netsplitter) allows the user to control separator selection. It combines local connection degree partitioning with global connectivity derived from random walks on the network, to produce a more even distribution of subnetwork sizes. Partitioning is performed progressively and the interactive visual matrix presentation used allows the user considerable control over the process, while incorporating special strategies to maintain the network integrity and minimise the information loss due to partitioning.

Results: Partitioning of a genome scale network of 1348 metabolites and 1468 reactions for Arabidopsis thaliana encapsulates 66% of the network into 10 medium sized subnets. Applied to the flavonoid subnetwork extracted in this way, it is shown that Netsplitter separates this naturally into four subnets with recognisable functionality, namely synthesis of lignin precursors, flavonoids, coumarin and benzenoids. A quantitative quality measure called efficacy is constructed and shows that the new method gives improved partitioning for several metabolic networks, including bacterial, plant and mammal species.

Conclusions: For the examples studied the Netsplitter method is a considerable improvement on the performance of connection degree partitioning, giving a better balance of subnet sizes with the removal of fewer mass balance constraints. In addition, the user can interactively control which metabolite nodes are selected for cutting and when to stop further partitioning as the desired granularity has been reached. Finally, the blocking transformation at the heart of the procedure provides a powerful visual display of network structure that may be useful for its exploration independent of whether partitioning is required.

Show MeSH
Related in: MedlinePlus