ASP-based method for the enumeration of attractors in non-deterministic synchronous and asynchronous multi-valued networks
Abstract Background 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 intera...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
BMC
2017-08-01
|
| Series: | Algorithms for Molecular Biology |
| Subjects: | |
| Online Access: | http://link.springer.com/article/10.1186/s13015-017-0111-2 |
| _version_ | 1830487426909339648 |
|---|---|
| author | Emna Ben Abdallah Maxime Folschette Olivier Roux Morgan Magnin |
| author_facet | Emna Ben Abdallah Maxime Folschette Olivier Roux Morgan Magnin |
| author_sort | Emna Ben Abdallah |
| collection | DOAJ |
| description | Abstract Background 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. Results 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. Conclusion 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. |
| first_indexed | 2024-12-21T19:00:07Z |
| format | Article |
| id | doaj.art-f24bd07b1dae426cbb2da3fab608bb04 |
| institution | Directory Open Access Journal |
| issn | 1748-7188 |
| language | English |
| last_indexed | 2024-12-21T19:00:07Z |
| publishDate | 2017-08-01 |
| publisher | BMC |
| record_format | Article |
| series | Algorithms for Molecular Biology |
| spelling | doaj.art-f24bd07b1dae426cbb2da3fab608bb042022-12-21T18:53:30ZengBMCAlgorithms for Molecular Biology1748-71882017-08-0112112310.1186/s13015-017-0111-2ASP-based method for the enumeration of attractors in non-deterministic synchronous and asynchronous multi-valued networksEmna Ben Abdallah0Maxime Folschette1Olivier Roux2Morgan Magnin3École Centrale de Nantes, LS2N UMR CNRS 6004Université de Nantes, LS2N UMR CNRS 6004École Centrale de Nantes, LS2N UMR CNRS 6004École Centrale de Nantes, LS2N UMR CNRS 6004Abstract Background 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. Results 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. Conclusion 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.http://link.springer.com/article/10.1186/s13015-017-0111-2Biological regulatory networkMultiple-valued networksAttractorsSteady statesCyclesAnswer set programming |
| spellingShingle | Emna Ben Abdallah Maxime Folschette Olivier Roux Morgan Magnin ASP-based method for the enumeration of attractors in non-deterministic synchronous and asynchronous multi-valued networks Algorithms for Molecular Biology Biological regulatory network Multiple-valued networks Attractors Steady states Cycles Answer set programming |
| title | ASP-based method for the enumeration of attractors in non-deterministic synchronous and asynchronous multi-valued networks |
| title_full | ASP-based method for the enumeration of attractors in non-deterministic synchronous and asynchronous multi-valued networks |
| title_fullStr | ASP-based method for the enumeration of attractors in non-deterministic synchronous and asynchronous multi-valued networks |
| title_full_unstemmed | ASP-based method for the enumeration of attractors in non-deterministic synchronous and asynchronous multi-valued networks |
| title_short | ASP-based method for the enumeration of attractors in non-deterministic synchronous and asynchronous multi-valued networks |
| title_sort | asp based method for the enumeration of attractors in non deterministic synchronous and asynchronous multi valued networks |
| topic | Biological regulatory network Multiple-valued networks Attractors Steady states Cycles Answer set programming |
| url | http://link.springer.com/article/10.1186/s13015-017-0111-2 |
| work_keys_str_mv | AT emnabenabdallah aspbasedmethodfortheenumerationofattractorsinnondeterministicsynchronousandasynchronousmultivaluednetworks AT maximefolschette aspbasedmethodfortheenumerationofattractorsinnondeterministicsynchronousandasynchronousmultivaluednetworks AT olivierroux aspbasedmethodfortheenumerationofattractorsinnondeterministicsynchronousandasynchronousmultivaluednetworks AT morganmagnin aspbasedmethodfortheenumerationofattractorsinnondeterministicsynchronousandasynchronousmultivaluednetworks |