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

Effect of network incompleteness on the performance of network minimization in the XOR environment. (A) The average size of links is reduced linearly but with decreased slope, (B) the minimized and initial network (after random link removal) have the same fitness, (C) the sensitivity of the method (how many of the true positive links are present in the minimal network is on par or better to that of the heuristic search. Analysis performed in sets of 100 cells over 10 randomizations. Similar statistics were gathered in the case of the AND environment (Additional file 1).
© Copyright Policy - open-access
Related In: Results  -  Collection

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

Figure 5: Effect of network incompleteness on the performance of network minimization in the XOR environment. (A) The average size of links is reduced linearly but with decreased slope, (B) the minimized and initial network (after random link removal) have the same fitness, (C) the sensitivity of the method (how many of the true positive links are present in the minimal network is on par or better to that of the heuristic search. Analysis performed in sets of 100 cells over 10 randomizations. Similar statistics were gathered in the case of the AND environment (Additional file 1).

Mentions: We evaluated the scalability of our algorithm in respect to node size, and it was found to scale well below the exponential theoretical upper bound (Additional file 2: Figure S2). To assess the performance of our method when data are missing, we randomly removed sets of links from the network before minimization (FigureĀ 5 and Additional file 2: Figure S3). This analysis is necessary as even for E. coli, the amount of missing information is high as it currently has a reconstructed network of about 1700 genes (38% of the genome) and many missing associations. Our method was found to be robust even in cases where half of the biological network is unknown. Similarly, perturbation of 10% of the weight value did not affect the network minimization result (<1% fitness change).


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

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

Effect of network incompleteness on the performance of network minimization in the XOR environment. (A) The average size of links is reduced linearly but with decreased slope, (B) the minimized and initial network (after random link removal) have the same fitness, (C) the sensitivity of the method (how many of the true positive links are present in the minimal network is on par or better to that of the heuristic search. Analysis performed in sets of 100 cells over 10 randomizations. Similar statistics were gathered in the case of the AND environment (Additional file 1).
© Copyright Policy - open-access
Related In: Results  -  Collection

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

Figure 5: Effect of network incompleteness on the performance of network minimization in the XOR environment. (A) The average size of links is reduced linearly but with decreased slope, (B) the minimized and initial network (after random link removal) have the same fitness, (C) the sensitivity of the method (how many of the true positive links are present in the minimal network is on par or better to that of the heuristic search. Analysis performed in sets of 100 cells over 10 randomizations. Similar statistics were gathered in the case of the AND environment (Additional file 1).
Mentions: We evaluated the scalability of our algorithm in respect to node size, and it was found to scale well below the exponential theoretical upper bound (Additional file 2: Figure S2). To assess the performance of our method when data are missing, we randomly removed sets of links from the network before minimization (FigureĀ 5 and Additional file 2: Figure S3). This analysis is necessary as even for E. coli, the amount of missing information is high as it currently has a reconstructed network of about 1700 genes (38% of the genome) and many missing associations. Our method was found to be robust even in cases where half of the biological network is unknown. Similarly, perturbation of 10% of the weight value did not affect the network minimization result (<1% fitness change).

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