Data_Sheet_3_Estimating Attractor Reachability in Asynchronous Logical Models.PDF

Logical models are well-suited to capture salient dynamical properties of regulatory networks. For networks controlling cell fate decisions, cell fates are associated with model attractors (stable states or cyclic attractors) whose identification and reachability properties are particularly relevant. While synchronous updates assume unlikely instantaneous or identical rates associated with component changes, the consideration of asynchronous updates is more realistic but, for large models, may hinder the analysis of the resulting non-deterministic concurrent dynamics. This complexity hampers the study of asymptotical behaviors, and most existing approaches suffer from efficiency bottlenecks, being generally unable to handle cyclical attractors and quantify attractor reachability. Here, we propose two algorithms providing probability estimates of attractor reachability in asynchronous dynamics. The first algorithm, named Firefront, exhaustively explores the state space from an initial state, and provides quasi-exact evaluations of the reachability probabilities of model attractors. The algorithm progresses in breadth, propagating the probabilities of each encountered state to its successors. Second, Avatar is an adapted Monte Carlo approach, better suited for models with large and intertwined transient and terminal cycles. Avatar iteratively explores the state space by randomly selecting trajectories and by using these random walks to estimate the likelihood of reaching an attractor. Unlike Monte Carlo simulations, Avatar is equipped to avoid getting trapped in transient cycles and to identify cyclic attractors. Firefront and Avatar are validated and compared to related methods, using as test cases logical models of synthetic and biological networks. Both algorithms are implemented as new functionalities of GINsim 3.0, a well-established software tool for logical modeling, providing executable GUI, Java API, and scripting facilities.

逻辑模型（Logical models）非常适于捕捉调控网络的核心动态特性。针对调控细胞命运决定的网络而言，细胞命运与模型的吸引子（attractors，包括稳定状态或循环吸引子）紧密相关，而吸引子的识别与可达性特性尤为关键。尽管同步更新假设组件变化以瞬时或统一速率发生，这一假设与实际情况不符；异步更新的考量更为贴合现实，但对于大规模模型而言，其引发的非确定性并发动态分析却存在显著阻碍。这类复杂性制约了渐近行为的研究，现有多数方法均存在效率瓶颈，通常无法处理循环吸引子，也难以量化吸引子的可达性。本研究提出两种算法，可对异步动态下的吸引子可达性进行概率估计。第一种算法名为Firefront，它从初始状态出发穷尽式遍历状态空间，可对模型吸引子的可达性概率提供准精确评估。该算法以广度优先的方式推进，将每个已访问状态的概率传递至其后继状态。第二种算法Avatar则是改进型蒙特卡洛（Monte Carlo）方法，更适配存在大规模且相互交织的暂态循环与终端循环的模型。Avatar通过随机选取轨迹、并利用这些随机游走过程来估计到达吸引子的概率，以此迭代遍历状态空间。与传统蒙特卡洛模拟不同，Avatar可避免陷入暂态循环，并能够识别循环吸引子。本研究以人工合成与生物网络的逻辑模型作为测试用例，对Firefront与Avatar进行了验证，并与相关方法开展了对比。两种算法均作为GINsim 3.0的新增功能得以实现——GINsim 3.0是一款成熟的逻辑建模仿真软件，提供可执行图形用户界面（GUI）、Java应用程序编程接口（API）以及脚本编写工具。