Abstract
Deciphering gene regulatory networks’ functioning is an essential step for better understanding of life, as these networks play a fundamental role in the control of cellular processes. Boolean networks have been widely used to represent gene regulatory networks. They allow to describe the dynamics of complex gene regulatory networks straightforwardly and efficiently. The attractors are essential in the analysis of the dynamics of a Boolean network. They explain that a particular cell can acquire specific phenotypes that may be transmitted over several generations. In this work, we consider a new representation of Boolean networks’ dynamics based on a new semantics used in Answer Set Programming (ASP). We use logic programs and ASP to express and deal with gene regulatory networks seen as Boolean networks, and develop a method to detect all the attractors of such networks. We first show how to represent and deal with general Boolean networks for the synchronous and asynchronous updates modes, where the computation of attractors requires a simulation of these networks’ dynamics. Then, we propose an approach for the particular case of circular networks where no simulation is needed. This last specific case plays an essential role in biological systems. We show several theoretical properties; in particular, simple attractors of the gene networks are represented by the stable models of the corresponding logic programs and cyclic attractors by its extra-stable models. These extra-stable models correspond to the extra-extensions of the new semantics that are not captured by the semantics of stable models. We then evaluate the proposed approach for general Boolean networks on real biological networks and the one dedicated to the case of circular networks on Boolean networks generated randomly. The obtained results for both approaches are encouraging.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
Data Availability
The benchmarks are available with the identifier https://zenodo.org/record/8103494
References
De Jong, H.: Modeling and simulation of genetic regulatory systems: a literature review. J. Comput. Biol. 9(1), 67–103 (2002)
Tran, N., Baral, C.: Hypothesizing about signaling networks. J. Appl. Log. 7, 253–274 (2009)
Kauffman, S.A.: Metabolic stability and epigenesis in randomly constructed genetic nets. J. Theor. Biol. 22(3), 437–467 (1969)
Kauffman, S.A., et al.: The origins of order: Self-organization and selection in evolution. Oxford University Press, (1993)
Shmulevich, I., Dougherty, E.R., Zhang, W.: From boolean to probabilistic Boolean networks as models of genetic regulatory networks. Proc. IEEE 90(11), 1778–1792 (2002)
Garg, A., Xenarios, I., Mendoza, L., DeMicheli, G: An efficient method for dynamic analysis of gene regulatory networks and in silico gene perturbation experiments, pp. 62–76 (2007). Springer
De Jong, H., Page, M.: Search for steady states of piecewise-linear differential equation models of genetic regulatory networks. IEEE/ACM Trans. Comput. Biol. Bioinforma. 5(2), 208–222 (2008)
Mendoza, L.: A network model for the control of the differentiation process in Th cells. BioSyst. 84(2), 101–114 (2006)
Espinosa-Soto, C., Padilla-Longoria, P., Alvarez-Buylla, E.R.: A gene regulatory network model for cell-fate determination during Arabidopsis thaliana flower development that is robust and recovers experimental gene expression profiles. Plant Cell 16(11), 2923–2939 (2004)
Marek, V.W., Truszczynski, M.L.: Stable models and an alternative logic programming paradigm. Logic Programming Paradigm, pp. 375–398 (1999)
Lin, F., Zhao, Y.: Assat: Computing answer sets of a logic program by SAT solvers. Artificial Intelligence, pp. 115–137 (2004)
Gebser, M., Kaufmann, B., Neumann, A., Schaub, T.: Conflict-driven answer set solving. In: Veloso, M.M. (ed.) IJCAI 2007, Proceedings of the 20th International joint conference on artificial intelligence, Hyderabad, India, January 6-12, 2007, p. 386 (2007)
Simons, P., Nimelä, I., Soininen, T.: Extending and implementing the stable model semantic. Artif. Intell. 138, 181–234 (2002)
Alviano, M., Dodaro, C., Faber, W, Leone, N., Ricca, F.: Wasp: A native ASP solver based on constraint learning. In: International conference on logic programming and nonmonotonic reasoning, pp. 54–66 (2013). Springer
Erdem, E., Gelfond, M., Leone, N.: Applications of answer set programming. AI Mag. 37, 53–68 (2016)
Khaled, T., Benhamou, B., Siegel, P.: A new method for computing stable models in logic programming. Tools with Artificial Intelligence (ICTAI), pp. 800–807 (2018)
Khaled, T., Benhamou, B.: Symmetry breaking in a new stable model search method. 22nd International Conference on Logic for Programming Artificial Intelligence and Reasoning (LPAR-22), Kalpa Publications in Computing 9, 58–74 (2018)
Benhamou, B., Siegel, P.: A new semantics for logic programs capturing and extending the stable model semantics. Tools with Artificial Intelligence (ICTAI), pp. 25–32 (2012)
Gelfond, M., Lifschitz, V.: The stable model semantics for logic programming. ICLP/SLP 50, 1070–1080 (1988)
Khaled, T., Benhamou, B.: An ASP-based approach for attractor enumeration in synchronous and asynchronous Boolean networks. Proceedings 35th International Conference on Logic Programming, ICLP 2019, Las Cruces, NM, USA, 295–301 (2019)
Khaled, T., Benhamou, B.: An ASP-based approach for boolean networks representation and attractor detection. In: LPAR, pp. 317–333 (2020)
Trinh, V.-G., Hiraishi, K., Benhamou, B.: Computing attractors of large-scale asynchronous Boolean networks using minimal trap spaces. In: Proceedings of the 13th ACM International conference on bioinformatics, computational biology and health informatics, pp. 1–10 (2022)
Jacob, F., Monod, J.: Genetic regulatory mechanisms in the synthesis of proteins. J. Mol. Biol. 3(3), 318–356 (1961)
Zheng, D., Yang, G., Li, X., Wang, Z., Liu, F., He, L.: An efficient algorithm for computing attractors of synchronous and asynchronous Boolean networks. PloS One 8(4), 60593 (2013)
Thomas, R.: On the relation between the logical structure of systems and their ability to generate multiple steady states or sustained oscillations. In: Numerical methods in the study of critical phenomena, pp. 180–193 (1981)
Remy, E.., Mossé, B.., Chaouiya, C.., Thieffry, D..: A description of dynamical graphs associated to elementary regulatory circuits. Bioinforma. 19(suppl–2), 172–178 (2003)
Gelfond, M., Lifschitz, V.: Classical negation in logic programs and disjunctive databases. New Gener. Comput. 9, 365–385 (1991)
Williams, R., Gomes, C.P., Selman, B.: Backdoors to typical case complexity. Int. Jt. Conf. Artif. Intell. 18, 1173–1178 (2003)
Davis, M., Logemann, G., Loveland, D.: A machine program for theorem proving. Commun. ACM 5, 394–397 (1962)
Gebser, M., Kaminski, R., Kaufmann, B., Schaub, T.: Multi-shot ASP solving with clingo. Theory Pract. Log. Program. 19(1), 27–82 (2019)
Dubrova, E., Teslenko, M.: A SAT-based algorithm for finding attractors in synchronous Boolean networks. IEEE/ACM Trans. Comput. Biol. Bioinforma. 8(5), 1393–1399 (2011)
Garg, A., Xenarios, I., Mendoza, L., DeMicheli, G.: An efficient method for dynamic analysis of gene regulatory networks and in silico gene perturbation experiments. In: Annual international conference on research in computational molecular biology, pp. 62–76 (2007). Springer
Ay, F., Xu, F., Kahveci, T.: Scalable steady state analysis of Boolean biological regulatory networks. PloS One 4(12), 7992 (2009)
Davidich, M.I., Bornholdt, S.: Boolean network model predicts cell cycle sequence of fission yeast. PloS One 3(2), 1672 (2008)
Klarner, H., Streck, A., Siebert, H.: PyBoolNet: a python package for the generation, analysis and visualization of Boolean networks. Bioinform. 33(5), 770–772 (2017). https://doi.org/10.1093/bioinformatics/btw682
Gebser, M., Kaufmann, B., Kaminski, R., Ostrowski, M., Schaub, T., Schneider, M.: Potassco: The Potsdam answer set solving collection. AI Commun. 24(2), 107–124 (2011). https://doi.org/10.3233/AIC-2011-0491
Sanchez-Corrales, Y.-E., Alvarez-Buylla, E.R., Mendoza, L.: The Arabidopsis thaliana flower organ specification gene regulatory network determines a robust differentiation process. J. Theor. Biol. 264(3), 971–983 (2010)
Li, F., Long, T., Lu, Y., Ouyang, Q., Tang, C.: The yeast cell-cycle network is robustly designed. Proc. Natl. Acad. Sci. 101(14), 4781–4786 (2004)
Kaufman, M., Urbain, J., Thomas, R.: Towards a logical analysis of the immune response. J. Theor. Biol. 114(4), 527–561 (1985)
Sánchez, L., Thieffry, D.: A logical analysis of the Drosophila gap-gene system. J. Theor. Biol. 211(2), 115–141 (2001)
Albert, R., Othmer, H.G.: The topology of the regulatory interactions predicts the expression pattern of the segment polarity genes in Drosophila melanogaster. J. Theor. Biol. 223(1), 1–18 (2003)
González, A., Chaouiya, C., Thieffry, D.: Logical modelling of the role of the Hh pathway in the patterning of the Drosophila wing disc. Bioinforma. 24(16), 234–240 (2008)
Berntenis, N., Ebeling, M.: Detection of attractors of large Boolean networks via exhaustive enumeration of appropriate subspaces of the state space. BMC Bioinforma. 14(1), 1–10 (2013)
He, Q., Xia, Z., Lin, B.: An efficient approach of attractor calculation for large-scale Boolean gene regulatory networks. J. Theor. Biol. 408, 137–144 (2016). https://doi.org/10.1016/j.jtbi.2016.08.006
He, Q., Xia, Z., Lin, B.: P_UNSAT approach of attractor calculation for Boolean gene regulatory networks. J. Theor. Biol. 447, 171–177 (2018). https://doi.org/10.1016/j.jtbi.2018.03.037
Gebser, M., Schaub, T., Thiele, S., Veber, P.: Detecting inconsistencies in large biological networks with answer set programming. Theor. Prac. Log. Program. 11(2–3), 323–360 (2011). https://doi.org/10.1017/s1471068410000554
Inoue, K.: Logic programming for Boolean networks. In: 22nd International joint conference on artificial intelligence (2011)
Mushthofa, M., Torres, G., Van de Peer, Y., Marchal, K., De Cock, M.: Asp-g: an ASP-based method for finding attractors in genetic regulatory networks. Bioinforma. 30(21), 3086–3092 (2014)
Fayruzov, T., De Cock, M., Cornelis, C, Vermeir, D.: Modeling protein interaction networks with answer set programming. In: 2009 IEEE International conference on bioinformatics and biomedicine, pp. 99–104 (2009). IEEE
Apt, K.R., Blair, H.A., Walker, A.: Towards a theory of declarative knowledge. In: Foundations of deductive databases and logic programming, pp. 89–148 (1988)
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflicts of interest
The authors declare that they have no conflict of interest.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Tarek Khaled and Belaid Benhamou are contributed equally to this work.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Khaled, T., Benhamou, B. & Trinh, VG. Using answer set programming to deal with boolean networks and attractor computation: application to gene regulatory networks of cells. Ann Math Artif Intell 91, 713–750 (2023). https://doi.org/10.1007/s10472-023-09886-7
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10472-023-09886-7