Steady state analysis of Boolean molecular network models via model reduction and computational algebra

详细信息    查看全文

• 作者：Alan Veliz-Cuba (1) (2)
  Boris Aguilar (3)
  Franziska Hinkelmann (4)
  Reinhard Laubenbacher (5)
  
  1. Department of Mathematics ; University of Houston ; 651 PGH Building ; Houston ; TX ; USA
  2. Department of Biochemistry and Cell Biology ; Rice University ; W100 George R. Brown Hall ; Houston ; TX ; USA
  3. Department of Computer Science ; Virginia Tech ; Blacksburg ; VA ; USA
  4. TNG Technology Consulting GmbH ; Unterf枚hring ; Germany
  5. Center for Quantitative Medicine ; University of Connecticut Health Center and Jackson Laboratory for Genomic Medicine ; Farmington ; CT ; USA
  
• 关键词：Steady state computation ; Boolean model ; Discrete model
• 刊名：BMC Bioinformatics
• 出版年：2014
• 出版时间：December 2014
• 年：2014
• 卷：15
• 期：1
• 全文大小：363 KB
• 参考文献：1. Zhang, Y, Qian, M, Ouyang, Q, Deng, M, Li, F, Tang, C (2006) Stochastic model of yeast cell-cycle network. Physica D: Nonlinear Phenomena 219: pp. 35-39 CrossRef
  2. Davidich, M, Bornholdt, S (2008) Boolean network model predicts cell cycle sequence of fission yeast. PLoS ONE 3: pp. 1672 CrossRef
  3. Kauffman, S, Peterson, C, Samuelsson, B, Troein, C (2003) Random Boolean network models and the yeast transcriptional network. PNAS 100: pp. 14796-14799 CrossRef
  4. Sahin, O, Frohlich, H, Lobke, C, Korf, U, Burmester, S, Majety, M, Mattern, J, Schupp, I, Chaouiya, C, Thieffry, D, Poustka, A, Wiemann, S, Beissbarth, T, Arlt, D. (2009) Modeling ERBB receptor-regulated g1/s transition to find novel targets for de novo trastuzumab resistance. BMC Syst Biol 3: pp. 1 CrossRef
  5. Klamt, S, Saez-Rodriguez, J, Lindquist, J, Simeoni, L, Gilles, E (2006) A methodology for the structural and functional analysis of signaling and regulatory networks. BMC Bioinformatics 7: pp. 56 CrossRef
  6. Li, F, Long, T, Lu, Y, Ouyang, Q, Tang, C (2004) The yeast cell-cycle network is robustly designed. Proc Natl Acad Sci USA 101: pp. 4781-4786 CrossRef
  7. Albert, R, Othmer, H (2003) The topology of the regulatory interactions predicts the expression pattern of the segment polarity genes in Drosophila melanogaster. J Theor Biol 223: pp. 1-18 CrossRef
  8. Mai, Z, Liu, H (2009) Boolean network-based analysis of the apoptosis network: Irreversible apoptosis and stable surviving. J Theor Biol 259: pp. 760-769 CrossRef
  9. Veliz-Cuba, A, Stigler, B (2011) Boolean models can explain bistability in the lac operon. J Comput Biol 18: pp. 783-794 CrossRef
  10. Mendoza, L, Xenarios, I (2006) A method for the generation of standardized qualitative dynamical systems of regulatory networks. Theor Biol Med Model 3: pp. 13 CrossRef
  11. Murrugarra, D, Veliz-Cuba, A, Aguilar, B, Arat, S, Laubenbacher, R (2012) Modeling stochasticity and variability in gene regulatory networks. EURASIP J Bioinformatics Syst Biol 2012: pp. 5 CrossRef
  12. Hinkelmann, F, Murrugarra, D, Jarrah, A, Laubenbacher, R (2011) A mathematical framework for agent based models of complex biological networks. Bull Math Biol 73: pp. 1583-1602 CrossRef
  13. Singh, A, Nascimento, J, Kowar, S, Busch, H, Boerries, M (2012) Boolean approach to signalling pathway modelling in hgf-induced keratinocyte migration. Bioinformatics 28: pp. 495-501 CrossRef
  14. Saez-Rodriguez, J, Simeoni, L, Lindquist, J, Hemenway, R, Bommhardt, U, Arndt, B, Haus, U, Weismantel, R, Gilles, E, Klamt, S, Schraven, B (2007) A logical model provides insights into t cell receptor signaling. PLoS Comput Biol 3: pp. 163 CrossRef
  15. Raza, S, Robertson, K, Lacaze, P, Page, D, Enright, A, Ghazal, P, Freeman, T (2008) A logic-based diagram of signalling pathways central to macrophage activation. BMC Syst Biol 2: pp. 36 CrossRef
  16. Kazemzadeh, L, Cvijovic, M, Petranovic, D (2012) Boolean model of yeast apoptosis as a tool to study yeast and human apoptotic regulations. Front Physiol 3: pp. 446 CrossRef
  17. Madrahimov, A, Helikar, T, Kowal, B, Lu, G, Rogers, J (2013) Dynamics of influenza virus and human host interactions during infection and replication cycle. Bull Math Biol 75: pp. 988-1011 CrossRef
  18. Saadatpour, A, Wang, R, Liao, A, Liu, X, Loughran, T, Albert, I, Albert, R (2011) Dynamical and structural analysis of a T-cell survival network identifies novel candidate therapeutic targets for large granular lymphocyte leukemia. PLoS Comput Biol 7: pp. 1002267 CrossRef
  19. Zhang, R, Shah, M, Yang, J, Nyland, S, Liu, X, Yun, J, Albert, R, Loughran, T (2008) Network model of survival signaling in large granular lymphocyte leukemia. PNAS 105: pp. 16308-16313 CrossRef
  20. Samaga, R, Saez-Rodriguez, J, Alexopoulos, L, Sorger, P, Klamt, S (2009) The logic of EGFR/ErbB signaling: theoretical properties and analysis of high-throughput data. PLoS Comput Biol 5: pp. 1000438 CrossRef
  21. Helikar, T, Konvalina, J, Heidel, J, Rogers, J (2008) Emergent decision-making in biological signal transduction networks. PNAS 105: pp. 1913-1918 CrossRef
  22. Helikar, T, Kochi, N, Kowal, B, Dimri, M, Naramura, M, Raja, S, Band, V, Band, H, Rogers, J (2013) A comprehensive, multi-scale dynamical model of ErbB receptor signal transduction in human mammary epithelial cells. PLoS ONE 8: pp. 61757 CrossRef
  23. Akutsu, T, Kuhara, S, Maruyama, O, Miyano, S (1998) A system for identifying genetic networks from gene expression patterns produced by gene disruptions and overexpressions. Genome Inform 9: pp. 151-160
  24. Zhao, Q (2005) A remark on 鈥渟calar equations for synchronous Boolean networks with biological applications鈥?by C. Farrow, J. Heidel, J. Maloney, and J. Rogers. IEEE Trans Neural Netw 16: pp. 1715-1716 CrossRef
  25. Veliz-Cuba, A (2011) Reduction of Boolean network models. J Theor Biol 289: pp. 167-172 CrossRef
  26. Za帽udo, J, Albert, R (2013) An effective network reduction approach to find the dynamical repertoire of discrete dynamic networks. Chaos: Interdiscip J Nonlinear Sci 23: pp. 025111 CrossRef
  27. Saadatpour, A, Albert, I, Albert, R (2010) Attractor analysis of asynchronous Boolean models of signal transduction networks. J Theor Biol 266: pp. 641-656 CrossRef
  28. Naldi, A, Remy, E, Thieffry, D, Chaouiya, C A reduction of logical regulatory graphs preserving essential dynamical properties. In: Degano, P, Gorrieri, R eds. (2009) Computational Methods in Systems Biology. Lecture Notes in Computer Science. Volume 5688. Springer, Heidelberg, Germany, pp. 266-280
  29. Veliz-Cuba, A, Jarrah, A, Laubenbacher, R (2010) Polynomial algebra of discrete models in systems biology. Bioinformatics 26: pp. 1637-1643 CrossRef
  30. Hinkelmann, F, Brandon, M, Guang, B, McNeill, R, Blekherman, G, Veliz-Cuba, A, Laubenbacher, R (2011) ADAM: Analysis of discrete models of biological systems using computer algebra. BMC Bioinformatics 12: pp. 295 CrossRef
  31. Zou, Y (2013) An algorithm for detecting fixed points of Boolean network. Complex Medical Engineering (CME), 2013 ICME International Conference On. IEEE, Piscataway, New Jersey, pp. 670-673 CrossRef
  32. Devloo, V, Hansen, P (2003) Identification of all steady states in large networks by logical analysis. Bull Math Biol 65: pp. 1025-1051 CrossRef
  33. Tamura, T, Akutsu, T (2009) Detecting a singleton attractor in a Boolean network utilizing SAT algorithms. IEICE Trans Fundam Electron Commun Comput Sci E92-A: pp. 493-501 CrossRef
  34. Dubrova, E, Teslenko, M (2011) A SAT-based algorithm for finding attractors in synchronous Boolean networks. IEEE/ACM Trans Comput Biol Bioinformatics 8: pp. 1393-1399 CrossRef
  35. Melkman, A, Tamura, T, Akutsu, T (2010) Determining a singleton attractor of an AND/OR Boolean network in O(1.587 n ) time. Inform Process Lett 110: pp. 565-569 CrossRef
  36. Tamura, T, Hayashida, M, Akutsu, T (2009) Integer programming-based methods for attractor detection and control of boolean networks. Proceedings of the 48th IEEE Conference on Decision and Control held jointly with the 28th Chinese Control Conference. CDC/CCC 2009. Piscataway, New Jersey, pp. 5610-5617
  37. Zhang, S, Hayashida, M, Akutsu, T, Ching, W, Ng, M (2007) Algorithms for finding small attractors in Boolean networks. EURASIP J Bioinformatics Syst Biol 2007: pp. 4
  38. Zheng, D, Yang, G, Li, X, Wang, Z, Liu, F, He, L (2013) An efficient algorithm for computing attractors of synchronous and asynchronous Boolean networks. PLoS ONE 8: pp. 60593 CrossRef
  39. Garg, A, Di Cara, A, Xenarios, I, Mendoza, L, De Micheli, G (2008) Synchronous versus asynchronous modeling of gene regulatory networks. Bioinformatics 24: pp. 1917-1925 CrossRef
  40. Dubrova, E, Teslenko, M, Martinelli, A (2005) Kauffman networks: analysis and applications. Proceedings of the 2005 IEEE/ACM International Conference on Computer-aided Design. ICCAD 鈥?5. IEEE Computer Society, Piscataway, New Jersey, pp. 479-484 CrossRef
  41. Naldi, A, Thieffry, D, Chaouiya, C Decision diagrams for the representation and analysis of logical models of genetic networks. In: Calder, M, Gilmore, S eds. (2007) Computational Methods in Systems Biology. Lecture Notes in Computer Science. Springer, Heidelberg, Germany, pp. 233-247 CrossRef
  42. Veliz-Cuba, A, Buschur, K, Hamershock, R, Kniss, A, Wolff, E, Laubenbacher, R (2013) AND-NOT logic framework for steady state analysis of Boolean network models. Appl Math Inform Sci 4: pp. 1263-1274 CrossRef
  43. Veliz-Cuba, A, Laubenbacher, R, Aguilar, B (2013) Dimension reduction of large AND-NOT network models.
  44. Grayson D, Stillman M: Macaulay 2, a software system for research in algebraic geometry . Available at [http://www.math.uiuc.edu/Macaulay2/]
  45. Siek, J, Lee, L, Lumsdaine, A (2000) Boost graph library.
  46. Sarrazin, P (2013) BoolStuff Library.
  47. Murrugarra, D, Laubenbacher, R (2011) Regulatory patterns in molecular interaction networks. J Theor Biol 288: pp. 66-72 CrossRef
  48. Kauffman, S, Peterson, C, Samuelsson, B, Troein, C (1710) Genetic networks with canalyzing Boolean rules are always stable. PNAS 101: pp. 2-17107
  49. Raeymaekers, L (2002) Dynamics of Boolean networks controlled by biologically meaningful functions. J Theor Biol 218: pp. 331-341 CrossRef
  50. Helikar, T, Kowal, B, McClenathan, S, Bruckner, M, Rowley, T, Madrahimov, A, Wicks, B, Shrestha, M, Limbu, K, Rogers, J (2012) The cell collective: toward an open and collaborative approach to systems biology. BMC Syst Biol 6: pp. 96 CrossRef
  51. Albert, R (2005) Scale-free networks in cell biology. J Cell Sci 118: pp. 4947-4957 CrossRef
  
• 刊物主题：Bioinformatics; Microarrays; Computational Biology/Bioinformatics; Computer Appl. in Life Sciences; Combinatorial Libraries; Algorithms;
• 出版者：BioMed Central
• ISSN：1471-2105

文摘

Background A key problem in the analysis of mathematical models of molecular networks is the determination of their steady states. The present paper addresses this problem for Boolean network models, an increasingly popular modeling paradigm for networks lacking detailed kinetic information. For small models, the problem can be solved by exhaustive enumeration of all state transitions. But for larger models this is not feasible, since the size of the phase space grows exponentially with the dimension of the network. The dimension of published models is growing to over 100, so that efficient methods for steady state determination are essential. Several methods have been proposed for large networks, some of them heuristic. While these methods represent a substantial improvement in scalability over exhaustive enumeration, the problem for large networks is still unsolved in general. Results This paper presents an algorithm that consists of two main parts. The first is a graph theoretic reduction of the wiring diagram of the network, while preserving all information about steady states. The second part formulates the determination of all steady states of a Boolean network as a problem of finding all solutions to a system of polynomial equations over the finite number system with two elements. This problem can be solved with existing computer algebra software. This algorithm compares favorably with several existing algorithms for steady state determination. One advantage is that it is not heuristic or reliant on sampling, but rather determines algorithmically and exactly all steady states of a Boolean network. The code for the algorithm, as well as the test suite of benchmark networks, is available upon request from the corresponding author. Conclusions The algorithm presented in this paper reliably determines all steady states of sparse Boolean networks with up to 1000 nodes. The algorithm is effective at analyzing virtually all published models even those of moderate connectivity. The problem for large Boolean networks with high average connectivity remains an open problem.