A parallel attractor-finding algorithm based on Boolean satisfiability for genetic regulatory networks.
A parallel attractor-finding algorithm based on Boolean satisfiability for genetic regulatory networks.
复制标题
一种基于布尔可满足性的遗传调控网络并行吸引子寻找算法
DOI：
10.1371/journal.pone.0094258
复制
发表时间：
2014
期刊：
影响因子：
3.7
通讯作者：
Sun M
中科院分区：
文献类型：
--
作者：
Guo W;Yang G;Wu W;He L;Sun M
在生物系统中，动态分析方法在近十年来得到了越来越多的关注。布尔网络是最常见的基因调控网络模型。遗传调控网络中激活和抑制的相互作用被建模为布尔网络的一组函数，而布尔网络中的状态转换反映了遗传调控网络的动态特性。状态转移分析的一个难题是寻找吸引子。本文将遗传调控网络建模为布尔网络，并提出了一种解决吸引子寻找问题的求解算法。在该算法中，我们将布尔网络根据其梯度划分为由强连通分量组成的若干块，并将块之间的连接定义为决策节点。基于在决策节点上计算的解，利用可满足性求解算法，确定了每个块的状态转移图中的吸引子。该算法在多种遗传调控网络上进行了基准测试。与现有算法相比，该算法在小型测试用例上的性能与现有算法相当，而在更大、更复杂的测试用例上的性能优于现有算法，这恰好是现代基因调控网络的发展趋势。此外，现有的基于满意度的算法由于其固有的算法设计而无法并行化，而本文提出的算法在并行计算架构上具有良好的可扩展性。
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.
登录
查看更多内容
影响因子：
3
作者：
Krumsiek J;Pölsterl S;Wittmann DM;Theis FJ
通讯作者：
Theis FJ
影响因子：
0.8
作者：
Clarke, E;Biere, A;Zhu, Y
通讯作者：
Zhu, Y
影响因子：
3
作者：
Karl S;Dandekar T
通讯作者：
Dandekar T
影响因子：
4.8
作者：
Chaos, Alvaro;Aldana, Max;Alvarez-Buylla, Elena R.
通讯作者：
Alvarez-Buylla, Elena R.
DOI：
10.1007/978-3-540-24605-3_37
发表时间：
2004-01-01
期刊：
THEORY AND APPLICATIONS OF SATISFIABILITY TESTING
影响因子：
--
作者：
Eén, N;Sörensson, N
通讯作者：
Sörensson, N