Department of Mathematics, University of Houston, 651 PGH Building, Houston TX, USA.
BMC Bioinformatics. 2014 Jun 26;15:221. doi: 10.1186/1471-2105-15-221.
A key problem in the analysis of mathematical models of molecular networks is the determination of their steady states. The present paper addresses this problem for Boolean network models, an increasingly popular modeling paradigm for networks lacking detailed kinetic information. For small models, the problem can be solved by exhaustive enumeration of all state transitions. But for larger models this is not feasible, since the size of the phase space grows exponentially with the dimension of the network. The dimension of published models is growing to over 100, so that efficient methods for steady state determination are essential. Several methods have been proposed for large networks, some of them heuristic. While these methods represent a substantial improvement in scalability over exhaustive enumeration, the problem for large networks is still unsolved in general.
This paper presents an algorithm that consists of two main parts. The first is a graph theoretic reduction of the wiring diagram of the network, while preserving all information about steady states. The second part formulates the determination of all steady states of a Boolean network as a problem of finding all solutions to a system of polynomial equations over the finite number system with two elements. This problem can be solved with existing computer algebra software. This algorithm compares favorably with several existing algorithms for steady state determination. One advantage is that it is not heuristic or reliant on sampling, but rather determines algorithmically and exactly all steady states of a Boolean network. The code for the algorithm, as well as the test suite of benchmark networks, is available upon request from the corresponding author.
The algorithm presented in this paper reliably determines all steady states of sparse Boolean networks with up to 1000 nodes. The algorithm is effective at analyzing virtually all published models even those of moderate connectivity. The problem for large Boolean networks with high average connectivity remains an open problem.
在分析分子网络的数学模型时，一个关键问题是确定其稳态。本文针对布尔网络模型（一种缺乏详细动力学信息的网络的流行建模范例）解决了这个问题。对于小模型，可以通过对所有状态转换进行穷举枚举来解决问题。但是对于较大的模型，这是不可行的，因为随着网络维度的增加，相空间的大小呈指数增长。已发表模型的维度已增长到 100 以上，因此，有效的稳态确定方法至关重要。已经提出了几种用于大型网络的方法，其中一些是启发式的。虽然这些方法在可扩展性方面相对于穷举枚举有了很大的改进，但对于大型网络，这个问题通常仍然没有得到解决。
本文提出了一种算法，该算法主要由两部分组成。第一部分是网络布线图的图论简化，同时保留了所有关于稳态的信息。第二部分将确定布尔网络的所有稳态表示为寻找具有两个元素的有限数系统中系统的多项式方程的所有解的问题。这个问题可以使用现有的计算机代数软件来解决。该算法与现有的几种稳态确定算法相比具有优势。一个优点是它不是启发式的，也不依赖于采样，而是通过算法精确地确定布尔网络的所有稳态。算法的代码以及基准网络的测试套件可根据要求从相应的作者处获得。
本文提出的算法可靠地确定了具有多达 1000 个节点的稀疏布尔网络的所有稳态。该算法可有效地分析几乎所有已发布的模型，即使是那些具有中等连接性的模型也是如此。具有高平均连接性的大型布尔网络的问题仍然是一个未解决的问题。
