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

Veliz-Cuba, Alan; Aguilar, Boris; Hinkelmann, Franziska; Laubenbacher, Reinhard C.

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

dc.contributor.author	Veliz-Cuba, Alan	en
dc.contributor.author	Aguilar, Boris	en
dc.contributor.author	Hinkelmann, Franziska	en
dc.contributor.author	Laubenbacher, Reinhard C.	en
dc.contributor.department	Computer Science	en
dc.date.accessioned	2014-07-23T15:06:22Z	en
dc.date.available	2014-07-23T15:06:22Z	en
dc.date.issued	2014-06-26	en
dc.date.updated	2014-07-23T15:06:22Z	en
dc.description.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.	en
dc.description.version	Published version	en
dc.format.mimetype	application/pdf	en
dc.identifier.citation	BMC Bioinformatics. 2014 Jun 26;15(1):221	en
dc.identifier.doi	https://doi.org/10.1186/1471-2105-15-221	en
dc.identifier.uri	http://hdl.handle.net/10919/49666	en
dc.language.iso	en	en
dc.rights	Creative Commons Attribution 4.0 International	en
dc.rights.holder	Alan Veliz-Cuba et al.; licensee BioMed Central Ltd.	en
dc.rights.uri	http://creativecommons.org/licenses/by/4.0/	en
dc.title	Steady state analysis of Boolean molecular network models via model reduction and computational algebra	en
dc.title.serial	BMC Bioinformatics	en
dc.type	Article - Refereed	en
dc.type.dcmitype	Text	en