Research Article: ASP-based method for the enumeration of attractors in non-deterministic synchronous and asynchronous multi-valued networks

Date Published: August 15, 2017

Publisher: BioMed Central

Author(s): Emna Ben Abdallah, Maxime Folschette, Olivier Roux, Morgan Magnin.

http://doi.org/10.1186/s13015-017-0111-2

Abstract

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.

Partial Text

In the last decades, the emergence of a wide range of new technologies have made it possible to produce a massive amount of biological data (genomics, proteomics…). This leads to considerable developments in systems biology which takes profit from this data. In order to understand the nature of a cellular function or more broadly a living biological system (healthy or diseased), it is indeed essential to study not only the individual properties of cellular components, but also their interactions. The behavior and functionalities of the cells emerge from such networks of interactions.

In this section, we briefly recapitulate the basic elements of ASP [18], a declarative language that proved efficient to address highly computational problems. An answer set program is a finite set of rules of the form:1documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}$$begin{aligned} a_{0} leftarrow a_{1}, ldots , a_{m}, not a_{m+1}, ldots , not a_{n}. end{aligned}$$end{document}a0←a1,…,am,notam+1,…,notan.where documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}$$n ge m ge 0$$end{document}n≥m≥0, documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}$$a_{0}$$end{document}a0 is an atom or documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}$$bot $$end{document}⊥, all documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}$$a_{1}, ldots ,a_{n}$$end{document}a1,…,an are atoms, and the symbol “not” denotes negation as failure. The intuitive reading of such a rule is that whenever documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}$$a_{1}, ldots , a_{m}$$end{document}a1,…,am are known to be true and there is no evidence for any of the negated atoms documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}$$a_{m+1}, ldots , a_{n}$$end{document}am+1,…,an to be true, then documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}$$a_{0}$$end{document}a0 has to be true as well. An atom or a negated atom is also called a literal.

The first aspect of our work is the enumeration of a special type of trap domains: fixed points (also called stable states or steady states) which are composed of only one global state (see Definition 9). They can be studied separately from attractors because their enumeration follows a different pattern which is more specific to this problem. A previous version of this work using another framework (process hitting) is presented in [19]. Although the main idea is preserved, the work we present here is different because we are interested in the more expressive AN framework in which the transitions have a different form.

In the previous section we gave a method to enumerate all fixed points of a given model. In a sense, a fixed point can be considered as an attractor: it cannot be escaped and its size (documentclass[12pt]{minimal}
usepackage{amsmath}
usepackage{wasysym}
usepackage{amsfonts}
usepackage{amssymb}
usepackage{amsbsy}
usepackage{mathrsfs}
usepackage{upgreek}
setlength{oddsidemargin}{-69pt}
begin{document}$$n=1$$end{document}n=1) makes it trivially minimal. However, attractors in the general case are made of several states. In the rest of this paper, we exclude one-state attractors (tackled in the last section “Fixed points enumeration”). We focus on attractors composed with several-states (following Definition 11) and we describe how to obtain some or all the attractors of a given length in a model. Obtaining all attractors of any length can be theoretically tackled by gradually increasing the considered length.

In this section, we exhibit several experiments conducted on biological networks. We first detail the results of our programs on the AN model of Fig. 1. Then, we sum up the results of benchmarks performed on other models up to 100 components. In general, the time performances are good and the overall results confirm the applicability ASP for the verification of formal properties or the enumeration of special constructs on biological systems.

In this paper, we presented a new logical approach to efficiently compute the list of all fixed points and attractors in biological regulatory networks. We formalized our approach using the AN framework, which is bisimilar to many logical networks [41]. All results given here can thus be applied to the widespread Thomas’ modeling [42] in the asynchronous scheme and to the Kauffman modeling in the synchronous scheme [43]. In addition, this framework can encompass any update rules, such as the ones represented in [44, 45].

 

Source:

http://doi.org/10.1186/s13015-017-0111-2

 

Leave a Reply

Your email address will not be published.