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

Matrix visualisation of simple connection degree network partitioning. DAG matrix for genome-scale network of Arabidopsis thaliana after applying connection degree partitioning with different cutoffs. Subnetworks are displayed as non-overlapping blocks (coloured pixels on blue background) for connectivity threshold value (a) 20 (b) 10 (c) 5 and (d) 4. Large values leave a monolithic unresolved block, while small cutoffs produce extensive fragmentation.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

Figure 7: Matrix visualisation of simple connection degree network partitioning. DAG matrix for genome-scale network of Arabidopsis thaliana after applying connection degree partitioning with different cutoffs. Subnetworks are displayed as non-overlapping blocks (coloured pixels on blue background) for connectivity threshold value (a) 20 (b) 10 (c) 5 and (d) 4. Large values leave a monolithic unresolved block, while small cutoffs produce extensive fragmentation.

Mentions: For comparison, Figure 7 first shows the performance of the simple connection degree partitioning [13] for various threshold values. Visual representation of the DAG matrix is as in Figure 1, but elaborated here by the addition of a blue background that displays automatically recognised block limits.


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

Verwoerd WS - BMC Syst Biol (2011)

Matrix visualisation of simple connection degree network partitioning. DAG matrix for genome-scale network of Arabidopsis thaliana after applying connection degree partitioning with different cutoffs. Subnetworks are displayed as non-overlapping blocks (coloured pixels on blue background) for connectivity threshold value (a) 20 (b) 10 (c) 5 and (d) 4. Large values leave a monolithic unresolved block, while small cutoffs produce extensive fragmentation.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

Figure 7: Matrix visualisation of simple connection degree network partitioning. DAG matrix for genome-scale network of Arabidopsis thaliana after applying connection degree partitioning with different cutoffs. Subnetworks are displayed as non-overlapping blocks (coloured pixels on blue background) for connectivity threshold value (a) 20 (b) 10 (c) 5 and (d) 4. Large values leave a monolithic unresolved block, while small cutoffs produce extensive fragmentation.
Mentions: For comparison, Figure 7 first shows the performance of the simple connection degree partitioning [13] for various threshold values. Visual representation of the DAG matrix is as in Figure 1, but elaborated here by the addition of a blue background that displays automatically recognised block limits.

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