Controllability and observability for Boolean networks and their applications to biological pathway analysis

Driving Boolean networks to desired states and determining the optimal measurable states are of paramount significance toward our ultimate goals of controlling and observing the progression of complex networks. Despite recent computational development of controllability and observability of general complex networks, there is still a lack of bridging the mathematical condition on controllability and observability to real Boolean operations in a network. Further, no realtime control strategies or sensor design strategies have been proposed to Boolean networks.

In this study, we have used semi-tensor product to represent Boolean functions in a network and explore controllability and observability of a Boolean network. Currently, there exist several direct mathematical results using semi-tensor product to analyze the controllability and observability properties, these results are deeply involved in large computational complexity and advanced mathematical explanation. Especially for models of biological systems, there are enormous nodes in its corresponding Boolean network, and the amount of computation will grow exponentially. More crucially, it is difficult and inefficient for biologists to assess the nature of biological systems. In order to reduce the computational burden, we have developed efficient approaches to determine system controllability and observability, which can be extended to more useful results, such as feedback control design and sensor selection.

We determined the necessary and sufficient condition for a controllable Boolean network and mapped this requirement in transition matrix to real Boolean functions and structure property of a network. Based on our results, we also developed an efficient tool to assess controllability of an arbitrary Boolean network and to determine all reachable and non-reachable states. We further found six simplest forms of controllable 2-node Boolean networks and explore the consistency of transition matrices while extending these six forms to controllable networks with more nodes. We represented the integrated states of a Boolean network with graph and proposed control strategy using the graph approach. This led to the first state feedback control strategy to drive the network based on the status of all nodes in the network.

In terms of observability, the fundamental observable styles and the unobservable styles were first proposed for undirected graphs. Then, a tool integrated by the effective graphical way was provided to determine the observability for Boolean networks with arbitrary number of nodes and Boolean functions. Furthermore, we proposed an efficient way to assign the sensors to observe the entire states.

We have applied our results on both controllability and observability to P53 pathway analysis. Our results showed the same progression patterns as published experimental studies, which verified the effectiveness of our methods. All these results enable a more comprehensive understanding of the evolution of Boolean networks. Also, two user-friendly software packages for determination of controllability and observability are provided for non-engineering users to download. These tools can easily and quickly determine the controllability and observability and offer a guideline of control design and sensor allocation for Boolean biological systems.