Strong modules and asynchronous attractors of Boolean networks
This work offers a theoretical foundation for attractor detection algorithms in Boolean networks, which is relevant for systems biology and computational modeling.
The paper provides an algebraic basis for decomposing asynchronous Boolean networks into strong modules, proving that attractors can be described as a dependent sum of attractors of controlled modules. It shows that attractor representation can be computed in polynomial time under conditions of small modules and sparse or small-circuit functions.
We consider Boolean networks with interaction graphs partitioned into strongly connected components, which we call strong modules. This type of network decomposition has been considered in the literature, primarily from the perspective of attractor detection algorithms. In this paper, we aim to provide an algebraic basis for this line of research in the case of asynchronous Boolean networks. We prove that the asynchronous attractors of a network can be described as a dependent sum construction: as products of attractors of its controlled strong modules. We then show that a representation of all attractors can be computed in polynomial time under two conditions: the strong modules are small, and either the network is sparse or its defining functions have small size circuits (in particular when they are nested canalizing). We illustrate these results on a published Boolean model.