Guo Wensheng, Yang Guowu, Wu Wei, He Lei, Sun Mingyu
School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu, Sichuan, China; Electrical Engineering Department, University of California Los Angeles, Los Angeles, California, United States of America.
School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu, Sichuan, China.
PLoS One. 2014 Apr 9;9(4):e94258. doi: 10.1371/journal.pone.0094258. eCollection 2014.
In biological systems, the dynamic analysis method has gained increasing attention in the past decade. The Boolean network is the most common model of a genetic regulatory network. The interactions of activation and inhibition in the genetic regulatory network are modeled as a set of functions of the Boolean network, while the state transitions in the Boolean network reflect the dynamic property of a genetic regulatory network. A difficult problem for state transition analysis is the finding of attractors. In this paper, we modeled the genetic regulatory network as a Boolean network and proposed a solving algorithm to tackle the attractor finding problem. In the proposed algorithm, we partitioned the Boolean network into several blocks consisting of the strongly connected components according to their gradients, and defined the connection between blocks as decision node. Based on the solutions calculated on the decision nodes and using a satisfiability solving algorithm, we identified the attractors in the state transition graph of each block. The proposed algorithm is benchmarked on a variety of genetic regulatory networks. Compared with existing algorithms, it achieved similar performance on small test cases, and outperformed it on larger and more complex ones, which happens to be the trend of the modern genetic regulatory network. Furthermore, while the existing satisfiability-based algorithms cannot be parallelized due to their inherent algorithm design, the proposed algorithm exhibits a good scalability on parallel computing architectures.
在生物系统中，动态分析方法在过去十年中受到了越来越多的关注。布尔网络是遗传调控网络最常见的模型。遗传调控网络中的激活和抑制相互作用被建模为布尔网络的一组函数，而布尔网络中的状态转换反映了遗传调控网络的动态特性。状态转换分析的一个难题是吸引子的寻找。在本文中，我们将遗传调控网络建模为布尔网络，并提出了一种求解算法来解决吸引子寻找问题。在所提出的算法中，我们根据梯度将布尔网络划分为由强连通分量组成的几个块，并将块之间的连接定义为决策节点。基于在决策节点上计算的解并使用可满足性求解算法，我们在每个块的状态转换图中识别出吸引子。所提出的算法在各种遗传调控网络上进行了基准测试。与现有算法相比，它在小型测试案例上表现出相似的性能，而在更大、更复杂的案例上则表现更优，这恰好是现代遗传调控网络的发展趋势。此外，虽然现有的基于可满足性的算法由于其固有的算法设计无法并行化，但所提出的算法在并行计算架构上表现出良好的可扩展性。
