ASP-based method for the enumeration of attractors in non-deterministic synchronous and asynchronous multi-valued networks
Tóm tắt
This paper addresses the problem of finding attractors in biological regulatory networks. We focus here on non-deterministic synchronous and asynchronous multi-valued networks, modeled using automata networks (AN). AN is a general and well-suited formalism to study complex interactions between different components (genes, proteins,...). An attractor is a minimal trap domain, that is, a part of the state-transition graph that cannot be escaped. Such structures are terminal components of the dynamics and take the form of steady states (singleton) or complex compositions of cycles (non-singleton). Studying the effect of a disease or a mutation on an organism requires finding the attractors in the model to understand the long-term behaviors. We present a computational logical method based on answer set programming (ASP) to identify all attractors. Performed without any network reduction, the method can be applied on any dynamical semantics. In this paper, we present the two most widespread non-deterministic semantics: the asynchronous and the synchronous updating modes. The logical approach goes through a complete enumeration of the states of the network in order to find the attractors without the necessity to construct the whole state-transition graph. We realize extensive computational experiments which show good performance and fit the expected theoretical results in the literature. The originality of our approach lies on the exhaustive enumeration of all possible (sets of) states verifying the properties of an attractor thanks to the use of ASP. Our method is applied to non-deterministic semantics in two different schemes (asynchronous and synchronous). The merits of our methods are illustrated by applying them to biological examples of various sizes and comparing the results with some existing approaches. It turns out that our approach succeeds to exhaustively enumerate on a desktop computer, in a large model (100 components), all existing attractors up to a given size (20 states). This size is only limited by memory and computation time.
Tài liệu tham khảo
Wuensche A. Genomic regulation modeled as a network with basins of attraction. Pac Symp Biocomput. 1998;3:89–102.
Huang S, Eichler G, Bar-Yam Y, Ingber DE. Cell fates as high-dimensional attractor states of a complex gene regulatory network. Phys Rev Lett. 2005;94(12):128701.
González A, Chaouiya C, Thieffry D. Logical modelling of the role of the hh pathway in the patterning of the drosophila wing disc. Bioinformatics. 2008;24(16):234–40.
Albert R, Othmer HG. The topology of the regulatory interactions predicts the expression pattern of the segment polarity genes in Drosophila melanogaster. J Theor Biol. 2003;223(1):1–18.
Stuart A. Kaufmann. The origins of order: self-organization and selection in evolution. Oxford: Oxford University Press; 1993. p. 354.
Folschette M, Paulevé L, Magnin M, Roux O. Sufficient conditions for reachability in automata networks with priorities. Theor Comput Sci. 2015;608:66–83.
Paulevé L. Goal-oriented reduction of automata networks. In: International Conference on computational methods in systems biology. Lecture notes in bioinformatics, vol. 9859. Springer; 2016. p. 252–72.
Thomas R. Regulatory networks seen as asynchronous automata: a logical description. J Theor Biol. 1991;153(1):1–23.
Zhang S-Q, Hayashida M, Akutsu T, Ching W-K, Ng MK. Algorithms for finding small attractors in Boolean networks. EURASIP J Bioinform Syst Biol. 2007;2007(1):1–13.
Klemm K, Bornholdt S. Stable and unstable attractors in Boolean networks. Phys Rev E. 2005;72(5):055101.
Akutsu T, Kosub S, Melkman AA, Tamura T. Finding a periodic attractor of a Boolean network. IEEE/ACM Trans Comput Biol Bioinform. 2012;9(5):1410–21.
Somogyi R, Greller LD. The dynamics of molecular networks: applications to therapeutic discovery. Drug Discov Today. 2001;6(24):1267–77.
Irons DJ. Improving the efficiency of attractor cycle identification in Boolean networks. Phys D: Nonlinear Phenom. 2006;217(1):7–21.
Garg A, Mendoza L, Xenarios I, DeMicheli G. Modeling of multiple valued gene regulatory networks. In: 2007 29th Annual International Conference of the IEEE engineering in medicine and biology society. IEEE; 2007. p. 1398–404.
Zhao Z, Liu CW, Wang CY, Qian W. Bdd-based synthesis of reconfigurable single-electron transistor arrays. In: Proceedings of the 2014 IEEE/ACM International Conference on computer-aided design. IEEE Press; 2014. p. 47–54.
Dubrova E, Teslenko M. A SAT-based algorithm for finding attractors in synchronous Boolean networks. IEEE/ACM Trans Comput Biol Bioinform. 2011;8(5):1393–9.
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. Bioinformatics. 2041;481.
Baral C. Knowledge representation, reasoning and declarative problem solving. Cambridge: Cambridge University Press; 2003.
Ben Abdallah E, Folschette M, Roux O, Magnin M. Exhaustive analysis of dynamical properties of biological regulatory networks with answer set programming. In: 2015 IEEE International Conference on bioinformatics and biomedicine (BIBM). IEEE; 2015. p. 281–85.
Paulevé L, Chancellor C, Folschette M, Magnin M, Roux O. Analyzing large network dynamics with process hitting. Log Model Biol Syst. 2014:125–66.
Skodawessely T, Klemm K. Finding attractors in asynchronous Boolean dynamics. Adv Complex Syst. 2011;14(03):439–49.
Berntenis N, Ebeling M. Detection of attractors of large Boolean networks via exhaustive enumeration of appropriate subspaces of the state space. BMC Bioinform. 2013;14(1):1.
Calzone L, Fages F, Soliman S. Biocham: an environment for modeling biological systems and formalizing experimental knowledge. Bioinformatics. 2006;22(14):1805–7.
Klarner H, Bockmayr A, Siebert H. Computing maximal and minimal trap spaces of Boolean networks. Nat Comput. 2015;14(4):535–44.
de Espanés PM, Osses A, Rapaport I. Fixed-points in random Boolean networks: the impact of parallelism in the barabási-albert scale-free topology case. Biosystems. 2016;150:167–76.
Gelfond M, Lifschitz V. The stable model semantics for logic programming. In: ICLP/SLP; 1988. p. 1070–080.
Gebser M, Kaminski R, Kaufmann B, Ostrowski M, Schaub T, Wanko P. Theory solving made easy with Clingo 5. Wadern: Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik; 2016.
Dubrova E, Teslenko M. A SAT-based algorithm for computing attractors in synchronous Boolean networks; 2009. arXiv preprint arXiv:0901.4448.
Qu H, Yuan Q, Pang J, Mizera A. Improving bdd-based attractor detection for synchronous Boolean networks. In: Proceedings of the 7th Asia-Pacific Symposium on Internetware. ACM; 2015.
Hayashida M, Tamura T, Akutsu T, Zhang S-Q, Ching W-K. Algorithms and complexity analyses for control of singleton attractors in Boolean networks. EURASIP J Bioinform Syst Biol. 2008;2008(1):1.
Thieffry D, Thomas R. Dynamical behaviour of biological regulatory networks—ii. Immunity control in bacteriophage lambda. Bull Math Biol. 1995;57(2):277–97.
Simao E, Remy E, Thieffry D, Chaouiya C. Qualitative modelling of regulated metabolic pathways: application to the tryptophan biosynthesis in E. coli. Bioinformatics. 2005;21(suppl 2):190–6.
Davidich MI, Bornholdt S. Boolean network model predicts cell cycle sequence of fission yeast. PloS ONE. 2008;3(2):1672.
Fauré A, Naldi A, Chaouiya C, Thieffry D. Dynamical analysis of a generic Boolean model for the control of the mammalian cell cycle. Bioinformatics. 2006;22(14):124–31.
Klamt S, Saez-Rodriguez J, Lindquist JA, Simeoni L, Gilles ED. A methodology for the structural and functional analysis of signaling and regulatory networks. BMC Bioinform. 2006;7(1):1.
Mbodj A, Junion G, Brun C, Furlong EE, Thieffry D. Logical modelling of drosophila signalling pathways. Molecular BioSyst. 2013;9(9):2248–58.
Abou-Jaoudé W, Monteiro PT, Naldi A, Grandclaudon M, Soumelis V, Chaouiya C, Thieffry D. Model checking to assess t-helper cell plasticity. Front Bioeng Biotechnol. 2014;2.
Chaouiya C, Naldi A, Thieffry D. Logical modelling of gene regulatory networks with GINsim. Bact Mol Netw: Methods Protoc. 2012:463–79.
Paulevé L. Pint, a static analyzer for dynamics of automata networks. In: 14th International Conference on computational methods in systems biology (CMSB 2016); 2016.
Naldi A, Monteiro PT, Müssel C, Kestler HA, Thieffry D, Xenarios I, Saez-Rodriguez J, Helikar T, Chaouiya C, et al. Cooperative development of logical modelling standards and tools with colomoto. Bioinformatics. 2015;013.
Chatain T, Haar S, Jezequel L, Paulevé L, Schwoon S. Characterization of reachable attractors using petri net unfoldings. In: International Conference on computational methods in systems biology. Springer. p. 129–42.
Thomas R. Boolean formalization of genetic control circuits. J Theor Biol. 1973;42(3):563–85.
Kauffman SA. Metabolic stability and epigenesis in randomly constructed genetic nets. J Theor Biol. 1969;22(3):437–67.
Gershenson C. Updating schemes in random Boolean networks: do they really matter. In: Artificial life IX Proceedings of the Ninth International Conference on the simulation and synthesis of living systems. MIT Press; 2004. p. 238–43.
Noual M, Sené S. Synchronism versus asynchronism in monotonic Boolean automata networks. Nat Comput. 2017. doi:10.1007/s11047-016-9608-8.
Fippo-Fittime L, Roux O, Guziolowski C, Paulevé L. Identification of bifurcations in biological regulatory networks using answer-set programming. In: Constraint-based methods for bioinformatics Workshop; 2016.