Limits...
A flood-based information flow analysis and network minimization method for gene regulatory networks.

Pavlogiannis A, Mozhayskiy V, Tagkopoulos I - BMC Bioinformatics (2013)

Bottom Line: Scalability and sensitivity analysis show that the proposed method scales well with the size of the network, and is robust to noise and missing data.The method of network flooding proves to be a useful, practical approach towards information flow analysis in gene regulatory networks.Further extension of the proposed theory has the potential to lead in a unifying framework for the simultaneous network minimization and information flow analysis across various "omics" levels.

View Article: PubMed Central - HTML - PubMed

Affiliation: Department of Computer Science, University of California Davis, One Shields Avenue, Davis, CA 95616, USA.

ABSTRACT

Background: Biological networks tend to have high interconnectivity, complex topologies and multiple types of interactions. This renders difficult the identification of sub-networks that are involved in condition- specific responses. In addition, we generally lack scalable methods that can reveal the information flow in gene regulatory and biochemical pathways. Doing so will help us to identify key participants and paths under specific environmental and cellular context.

Results: This paper introduces the theory of network flooding, which aims to address the problem of network minimization and regulatory information flow in gene regulatory networks. Given a regulatory biological network, a set of source (input) nodes and optionally a set of sink (output) nodes, our task is to find (a) the minimal sub-network that encodes the regulatory program involving all input and output nodes and (b) the information flow from the source to the sink nodes of the network. Here, we describe a novel, scalable, network traversal algorithm and we assess its potential to achieve significant network size reduction in both synthetic and E. coli networks. Scalability and sensitivity analysis show that the proposed method scales well with the size of the network, and is robust to noise and missing data.

Conclusions: The method of network flooding proves to be a useful, practical approach towards information flow analysis in gene regulatory networks. Further extension of the proposed theory has the potential to lead in a unifying framework for the simultaneous network minimization and information flow analysis across various "omics" levels.

Show MeSH

Related in: MedlinePlus

Pipeline for flooding minimization. (A) Transformation of the regulatory networks for flooding analysis as described in the text. (B) Flooding the network; for a given regulator node u with a positive total incoming flin the following scenarios are possible for the flood fl(u,v) through the edge (u,v): (i) and (ii) if edge capacity c(u,v) is positive and is greater or smaller than the value of the incoming flood, respectively; (iii) and (iv) if edge capacity c(u,v) is negative and its absolute value is greater or smaller than the value of the incoming flood, respectively; (v) if the total incoming flood floodin is negative, then the node is down-regulated and no flood is propagated regardless of the capacity of the edge. (C) Selection of nodes/links with flood above the threshold and the reverse transformation of the network.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

Figure 3: Pipeline for flooding minimization. (A) Transformation of the regulatory networks for flooding analysis as described in the text. (B) Flooding the network; for a given regulator node u with a positive total incoming flin the following scenarios are possible for the flood fl(u,v) through the edge (u,v): (i) and (ii) if edge capacity c(u,v) is positive and is greater or smaller than the value of the incoming flood, respectively; (iii) and (iv) if edge capacity c(u,v) is negative and its absolute value is greater or smaller than the value of the incoming flood, respectively; (v) if the total incoming flood floodin is negative, then the node is down-regulated and no flood is propagated regardless of the capacity of the edge. (C) Selection of nodes/links with flood above the threshold and the reverse transformation of the network.

Mentions: Here, we introduce a three-phase pipeline to address the network minimization problem defined above (FigureĀ 3). Given a GRN G, and a set of active environmental signals Sact, we first transform the input network G to a flood network that captures basic properties of gene networks such as a basal steady-state expression and a saturation limit on the expression of any given gene (phase one). Then, we calculate the floods on the transformed network (stage two). We then perform the actual minimization by imposing a flood threshold and then we inversely transform the resulting network to its GRN counterpart (stage three).


A flood-based information flow analysis and network minimization method for gene regulatory networks.

Pavlogiannis A, Mozhayskiy V, Tagkopoulos I - BMC Bioinformatics (2013)

Pipeline for flooding minimization. (A) Transformation of the regulatory networks for flooding analysis as described in the text. (B) Flooding the network; for a given regulator node u with a positive total incoming flin the following scenarios are possible for the flood fl(u,v) through the edge (u,v): (i) and (ii) if edge capacity c(u,v) is positive and is greater or smaller than the value of the incoming flood, respectively; (iii) and (iv) if edge capacity c(u,v) is negative and its absolute value is greater or smaller than the value of the incoming flood, respectively; (v) if the total incoming flood floodin is negative, then the node is down-regulated and no flood is propagated regardless of the capacity of the edge. (C) Selection of nodes/links with flood above the threshold and the reverse transformation of the network.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

Figure 3: Pipeline for flooding minimization. (A) Transformation of the regulatory networks for flooding analysis as described in the text. (B) Flooding the network; for a given regulator node u with a positive total incoming flin the following scenarios are possible for the flood fl(u,v) through the edge (u,v): (i) and (ii) if edge capacity c(u,v) is positive and is greater or smaller than the value of the incoming flood, respectively; (iii) and (iv) if edge capacity c(u,v) is negative and its absolute value is greater or smaller than the value of the incoming flood, respectively; (v) if the total incoming flood floodin is negative, then the node is down-regulated and no flood is propagated regardless of the capacity of the edge. (C) Selection of nodes/links with flood above the threshold and the reverse transformation of the network.
Mentions: Here, we introduce a three-phase pipeline to address the network minimization problem defined above (FigureĀ 3). Given a GRN G, and a set of active environmental signals Sact, we first transform the input network G to a flood network that captures basic properties of gene networks such as a basal steady-state expression and a saturation limit on the expression of any given gene (phase one). Then, we calculate the floods on the transformed network (stage two). We then perform the actual minimization by imposing a flood threshold and then we inversely transform the resulting network to its GRN counterpart (stage three).

Bottom Line: Scalability and sensitivity analysis show that the proposed method scales well with the size of the network, and is robust to noise and missing data.The method of network flooding proves to be a useful, practical approach towards information flow analysis in gene regulatory networks.Further extension of the proposed theory has the potential to lead in a unifying framework for the simultaneous network minimization and information flow analysis across various "omics" levels.

View Article: PubMed Central - HTML - PubMed

Affiliation: Department of Computer Science, University of California Davis, One Shields Avenue, Davis, CA 95616, USA.

ABSTRACT

Background: Biological networks tend to have high interconnectivity, complex topologies and multiple types of interactions. This renders difficult the identification of sub-networks that are involved in condition- specific responses. In addition, we generally lack scalable methods that can reveal the information flow in gene regulatory and biochemical pathways. Doing so will help us to identify key participants and paths under specific environmental and cellular context.

Results: This paper introduces the theory of network flooding, which aims to address the problem of network minimization and regulatory information flow in gene regulatory networks. Given a regulatory biological network, a set of source (input) nodes and optionally a set of sink (output) nodes, our task is to find (a) the minimal sub-network that encodes the regulatory program involving all input and output nodes and (b) the information flow from the source to the sink nodes of the network. Here, we describe a novel, scalable, network traversal algorithm and we assess its potential to achieve significant network size reduction in both synthetic and E. coli networks. Scalability and sensitivity analysis show that the proposed method scales well with the size of the network, and is robust to noise and missing data.

Conclusions: The method of network flooding proves to be a useful, practical approach towards information flow analysis in gene regulatory networks. Further extension of the proposed theory has the potential to lead in a unifying framework for the simultaneous network minimization and information flow analysis across various "omics" levels.

Show MeSH
Related in: MedlinePlus