Ben Abdallah Emna, Folschette Maxime, Roux Olivier, Magnin Morgan
École Centrale de Nantes, LS2N UMR CNRS 6004, 1 rue de la Noë, 44321 Nantes, France.
Université de Nantes, LS2N UMR CNRS 6004, 1 rue de la Noë, 44321 Nantes, France.
Algorithms Mol Biol. 2017 Aug 15;12:20. doi: 10.1186/s13015-017-0111-2. eCollection 2017.
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.
本文探讨了在生物调控网络中寻找吸引子的问题。我们在此关注使用自动机网络（AN）建模的非确定性同步和异步多值网络。自动机网络是一种通用且适用的形式体系，用于研究不同组件（基因、蛋白质等）之间的复杂相互作用。吸引子是一个最小陷阱域，即状态转移图中无法逃脱的一部分。此类结构是动力学的终端组件，形式为稳态（单元素集）或循环的复杂组合（非单元素集）。研究疾病或突变对生物体的影响需要在模型中找到吸引子，以了解长期行为。
我们提出了一种基于回答集编程（ASP）的计算逻辑方法来识别所有吸引子。该方法无需进行任何网络简化，可应用于任何动态语义。在本文中，我们介绍了两种最广泛使用的非确定性语义：异步和同步更新模式。逻辑方法通过对网络状态进行完全枚举来找到吸引子，而无需构建整个状态转移图。我们进行了广泛的计算实验，结果表明该方法性能良好，符合文献中的预期理论结果。
我们方法的独特之处在于，借助回答集编程对所有可能的（一组）状态进行详尽枚举，以验证吸引子的属性。我们的方法以两种不同方案（异步和同步）应用于非确定性语义。通过将我们的方法应用于各种规模的生物学示例，并将结果与一些现有方法进行比较，展示了我们方法的优点。结果表明，我们的方法能够在台式计算机上，针对一个大型模型（100个组件），详尽枚举直至给定大小（20个状态）的所有现有吸引子。这个大小仅受内存和计算时间的限制。
