A reduction method for Boolean network models proven to conserve attractors

Boolean models, wherein each component is characterized with a binary (ON or OFF) variable, have been widely employed for dynamic modeling of biological regulatory networks. However, the exponential dependence of the size of the state space of these models on the number of nodes in the network can be a daunting prospect for attractor analysis of large-scale systems. We have previously proposed a network reduction technique for Boolean models and demonstrated its applicability on two biological systems, namely, the abscisic acid signal transduction network and the T-LGL leukemia survival signaling network. In this paper, we provide a rigorous mathematical proof that this method not only conserves the fixed points of a Boolean network, but also conserves the complex attractors of general asynchronous Boolean models wherein at each time step a randomly selected node is updated. This method thus allows one to infer the long-term dynamic properties of a large-scale system from those of the corresponding reduced model.