Limits...
Steady state analysis of Boolean molecular network models via model reduction and computational algebra.

Veliz-Cuba A, Aguilar B, Hinkelmann F, Laubenbacher R - BMC Bioinformatics (2014)

Bottom Line: The first is a graph theoretic reduction of the wiring diagram of the network, while preserving all information about steady states.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 problem for large Boolean networks with high average connectivity remains an open problem.

View Article: PubMed Central - HTML - PubMed

Affiliation: Department of Mathematics, University of Houston, 651 PGH Building, Houston TX, USA. alanavc@math.uh.edu.

ABSTRACT

Background: 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.

Results: 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.

Conclusions: 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.

Show MeSH

Related in: MedlinePlus

Flow chart of steady state computation. Main steps in our method highlighting the intermediate systems. S denotes the set of steady states of a given network; f is an arbitrary Boolean network, g is an AND-NOT network (in possibly more variables), h is a reduced AND-NOT network, p is the polynomial representation of h.
© Copyright Policy - open-access
Related In: Results  -  Collection

License 1 - License 2
getmorefigures.php?uid=PMC4230806&req=5

Figure 1: Flow chart of steady state computation. Main steps in our method highlighting the intermediate systems. S denotes the set of steady states of a given network; f is an arbitrary Boolean network, g is an AND-NOT network (in possibly more variables), h is a reduced AND-NOT network, p is the polynomial representation of h.

Mentions: The method we propose for steady state analysis is a combination of network reduction/transformation and computational algebra (see Figure 1). The reduction technique we use is based on results in [42,43]. In [42] it was shown that any Boolean network can be “transformed” into an AND-NOT network, namely a network whose Boolean functions are all of the form y1∧y2∧…, where yi∈{xi,¬xi}. The AND-NOT network has the property that its steady states are in one-to-one correspondence with the steady states of the original network. Furthermore, the one-to-one correspondence between steady states is algorithmic. In [43], the authors proposed a method to reduce an AND-NOT network to another, smaller AND-NOT network in polynomial time, in such a way that the steady states of the original and the reduced network are in one-to-one correspondence, in a constructive way. This reduction algorithm looks for motifs (e.g. feed-forward loops) in the wiring diagram and removes nodes in such motifs; the reduction stops when there are no more motifs to be reduced (attempting to do further reductions would destroy the 1-1 correspondence of steady states). Once the reduced network is constructed, one can compute its steady states by converting the Boolean functions into polynomial functions and then solving a system of polynomial equations, as explained above. The computational algebra technique is based on [29,30]. The idea is that by computing a Gröbner basis (a special set of polynomials with the same roots as the original equations), it is possible to find the roots of the system of polynomial equations using a generalized version of Gaussian elimination.


Steady state analysis of Boolean molecular network models via model reduction and computational algebra.

Veliz-Cuba A, Aguilar B, Hinkelmann F, Laubenbacher R - BMC Bioinformatics (2014)

Flow chart of steady state computation. Main steps in our method highlighting the intermediate systems. S denotes the set of steady states of a given network; f is an arbitrary Boolean network, g is an AND-NOT network (in possibly more variables), h is a reduced AND-NOT network, p is the polynomial representation of h.
© Copyright Policy - open-access
Related In: Results  -  Collection

License 1 - License 2
Show All Figures
getmorefigures.php?uid=PMC4230806&req=5

Figure 1: Flow chart of steady state computation. Main steps in our method highlighting the intermediate systems. S denotes the set of steady states of a given network; f is an arbitrary Boolean network, g is an AND-NOT network (in possibly more variables), h is a reduced AND-NOT network, p is the polynomial representation of h.
Mentions: The method we propose for steady state analysis is a combination of network reduction/transformation and computational algebra (see Figure 1). The reduction technique we use is based on results in [42,43]. In [42] it was shown that any Boolean network can be “transformed” into an AND-NOT network, namely a network whose Boolean functions are all of the form y1∧y2∧…, where yi∈{xi,¬xi}. The AND-NOT network has the property that its steady states are in one-to-one correspondence with the steady states of the original network. Furthermore, the one-to-one correspondence between steady states is algorithmic. In [43], the authors proposed a method to reduce an AND-NOT network to another, smaller AND-NOT network in polynomial time, in such a way that the steady states of the original and the reduced network are in one-to-one correspondence, in a constructive way. This reduction algorithm looks for motifs (e.g. feed-forward loops) in the wiring diagram and removes nodes in such motifs; the reduction stops when there are no more motifs to be reduced (attempting to do further reductions would destroy the 1-1 correspondence of steady states). Once the reduced network is constructed, one can compute its steady states by converting the Boolean functions into polynomial functions and then solving a system of polynomial equations, as explained above. The computational algebra technique is based on [29,30]. The idea is that by computing a Gröbner basis (a special set of polynomials with the same roots as the original equations), it is possible to find the roots of the system of polynomial equations using a generalized version of Gaussian elimination.

Bottom Line: The first is a graph theoretic reduction of the wiring diagram of the network, while preserving all information about steady states.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 problem for large Boolean networks with high average connectivity remains an open problem.

View Article: PubMed Central - HTML - PubMed

Affiliation: Department of Mathematics, University of Houston, 651 PGH Building, Houston TX, USA. alanavc@math.uh.edu.

ABSTRACT

Background: 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.

Results: 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.

Conclusions: 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.

Show MeSH
Related in: MedlinePlus