Document Open Access Logo

Efficient Enumeration of Fixed Points in Complex Boolean Networks Using Answer Set Programming

Authors Van-Giang Trinh , Belaid Benhamou, Sylvain Soliman

PDF
Thumbnail PDF

File

LIPIcs.CP.2023.35.pdf
  • Filesize: 0.77 MB
  • 19 pages

Document Identifiers

Author Details

Van-Giang Trinh
  • LIS, Aix-Marseille University, Marseille, France
Belaid Benhamou
  • LIS, Aix-Marseille University, Marseille, France
Sylvain Soliman
  • Lifeware team, Inria Saclay, Palaiseau, France

Funding

  • Trinh, Van-Giang: This work is supported by Institut Carnot STAR, Marseille, France.

Cite As Get BibTex

Van-Giang Trinh, Belaid Benhamou, and Sylvain Soliman. Efficient Enumeration of Fixed Points in Complex Boolean Networks Using Answer Set Programming. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 35:1-35:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.CP.2023.35

Abstract

Boolean Networks (BNs) are an efficient modeling formalism with applications in various research fields such as mathematics, computer science, and more recently systems biology. One crucial problem in the BN research is to enumerate all fixed points, which has been proven crucial in the analysis and control of biological systems. Indeed, in that field, BNs originated from the pioneering work of R. Thomas on gene regulation and from the start were characterized by their asymptotic behavior: complex attractors and fixed points. The former being notably more difficult to compute exactly, and specific to certain biological systems, the computation of stable states (fixed points) has been the standard way to analyze those BNs for years. However, with the increase in model size and complexity of Boolean update functions, the existing methods for this problem show their limitations. To our knowledge, the most efficient state-of-the-art methods for the fixed point enumeration problem rely on Answer Set Programming (ASP). Motivated by these facts, in this work we propose two new efficient ASP-based methods to solve this problem. We evaluate them on both real-world and pseudo-random models, showing that they vastly outperform four state-of-the-art methods as well as can handle very large and complex models.

Subject Classification

ACM Subject Classification
  • Computing methodologies → Logic programming and answer set programming
  • Applied computing → Computational biology
  • Applied computing → Systems biology
Keywords
  • Computational systems biology
  • Boolean network
  • Fixed point
  • Answer set programming

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. Emna Ben Abdallah, Maxime Folschette, Olivier F. Roux, and Morgan Magnin. ASP-based method for the enumeration of attractors in non-deterministic synchronous and asynchronous multi-valued networks. Algorithms Mol. Biol., 12(1):20:1-20:23, 2017. URL: https://doi.org/10.1186/s13015-017-0111-2.
  2. Sara Sadat Aghamiri, Vidisha Singh, Aurélien Naldi, Tomás Helikar, Sylvain Soliman, Anna Niarakis, and Jinbo Xu. Automated inference of Boolean models from molecular interaction maps using CaSQ. Bioinform., 36(16):4473-4482, 2020. URL: https://doi.org/10.1093/bioinformatics/btaa484.
  3. Tatsuya Akutsu, Satoru Kuhara, Osamu Maruyama, and Satoru Miyano. A system for identifying genetic networks from gene expression patterns produced by gene disruptions and overexpressions. Genome Informatics, 9:151-160, 1998. URL: https://doi.org/10.11234/gi1990.9.151.
  4. Tatsuya Akutsu, Avraham A. Melkman, Takeyuki Tamura, and Masaki Yamamoto. Determining a singleton attractor of a Boolean network with nested canalyzing functions. J. Comput. Biol., 18(10):1275-1290, 2011. URL: https://doi.org/10.1089/cmb.2010.0281.
  5. Tatsuya Akutsu, Yang Zhao, Morihiro Hayashida, and Takeyuki Tamura. Integer programming-based approach to attractor detection and control of Boolean networks. IEICE Trans. Inf. Syst., 95-D(12):2960-2970, 2012. URL: https://doi.org/10.1587/transinf.E95.D.2960.
  6. Julio Aracena. Maximum number of fixed points in regulatory Boolean networks. Bull. Math. Biol., 70:1398-1409, 2008. URL: https://doi.org/10.1007/s11538-008-9304-7.
  7. Julio Aracena, Luis Cabrera-Crot, and Lilian Salinas. Finding the fixed points of a Boolean network from a positive feedback vertex set. Bioinform., 37(8):1148-1155, 2021. URL: https://doi.org/10.1093/bioinformatics/btaa922.
  8. Ferhat Ay, Günhan Gülsoy, and Tamer Kahveci. Finding steady states of large scale regulatory networks through partitioning. In International Workshop on Genomic Signal Processing and Statistics, pages 1-4. IEEE, 2010. URL: https://doi.org/10.1109/GENSIPS.2010.5719669.
  9. Nikola Benes, Lubos Brim, Samuel Pastva, and David Safránek. Computing bottom SCCs symbolically using transition guided reduction. In International Conference on Computer Aided Verification, pages 505-528. Springer, 2021. URL: https://doi.org/10.1007/978-3-030-81685-8_24.
  10. Nikolaos Berntenis and Martin Ebeling. Detection of attractors of large Boolean networks via exhaustive enumeration of appropriate subspaces of the state space. BMC Bioinform., 14(1):1-10, 2013. URL: https://doi.org/10.1186/1471-2105-14-361.
  11. R. E. Bryant. Graph-based algorithms for Boolean function manipulation. IEEE Trans. Comput., 35(8):677-691, 1986. Google Scholar
  12. Stéphanie Chevalier, Vincent Noël, Laurence Calzone, Andrei Yu. Zinovyev, and Loïc Paulevé. Synthesis and simulation of ensembles of Boolean networks for cell fate decision. In International Conference on Computational Methods in Systems Biology, pages 193-209. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-60327-4_11.
  13. Karla Fabiola Corral-Jara, Camille Chauvin, Wassim Abou-Jaoudé, Maximilien Grandclaudon, Aurélien Naldi, Vassili Soumelis, and Denis Thieffry. Interplay between SMAD2 and STAT5A is a critical determinant of IL-17A/IL-17F differential expression. Mol. Biomed., 2(1):9, 2021. URL: https://doi.org/10.1186/s43556-021-00034-3.
  14. Steve Dworschak, Susanne Grell, Victoria J. Nikiforova, Torsten Schaub, and Joachim Selbig. Modeling biological networks by action languages via answer set programming. Constraints An Int. J., 13(1-2):21-65, 2008. URL: https://doi.org/10.1007/s10601-007-9031-y.
  15. Swann Floc'Hlay, Maria Dolores Molina, Céline Hernandez, Emmanuel Haillot, Morgane Thomas-Chollier, Thierry Lepage, and Denis Thieffry. Deciphering and modelling the TGF-β signalling interplays specifying the dorsal-ventral axis of the sea urchin embryo. Dev., 148(2):dev189944, 2021. URL: https://doi.org/10.1242/dev.189944.
  16. Piyali Ganguli, Saikat Chowdhury, Rupa Bhowmick, and Ram Rup Sarkar. Temporal protein expression pattern in intracellular signalling cascade during T-cell activation: A computational study. J. Biosci., 40(4):769-789, September 2015. URL: https://doi.org/10.1007/s12038-015-9561-1.
  17. Piyali Ganguli, Saikat Chowdhury, Shomeek Chowdhury, and Ram Rup Sarkar. Identification of Th1/Th2 regulatory switch to promote healing response during leishmaniasis: a computational approach. EURASIP J. Bioinform. Syst. Biol., 2015:13, 2015. URL: https://doi.org/10.1186/s13637-015-0032-7.
  18. Martin Gebser, Benjamin Kaufmann, Roland Kaminski, Max Ostrowski, Torsten Schaub, and Marius Schneider. Potassco: The Potsdam answer set solving collection. AI Commun., 24(2):107-124, 2011. URL: https://doi.org/10.3233/AIC-2011-0491.
  19. Michael Gelfond and Vladimir Lifschitz. The stable model semantics for logic programming. In International Conference and Symposium on Logic Programming, pages 1070-1080. MIT Press, 1988. Google Scholar
  20. Carlos Gershenson. Classification of random Boolean networks. In Artificial Life VIII, Proceedings of the Eighth International Conference on Artificial Life, pages 1-8, 2003. Google Scholar
  21. Trinh Van Giang, Tatsuya Akutsu, and Kunihiko Hiraishi. An FVS-based approach to attractor detection in asynchronous random Boolean networks. IEEE ACM Trans. Comput. Biol. Bioinform., 19(2):806-818, 2022. URL: https://doi.org/10.1109/TCBB.2020.3028862.
  22. Leon Glass and Stuart A Kauffman. The logical analysis of continuous, non-linear biochemical control networks. J. Theor. Biol., 39(1):103-129, 1973. URL: https://doi.org/10.1016/0022-5193(73)90208-7.
  23. Eric Goles and Lilian Salinas. Sequential operator for filtering cycles in Boolean networks. Adv. Appl. Math., 45(3):346-358, 2010. URL: https://doi.org/10.1016/j.aam.2010.03.002.
  24. A Gonzalez Gonzalez, Aurélien Naldi, Lucas Sanchez, Denis Thieffry, and Claudine Chaouiya. GINsim: a software suite for the qualitative modelling, simulation and analysis of regulatory networks. Biosyst., 84(2):91-100, 2006. URL: https://doi.org/10.1016/j.biosystems.2005.10.003.
  25. Changki Hong, Jeewon Hwang, Kwang-Hyun Cho, and Insik Shin. An efficient steady-state analysis method for large Boolean networks with high maximum node connectivity. PLoS One, 10(12):e0145734, December 2015. URL: https://doi.org/10.1371/journal.pone.0145734.
  26. Katsumi Inoue. Logic programming for Boolean networks. In International Joint Conference on Artificial Intelligence, pages 924-930. IJCAI/AAAI, 2011. URL: https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-160.
  27. Roland Kaminski, Torsten Schaub, Anne Siegel, and Santiago Videla. Minimal intervention strategies in logical signaling networks with ASP. Theory Pract. Log. Program., 13(4-5):675-690, 2013. URL: https://doi.org/10.1017/S1471068413000422.
  28. Hannes Klarner, Adam Streck, and Heike Siebert. PyBoolNet: a python package for the generation, analysis and visualization of Boolean networks. Bioinform., 33(5):770-772, 2017. URL: https://doi.org/10.1093/bioinformatics/btw682.
  29. Tomoya Mori and Tatsuya Akutsu. Attractor detection and enumeration algorithms for Boolean networks. Comput. Struct. Biotechnol. J., 20:2512-2520, 2022. URL: https://doi.org/10.1016/j.csbj.2022.05.027.
  30. Mushthofa Mushthofa, Gustavo Torres, Yves Van de Peer, Kathleen Marchal, and Martine De Cock. ASP-G: an ASP-based method for finding attractors in genetic regulatory networks. Bioinform., 30(21):3086-3092, 2014. URL: https://doi.org/10.1093/bioinformatics/btu481.
  31. Aurélien Naldi. BioLQM: a Java toolkit for the manipulation and conversion of logical qualitative models of biological networks. Front. Physiol., 9:1605, 2018. URL: https://doi.org/10.3389/fphys.2018.01605.
  32. Aurélien Naldi, Pedro T. Monteiro, Christoph Müssel, Hans A. Kestler, Denis Thieffry, Ioannis Xenarios, Julio Saez-Rodriguez, Tomás Helikar, and Claudine Chaouiya. Cooperative development of logical modelling standards and tools with CoLoMoTo. Bioinform., 31(7):1154-1159, 2015. URL: https://doi.org/10.1093/bioinformatics/btv013.
  33. Karen J Nuñez-Reza, Aurélien Naldi, Arantza Sánchez-Jiménez, Ana V Leon-Apodaca, M Angélica Santana, Morgane Thomas-Chollier, Denis Thieffry, and Alejandra Medina-Rivera. Logical modelling of in vitro differentiation of human monocytes into dendritic cells unravels novel transcriptional regulatory interactions. Interface Focus, 11(4):20200061, 2021. URL: https://doi.org/10.1098/rsfs.2020.0061.
  34. Loïc Paulevé, Juraj Kolčák, Thomas Chatain, and Stefan Haar. Reconciling qualitative, abstract, and scalable modeling of biological networks. Nat. Commun., 11(1), August 2020. URL: https://doi.org/10.1038/s41467-020-18112-5.
  35. Alexandre Rocca, Nicolas Mobilia, Eric Fanchon, Tony Ribeiro, Laurent Trilling, and Katsumi Inoue. ASP for construction and validation of regulatory biological networks. Logical Modeling of Biological Systems, pages 167-206, 2014. Google Scholar
  36. Jesper C Romers and Marcus Krantz. rxncon 2.0: a language for executable molecular systems biology. BioRxiv, page 107136, 2017. URL: https://doi.org/10.1101/107136.
  37. Torsten Schaub and Sven Thiele. Metabolic network expansion with answer set programming. In International Conference on Logic Programming, pages 312-326. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-02846-5_27.
  38. Emmalee Sullivan, Marlayna Harris, Arnav Bhatnagar, Eric Guberman, Ian Zonfa, and Erzsébet Ravasz Regan. Boolean modeling of mechanosensitive Epithelial to Mesenchymal Transition and its reversal. bioRxiv, September 2022. URL: https://doi.org/10.1101/2022.08.29.505701.
  39. René Thomas. Boolean formalisation of genetic control circuits. J. Theor. Biol., 42:565-583, 1973. URL: https://doi.org/10.1016/0022-5193(73)90247-6.
  40. René Thomas. Regulatory networks seen as asynchronous automata: a logical description. J. Theor. Biol., 153(1):1-23, 1991. URL: https://doi.org/10.1016/S0022-5193(05)80350-9.
  41. René Thomas and Richard d'Ari. Biological feedback. CRC press, 1990. Google Scholar
  42. Van-Giang Trinh, Kunihiko Hiraishi, and Belaid Benhamou. Computing attractors of large-scale asynchronous Boolean networks using minimal trap spaces. In ACM International Conference on Bioinformatics, Computational Biology and Health Informatics, pages 13:1-13:10. ACM, 2022. URL: https://doi.org/10.1145/3535508.3545520.
  43. Eirini Tsirvouli, Felicity Ashcroft, Berit Johansen, and Martin Kuiper. Logical and experimental modeling of cytokine and eicosanoid signaling in psoriatic keratinocytes. iScience, 24(12):103451, 2021. URL: https://doi.org/10.1016/j.isci.2021.103451.
  44. Leslie G Valiant. The complexity of enumeration and reliability problems. SIAM J. Comput., 8(3):410-421, 1979. Google Scholar
  45. Alan Veliz-Cuba, Boris Aguilar, Franziska Hinkelmann, and Reinhard C. Laubenbacher. Steady state analysis of Boolean molecular network models via model reduction and computational algebra. BMC Bioinform., 15(1):1-8, 2014. URL: https://doi.org/10.1186/1471-2105-15-221.
  46. Santiago Videla, Carito Guziolowski, Federica Eduati, Sven Thiele, Martin Gebser, Jacques Nicolas, Julio Saez-Rodriguez, Torsten Schaub, and Anne Siegel. Learning Boolean logic models of signaling networks with ASP. Theor. Comput. Sci., 599:79-101, 2015. URL: https://doi.org/10.1016/j.tcs.2014.06.022.
  47. Santiago Videla, Julio Saez-Rodriguez, Carito Guziolowski, and Anne Siegel. caspo: a toolbox for automated reasoning on the response of logical signaling networks families. Bioinform., 33(6):947-950, 2017. URL: https://doi.org/10.1093/bioinformatics/btw738.
  48. Rui-Sheng Wang, Assieh Saadatpour, and Reka Albert. Boolean modeling in systems biology: an overview of methodology and applications. Phys. Biol., 9(5):055001, 2012. URL: https://doi.org/10.1088/1478-3975/9/5/055001.
  49. Ayako Yachie-Kinoshita, Kento Onishi, Joel Ostblom, Matthew A Langley, Eszter Posfai, Janet Rossant, and Peter W Zandstra. Modeling signaling-dependent pluripotency with Boolean logic to predict cell fate transitions. Mol. Syst. Biol., 14(1):e7952, 2018. URL: https://doi.org/10.15252/msb.20177952.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact