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

Example of the flood network minimization. Original gene regulatory network (A) is transformed (B) to introduce saturation gadgets and potentially basal nodes (not shown). Minimized network is obtained after a flood threshold is applied to the flooded transformed network. Degree of minimization can be varied from aggressive (C) to mild (D) depending on the value of the threshold. Capacity of the edge is the upper limit for the magnitude of the flood through that edge, which depends on the upstream regulation. For example: edge 3→6 has a high capacity and a high positive flood, but the flood through edge 5→2 is low regardless its high capacity. Floods are calculated for the essential traversals from the input(s)/signal(s) to the output(s)/sink(s): 1→3→6, 1→4→6, 1→4→6→5→2→6, 1→3→6→5→2→6, 1→3→4→6, etc. The total flood through edge 2→6 is zero due to the strong negative flood 5→2 (inhibition of node 2). Therefore, nodes 2 and 5 are not part of the minimized network connecting inputs and outputs regardless of the imposed flood threshold. In contrast, node 4 may be included in the minimized network if a flood threshold is relatively low: flood 1→3 is replicated into two edges of high capacity 3→6 (positive flood, activation of node 6) and 3→4 (negative flood, inhibition of node 4). Large positive flood 1→4 in combination with a negative flood 3→4 produces a weak positive flood 4→6. Edge 4→6 is included in the minimized network only if the flood threshold is below 4→6 flood (D). If edge 4→6 is not in minimized network (C), edges 1→4 and 3→4, and node 4 are also not included, as they are disconnected from the output node(s).
© Copyright Policy - open-access
Related In: Results  -  Collection

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

Figure 2: Example of the flood network minimization. Original gene regulatory network (A) is transformed (B) to introduce saturation gadgets and potentially basal nodes (not shown). Minimized network is obtained after a flood threshold is applied to the flooded transformed network. Degree of minimization can be varied from aggressive (C) to mild (D) depending on the value of the threshold. Capacity of the edge is the upper limit for the magnitude of the flood through that edge, which depends on the upstream regulation. For example: edge 3→6 has a high capacity and a high positive flood, but the flood through edge 5→2 is low regardless its high capacity. Floods are calculated for the essential traversals from the input(s)/signal(s) to the output(s)/sink(s): 1→3→6, 1→4→6, 1→4→6→5→2→6, 1→3→6→5→2→6, 1→3→4→6, etc. The total flood through edge 2→6 is zero due to the strong negative flood 5→2 (inhibition of node 2). Therefore, nodes 2 and 5 are not part of the minimized network connecting inputs and outputs regardless of the imposed flood threshold. In contrast, node 4 may be included in the minimized network if a flood threshold is relatively low: flood 1→3 is replicated into two edges of high capacity 3→6 (positive flood, activation of node 6) and 3→4 (negative flood, inhibition of node 4). Large positive flood 1→4 in combination with a negative flood 3→4 produces a weak positive flood 4→6. Edge 4→6 is included in the minimized network only if the flood threshold is below 4→6 flood (D). If edge 4→6 is not in minimized network (C), edges 1→4 and 3→4, and node 4 are also not included, as they are disconnected from the output node(s).

Mentions: Given a GRN G and a set of active environmental signals Sact ⊆ S, infer the minimal GRN G’ = (V’, E’), such that G′ is the sub-graph of G that only contains all active nodes E′ and active edges E′, from the whole set of nodes and edges in G. In case that a set of sink nodes A ⊆ V is also supplied, E′ should contain only edges that are found on a path from any nodes s ∊ Sact to any nodes t ∈ A. Figure 2 depicts an example of gene regulatory network minimization problem.


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

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

Example of the flood network minimization. Original gene regulatory network (A) is transformed (B) to introduce saturation gadgets and potentially basal nodes (not shown). Minimized network is obtained after a flood threshold is applied to the flooded transformed network. Degree of minimization can be varied from aggressive (C) to mild (D) depending on the value of the threshold. Capacity of the edge is the upper limit for the magnitude of the flood through that edge, which depends on the upstream regulation. For example: edge 3→6 has a high capacity and a high positive flood, but the flood through edge 5→2 is low regardless its high capacity. Floods are calculated for the essential traversals from the input(s)/signal(s) to the output(s)/sink(s): 1→3→6, 1→4→6, 1→4→6→5→2→6, 1→3→6→5→2→6, 1→3→4→6, etc. The total flood through edge 2→6 is zero due to the strong negative flood 5→2 (inhibition of node 2). Therefore, nodes 2 and 5 are not part of the minimized network connecting inputs and outputs regardless of the imposed flood threshold. In contrast, node 4 may be included in the minimized network if a flood threshold is relatively low: flood 1→3 is replicated into two edges of high capacity 3→6 (positive flood, activation of node 6) and 3→4 (negative flood, inhibition of node 4). Large positive flood 1→4 in combination with a negative flood 3→4 produces a weak positive flood 4→6. Edge 4→6 is included in the minimized network only if the flood threshold is below 4→6 flood (D). If edge 4→6 is not in minimized network (C), edges 1→4 and 3→4, and node 4 are also not included, as they are disconnected from the output node(s).
© Copyright Policy - open-access
Related In: Results  -  Collection

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

Figure 2: Example of the flood network minimization. Original gene regulatory network (A) is transformed (B) to introduce saturation gadgets and potentially basal nodes (not shown). Minimized network is obtained after a flood threshold is applied to the flooded transformed network. Degree of minimization can be varied from aggressive (C) to mild (D) depending on the value of the threshold. Capacity of the edge is the upper limit for the magnitude of the flood through that edge, which depends on the upstream regulation. For example: edge 3→6 has a high capacity and a high positive flood, but the flood through edge 5→2 is low regardless its high capacity. Floods are calculated for the essential traversals from the input(s)/signal(s) to the output(s)/sink(s): 1→3→6, 1→4→6, 1→4→6→5→2→6, 1→3→6→5→2→6, 1→3→4→6, etc. The total flood through edge 2→6 is zero due to the strong negative flood 5→2 (inhibition of node 2). Therefore, nodes 2 and 5 are not part of the minimized network connecting inputs and outputs regardless of the imposed flood threshold. In contrast, node 4 may be included in the minimized network if a flood threshold is relatively low: flood 1→3 is replicated into two edges of high capacity 3→6 (positive flood, activation of node 6) and 3→4 (negative flood, inhibition of node 4). Large positive flood 1→4 in combination with a negative flood 3→4 produces a weak positive flood 4→6. Edge 4→6 is included in the minimized network only if the flood threshold is below 4→6 flood (D). If edge 4→6 is not in minimized network (C), edges 1→4 and 3→4, and node 4 are also not included, as they are disconnected from the output node(s).
Mentions: Given a GRN G and a set of active environmental signals Sact ⊆ S, infer the minimal GRN G’ = (V’, E’), such that G′ is the sub-graph of G that only contains all active nodes E′ and active edges E′, from the whole set of nodes and edges in G. In case that a set of sink nodes A ⊆ V is also supplied, E′ should contain only edges that are found on a path from any nodes s ∊ Sact to any nodes t ∈ A. Figure 2 depicts an example of gene regulatory network minimization problem.

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