An integer optimization algorithm for robust identification of non-linear gene regulatory networks

BMC Systems Biology

Ipsita Banerjee¹  Keith Task¹  Nishanth Chemmangattuvalappil¹ 

[1] Department of Chemical Engineering, University of Pittsburgh, 1249 Benedum Hall, 3700 O’Hara Street, Pittsburgh, PA, 15261, USA

关键词: Optimization algorithm;    Integer programming;    Bootstrapping;    Robust network identification;    S-system;    Non-linear dynamics;    Gene regulatory networks;   

Others  :  1143605
DOI  :  10.1186/1752-0509-6-119

 received in 2012-03-08, accepted in 2012-08-27,  发布年份 2012

【 摘 要 】

Background

Reverse engineering gene networks and identifying regulatory interactions are integral to understanding cellular decision making processes. Advancement in high throughput experimental techniques has initiated innovative data driven analysis of gene regulatory networks. However, inherent noise associated with biological systems requires numerous experimental replicates for reliable conclusions. Furthermore, evidence of robust algorithms directly exploiting basic biological traits are few. Such algorithms are expected to be efficient in their performance and robust in their prediction.

Results

We have developed a network identification algorithm to accurately infer both the topology and strength of regulatory interactions from time series gene expression data in the presence of significant experimental noise and non-linear behavior. In this novel formulism, we have addressed data variability in biological systems by integrating network identification with the bootstrap resampling technique, hence predicting robust interactions from limited experimental replicates subjected to noise. Furthermore, we have incorporated non-linearity in gene dynamics using the S-system formulation. The basic network identification formulation exploits the trait of sparsity of biological interactions. Towards that, the identification algorithm is formulated as an integer-programming problem by introducing binary variables for each network component. The objective function is targeted to minimize the network connections subjected to the constraint of maximal agreement between the experimental and predicted gene dynamics. The developed algorithm is validated using both in silico and experimental data-sets. These studies show that the algorithm can accurately predict the topology and connection strength of the in silico networks, as quantified by high precision and recall, and small discrepancy between the actual and predicted kinetic parameters. Furthermore, in both the in silico and experimental case studies, the predicted gene expression profiles are in very close agreement with the dynamics of the input data.

Conclusions

Our integer programming algorithm effectively utilizes bootstrapping to identify robust gene regulatory networks from noisy, non-linear time-series gene expression data. With significant noise and non-linearities being inherent to biological systems, the present formulism, with the incorporation of network sparsity, is extremely relevant to gene regulatory networks, and while the formulation has been validated against in silico and E. Coli data, it can be applied to any biological system.

【 授权许可】

   
2012 Chemmangattuvalappil et al.; licensee BioMed Central Ltd.

【 图 表 】

Figure 1.

Figure 2.

Figure 3.

Figure 4.

Figure 5.

Figure 6.

Figure 7.

Figure 8.

【 参考文献 】

• [1]Kabir M, Noman N, Iba H: Reverse engineering gene regulatory network from microarray data using linear time-variant model. BMC Bioinform 2010, 11(Suppl 1):S56. BioMed Central Full Text
• [2]Bansal M, Belcastro V, Ambesi-Impiombato A, di Bernardo D: How to infer gene networks from expression profiles. Mol Syst Biol 2007, 3:122.
• [3]Huang S: Gene expression profiling, genetic networks, and cellular states: an integrating concept for tumorigenesis and drug discovery. J Mole Med 1999, 77(6):469-480.
• [4]Shmulevich I, Dougherty ER, Kim S, Zhang W: Probabilistic Boolean networks: a rule-based uncertainty model for gene regulatory networks. Bioinform 2002, 18(2):261-274.
• [5]Chen X-w, Anantha G, Wang X: An effective structure learning method for constructing gene networks. Bioinform 2006, 22(11):1367-1374.
• [6]Imoto S, Goto T, Miyano S: Estimation of genetic networks and functional structures between genes by using Bayesian network and nonparametric regression. Pac symp Biocomput 2002, 7:12.
• [7]Zhou X, Wang X, Pal R, Ivanov I, Bittner M, Dougherty ER: A Bayesian connectivity-based approach to constructing probabilistic gene regulatory networks. Bioinform 2004, 20(17):2918-2927.
• [8]Basso K, Margolin AA, Stolovitzky G, Klein U, Dalla-Favera R, Califano A: Reverse engineering of regulatory networks in human B cells. Nat Genet 2005, 37(4):382-390.
• [9]Soranzo N, Bianconi G, Altafini C: Comparing association network algorithms for reverse engineering of large-scale gene regulatory networks: synthetic versus real data. Bioinform 2007, 23(13):1640-1647.
• [10]Yu J, Smith VA, Wang PP, Hartemink AJ, Jarvis ED: Advances to Bayesian network inference for generating causal networks from observational biological data. Bioinform 2004, 20(18):3594-3603.
• [11]Zou M, Conzen SD: A new dynamic Bayesian network (DBN) approach for identifying gene regulatory networks from time course microarray data. Bioinform 2005, 21(1):71-79.
• [12]Kimura S, Nakayama S, Hatakeyama M: Genetic network inference as a series of discrimination tasks. Bioinform 2009, 25(7):918-925.
• [13]Yeung MKS, Tegnér J, Collins JJ: Reverse engineering gene networks using singular value decomposition and robust regression. Proc Natl Acad Sci 2002, 99(9):6163-6168.
• [14]Bansal M, Gatta GD, di Bernardo D: Inference of gene regulatory networks and compound mode of action from time course gene expression profiles. Bioinform 2006, 22(7):815-822.
• [15]Liu P-K, Wang F-S: Inference of biochemical network models in S-system using multiobjective optimization approach. Bioinform 2008, 24(8):1085-1092.
• [16]Kikuchi S, Tominaga D, Arita M, Takahashi K, Tomita M: Dynamic modeling of genetic networks using genetic algorithm and S-system. Bioinform 2003, 19(5):643-650.
• [17]Kimura S, Ide K, Kashihara A, Kano M, Hatakeyama M, Masui R, Nakagawa N, Yokoyama S, Kuramitsu S, Konagaya A: Inference of S-system models of genetic networks using a cooperative coevolutionary algorithm. Bioinform 2005, 21(7):1154-1163.
• [18]Thomas R, Mehrotra S, Papoutsakis ET, Hatzimanikatis V: A model-based optimization framework for the inference on gene regulatory networks from DNA array data. Bioinform 2004, 20(17):3221-3235.
• [19]Vilela M, Chou I-C, Vinga S, Vasconcelos A, Voit E, Almeida J: Parameter optimization in S-system models. BMC Syst Biol 2008, 2(1):35. BioMed Central Full Text
• [20]Morishita R, Imade H, Ono I, Ono N, Okamoto M: Finding multiple solutions based on an evolutionary algorithm for inference of genetic networks by S-system. Evolutionary Computation, 2003 CEC '03 The 2003 Congress on: 8–12 Dec. 2003 2003 2003, 615-622. Vol. 611
• [21]Thattai M, van Oudenaarden A: Intrinsic noise in gene regulatory networks. Proc Natl Acad Sci 2001, 98(15):8614-8619.
• [22]Vinje WE, Gallant JL: Sparse Coding and Decorrelation in Primary Visual Cortex During Natural Vision. Sci 2000, 287(5456):1273-1276.
• [23]DeWeese MR, Wehr M, Zador AM: Binary Spiking in Auditory Cortex. J Neurosci 2003, 23(21):10.
• [24]Leclerc RD: Survival of the sparsest: robust gene networks are parsimonious. Mol Syst Biol 2008, 4:213.
• [25]Banerjee I, Maiti S, Parashurama N, Yarmush M: An integer programming formulation to identify the sparse network architecture governing differentiation of embryonic stem cells. Bioinform 2010, 26(10):1332-1339.
• [26]Efron B, Tibshirani RJ: An introduction to bootstrap. Chapman and Hall, New York; 1993.
• [27]Sutton MD, Smith BT, Godoy VG, Walker GC: THE SOS RESPONSE: Recent Insights into umuDC-Dependent Mutagenesis and DNA Damage Tolerance. Annu Rev Genet 2000, 34(1):479-497.
• [28]Ronen M, Rosenberg R, Shraiman BI, Alon U: Assigning numbers to the arrows: Parameterizing a gene regulation network by using accurate expression kinetics. Proc Natl Acad Sci 2002, 99(16):10555-10560.
• [29]Index of /mcb/UriAlon/Papers/SOSData. [http://www.weizmann.ac.il/mcb/UriAlon/Papers/SOSData/ webcite]
• [30]Papadimitriou CH, Steiglitz K: Combinatorial optimization: Algorithms and complexity. Dover, Mineola, NY; 1998.
• [31]Yao X: Evolutionary computation: Theory and applications. World Scientific Publishing, Singapore; 1999.
• [32]Gutenkunst RN, Waterfall JJ, Casey FP, Brown KS, Myers CR, Sethna JP: Universally Sloppy Parameter Sensitivities in Systems Biology Models. PLoS Comput Biol 2007, 3(10):e189.
• [33]Wehrens R, Putter H, Buydens LMC: The bootstrap: a tutorial. Chemometrics and Intelligent Laboratory Syst 2000, 54:18.