Reconstruction of large-scale regulatory networks based on perturbation graphs and transitive reduction: improved methods and their evaluation

BMC Systems Biology

Steffen Klamt¹  Alberto de la Fuente²  Robert J Flassig¹  Sandra Heise¹  Andrea Pinna³ 

[1] Max Planck Institute for Dynamics of Complex Technical Systems, Magdeburg, Germany;Leibniz Institute for Farm Animal Biology, Dummerstorf, Germany;Center for Advanced Studies, Research and Development (CRS4) Bioinformatica, Pula, Italy

关键词: Yeast;    Saccharomyces cerevisiae;    Transcriptional regulation;    Transitive reduction;    Interaction graphs;    Graph theory;    Causal networks;    Perturbation experiments;    Reverse engineering;    Gene network inference;   

Others  :  1142466
DOI  :  10.1186/1752-0509-7-73

 received in 2013-03-15, accepted in 2013-08-05,  发布年份 2013

【 摘 要 】

Background

The data-driven inference of intracellular networks is one of the key challenges of computational and systems biology. As suggested by recent works, a simple yet effective approach for reconstructing regulatory networks comprises the following two steps. First, the observed effects induced by directed perturbations are collected in a signed and directed perturbation graph (PG). In a second step, Transitive Reduction (TR) is used to identify and eliminate those edges in the PG that can be explained by paths and are therefore likely to reflect indirect effects.

Results

In this work we introduce novel variants for PG generation and TR, leading to significantly improved performances. The key modifications concern: (i) use of novel statistical criteria for deriving a high-quality PG from experimental data; (ii) the application of local TR which allows only short paths to explain (and remove) a given edge; and (iii) a novel strategy to rank the edges with respect to their confidence. To compare the new methods with existing ones we not only apply them to a recent DREAM network inference challenge but also to a novel and unprecedented synthetic compendium consisting of 30 5000-gene networks simulated with varying biological and measurement error variances resulting in a total of 270 datasets. The benchmarks clearly demonstrate the superior reconstruction performance of the novel PG and TR variants compared to existing approaches. Moreover, the benchmark enabled us to draw some general conclusions. For example, it turns out that local TR restricted to paths with a length of only two is often sufficient or even favorable. We also demonstrate that considering edge weights is highly beneficial for TR whereas consideration of edge signs is of minor importance. We explain these observations from a graph-theoretical perspective and discuss the consequences with respect to a greatly reduced computational demand to conduct TR. Finally, as a realistic application scenario, we use our framework for inferring gene interactions in yeast based on a library of gene expression data measured in mutants with single knockouts of transcription factors. The reconstructed network shows a significant enrichment of known interactions, especially within the 100 most confident (and for experimental validation most relevant) edges.

Conclusions

This paper presents several major achievements. The novel methods introduced herein can be seen as state of the art for inference techniques relying on perturbation graphs and transitive reduction. Another key result of the study is the generation of a new and unprecedented large-scale in silico benchmark dataset accounting for different noise levels and providing a solid basis for unbiased testing of network inference methodologies. Finally, applying our approach to Saccharomyces cerevisiae suggested several new gene interactions with high confidence awaiting experimental validation.

【 授权许可】

   
2013 Pinna et al.; licensee BioMed Central Ltd.

【 图 表 】

Figure 1.

Figure 2.

Figure 3.

Figure 4.

Figure 5.

Figure 6.

Figure 7.

【 参考文献 】

• [1]Markowetz F, Spang R: Inferring cellular networks–a review. BMC Bioinformatics 2007, 8(Suppl 6):S5. BioMed Central Full Text
• [2]Gardner T, Faith J: Reverse-engineering transcription control networks. Phys Life Rev 2005, 2:65-88.
• [3]Bansal M, Belcastro V, Ambesi-Impiombato A, di Bernardo D: How to infer gene networks from expression profiles. Mol Syst Biol 2007, 3:78.
• [4]Schlitt T, Brazma A: Current approaches to gene regulatory network modelling. BMC Bioinformatics 2007, 8(Suppl 6):S9. BioMed Central Full Text
• [5]De Smet R, Marchal K: Advantages and limitations of current network inference methods. Nat Rev Microbiol 2010, 8(10):717-729.
• [6]Marbach D, Costello JC, Kuffner R, Vega NM, Prill RJ, Camacho DM, Allison KR, Kellis M, Collins JJ, Stolovitzky G, et al.: Wisdom of crowds for robust gene network inference. Nat Methods 2012, 9(8):796-804.
• [7]Tibshirani R: Regression shrinkage and selection via the lasso. J R Stat Soc, Ser B 1994, 58:267-288.
• [8]de la Fuente A, Bing N, Hoeschele I, Mendes P: Discovery of meaningful associations in genomic data using partial correlation coefficients. Bioinformatics 2004, 20:3565-3574.
• [9]Prill R, Marbach D, Saez-Rodriguez J, Sorger P, Alexopoulos L, Xue X, Clarke N, Altan-Bonnet G, Stolovitzky G: Towards a rigorous assessment of systems biology models: the DREAM3 challenges. PLoS ONE 2010, 5:e9202.
• [10]Watkinson J, Lian K, Wang X, Zheng T, Anastassiou D: Inference of regulatory gene interactions from expression data using three-way mutual information. Ann New York Acad Sci 2009, 1158:302-313.
• [11]Margolin AA, Nemenman I, Basso K, Wiggins C, Stolovitzky G, Favera RD, Califano A: ARACNE: an algorithm for the reconstruction of gene regulatory networks in a mammalian cellular context. BMC Bioinformatics 2006, 7(Suppl 1):S7. BioMed Central Full Text
• [12]Kueffner R, Petri T, Tavakkolkhah P, Windhager L, Zimmer R: Inferring Gene Regulatory Networks by ANOVA. Bioinformatics 2012, 28:1376-1382.
• [13]Friedman N, Linial M, Nachman I, Pe’er D: Using Bayesian networks to analyze expression data. J Comput Biol 2000, 7:601-620.
• [14]Chiquet J, Grandvalet Y, Ambroise C: Inferring multiple graphical structures. Stat Comput 2011, 21(4):537-553.
• [15]Huynh-Thu V, Irrthum A, Wehenkel L, Geurts P: Inferring regulatory networks from expression data using tree-based methods. PLoS ONE 2010, 5(9):e12776.
• [16]Nelander S, Wang W, Nilsson B, She QB, Pratilas C, Rosen N, Gennemark P, Sander C: Models from experiments: combinatorial drug perturbations of cancer cells. Mol Syst Biol 2008, 4:216.
• [17]Durzinsky M, Wagler A, Weismantel R, Marwan W: Automatic reconstruction of molecular and genetic networks from discrete time series data. BioSystems 2008, 93(3):181-90.
• [18]Akutsu T, Kuhara S, Maruyama O, Miyano S: Identification of genetic networks by strategic gene disruptions and gene overexpressions under a boolean model. Theor Comput Sci 2003, 298:235-251.
• [19]Rodriguez JS, Alexopoulos L, Epperlein J, Samaga R, Lauffenburger D, Klamt S, Sorger P: Discrete logic modelling as a means to link protein signalling networks with functional analysis of mammalian signal transduction. Mol Syst Biol 2009, 5:331.
• [20]The DREAM Project http://www.the-dream-project.org webcite
• [21]Marbach D, Prill RJ, Schaffter T, Mattiussi C, Floreano D, Stolovitzky G: Revealing strengths and weaknesses of methods for gene network inference. Proc Natl Acad Sci 2010, 107(14):6286-6291.
• [22]Meyer P, Alexopoulos L, Bonk T, Califano A, Cho C, de la Fuente A, de Graaf D, Hartemink A, Hoeng J, Ivanov N, Koeppl H, Linding R, Marbach D, Norel R, Peitsch M, Rice J, Royyuru A, Schacherer F, Sprengel J, Stolle K, Vitkup D, Stolovitzky G: Verification of systems biology research in the age of collaborative competition. Nat Biotechnol 2011, 29:811-815.
• [23]Stumpf MP, Thorne T, de Silva E, Stewart R, An HJ, Lappe M, Wiuf C: Estimating the size of the human interactome. Proc Natl Acad Sci 2008, 105(19):6959-6964.
• [24]de la Fuente A, Brazhnik P, Mendes P: Linking the genes: inferring quantitative gene networks from microarray data. Trends Genet 2002, 18(8):395-398.
• [25]Kholodenko BN, Kiyatkin A, Bruggeman FJ, Sontag E, Westerhoff HV, Hoek JB: Untangling the wires: a strategy to trace functional interactions in signaling and gene networks. Proc Natl Acad Sci 1284, 99(20):1-12846.
• [26]van Someren EP, Wessels LF, Reinders MJ: Linear modeling of genetic networks from experimental data. Proc Int Conf Intell Syst Mol Biol 2000, 8:355-366.
• [27]Smith VA, Jarvis ED, Hartemink AJ: Evaluating functional network inference using simulations of complex biological systems. Bioinformatics 2002, 18(Suppl 1):S216-S224.
• [28]Mendes P, Sha W, Ye K: Artificial gene networks for objective comparison of analysis algorithms. Bioinformatics 2003, 19(Suppl 2):ii122-ii129.
• [29]Soranzo N, Bianconi G, Altafini C: Comparing association network algorithms for reverse engineering of large-scale gene regulatory networks: synthetic versus real data. Bioinformatics 2007, 23(13):1640-1647.
• [30]Pinna A, Soranzo N, de la Fuente A: From knockouts to networks: establishing direct cause-effect relationships through graph analysis. PLoS ONE 2010, 5(10):e12912.
• [31]Klamt S, Flassig RJ, Sundmacher K: TRANSWESD: inferring cellular networks with transitive reduction. Bioinformatics 2010, 26(17):2160-2168.
• [32]Winzeler EA, Shoemaker DD, Astromoff A, Liang H, Anderson K, Andre B, Bangham R, Benito R, Boeke JD, Bussey H, Chu AM, Connelly C, Davis K, Dietrich F, Dow SW, El Bakkoury M, Foury F, Friend SH, Gentalen E, Giaever G, Hegemann JH, Jones T, Laub M, Liao H, Liebundguth N, Lockhart DJ, Lucau-Danila A, Lussier M, M’Rabet N, Menard P, Mittmann M, Pai C, Rebischung C, Revuelta JL, Riles L, Roberts CJ, Ross-MacDonald P, Scherens B, Snyder M, Sookhai-Mahadeo S, Storms RK, Veronneau S, Voet M, Volckaert G, Ward TR, Wysocki R, Yen GS, Yu K, Zimmermann K, Philippsen P, Johnston M, Davis RW: Functional characterization of the S. cerevisiae genome by gene deletion and parallel analysis. Science 1999, 285(5429):901-906.
• [33]Dolgin E: Mouse library set to be knockout. Nature 2011, 474(7351):262-263.
• [34]Hu Z, Killion PJ, Iyer VR: Genetic reconstruction of a functional transcriptional regulatory network. Nat Genet 2007, 39(5):683-687.
• [35]Reimand J, Vaquerizas JM, Todd AE, Vilo J, Luscombe NM: Comprehensive reanalysis of transcription factor knockout expression data in Saccharomyces cerevisiae reveals many new targets. Nucleic Acid Res 2010, 38(14):4768-4777.
• [36]Bošnački D, Odenbrett MR, Wijs A, Ligtenberg W, Hilbers P: Efficient reconstruction of biological networks via transitive reduction on general purpose graphics processors. BMC Bioinformatics 2012, 13:281. BioMed Central Full Text
• [37]Tresch A, Beissbarth T, Sültmann H, Kuner R, Poustka A, Buness A: Discrimination of direct and indirect interactions in a network of regulatory effects. J Comput Biol 2007, 14(9):1217-1228.
• [38]Wagner A: How to reconstruct a large genetic network from n gene perturbations in fewer than n2 easy steps. Bioinformatics 2001, 17(12):1183-1197.
• [39]Kachalo S, Zhang R, Sontag E, Albert R, DasGupta B: NET-SYNTHESIS: a software for synthesis, inference and simplification of signal transduction networks. Bioinformatics 2008, 24(2):293-295.
• [40]Klamt S, Kamp AV: Computing paths and cycles in biological interaction graphs. BMC Bioinformatics 2009, 10:181. BioMed Central Full Text
• [41]Pinna A, Soranzo N, Hoeschele I, de la Fuente A: Simulating systems genetics data with SysGenSIM. Bioinformatics 2011, 27(17):2459-2462.
• [42]DREAM4 In Silico Network Challenge http://wiki.c2b2.columbia.edu/dream/index.php/D4c2 webcite
• [43]Evaluation script for the DREAM4 In Silico Network Challenge http://wiki.c2b2.columbia.edu/dream/results/DREAM4 webcite
• [44]Schaffter T, Marbach D, Floreano D: GeneNetWeaver: in silico benchmark generation and performance profiling of network inference methods. Bioinformatics 2011, 27(16):2263-2270.
• [45]Wang Y, Zhou T: A relative variation-based method to unraveling gene regulatory networks. PLoS ONE 2012, 7(2):e31194.
• [46]Guelzim N, Bottani S, Bourgine P, Kepes F: Topological and causal structure of the yeast transcriptional regulatory network. Nat Genet 2002, 31:60-63.
• [47]Gentleman RC, Carey VJ, Bates DM, Bolstad B, Dettling M, Dudoit S, Ellis B, Gautier L, Ge Y, Gentry J, et al.: Bioconductor: open software development for computational biology and bioinformatics. Genome Biol 2004, 5(10):R80. BioMed Central Full Text
• [48]Kaplan N, Moore IK, Fondufe-Mittendorf Y, Gossett AJ, Tillo D, Field Y, LeProust EM, Hughes TR, Lieb JD, Widom J, et al.: The DNA-encoded nucleosome organization of a eukaryotic genome. Nature 2008, 458(7236):362-366.
• [49]Luscombe NM, Babu MM, Yu H, Snyder M, Teichmann SA, Gerstein M: Genomic analysis of regulatory network dynamics reveals large topological changes. Nature 2004, 431(7006):308-312.
• [50]Flassig RJ, Heise S, Sundmacher K, Klamt S: An effective framework for reconstructing gene regulatory networks from genetical genomics data. Bioinformatics 2013, 29(2):246-254.