Abstract
A Boolean network is a finite state discrete time dynamical system. At each step, each variable takes a value from a binary set. The value update rule for each variable is a local function which depends only on a selected subset of variables. Boolean networks have been used in modeling gene regulatory networks. We focus in this paper on a special class of Boolean networks, namely the conjunctive Boolean networks (CBNs), whose value update rule is comprised of only logic AND operations. It is known that any trajectory of a Boolean network will enter a periodic orbit. Periodic orbits of a CBN have been completely understood. In this paper, we investigate the orbit-controllability and state-controllability of a CBN: We ask the question of how one can steer a CBN to enter any periodic orbit or to reach any final state, from any initial state. We establish necessary and sufficient conditions for a CBN to be orbit-controllable and state-controllable. Furthermore, explicit control laws are presented along the analysis.
Introduction
In systems biology, modeling the "on/off" nature of gene expression is often achieved through Boolean Networks (BNs). While ordinary differential equations (ODEs) offer high detail, they are computationally intensive and frequently lack explicit solutions for large-scale networks. BNs simplify these complex interactions: a gene is either expressed (1) or not (0).
This paper focuses on Conjunctive Boolean Networks (CBNs), which utilize only logic "AND" operations. In a CBN, a gene activates only if all its regulators were active in the preceding time step. While the natural behavior of these systems—eventually settling into repeating cycles known as "periodic orbits"—is well-understood, a clear framework for their controllability has been missing. The authors, Zuguang Gao, Xudong Chen, and Tamer Başar, address this gap by establishing the necessary and sufficient conditions to steer CBNs from any initial state into a desired periodic orbit or a specific final state.
Methodology: A Graphical Approach
The authors depart from traditional algebraic methods, such as semi-tensor products, in favor of a more intuitive graphical approach. They represent the network as a "dependency graph" where nodes represent genes and directed edges represent regulatory interactions.
Key methodological innovations include:
- The Derived Graph ($D'$): To analyze control, a modified graph is created where natural incoming edges to control nodes are removed, as an external controller now dictates their values.
- Graph Decomposition: For orbit-controllability, strongly connected graphs are decomposed into "irreducible components" to determine the system's underlying "loop number."
- Acyclicity as a Requirement: The researchers prove that for a system to be controllable, the derived graph must be acyclic. This implies that control nodes must effectively "break" all natural feedback loops within the system.
Key Results: Orbit and State Controllability
The paper establishes two primary theorems regarding controllability:
- Orbit-Controllability: A set of nodes can control the system's orbit if and only if removing their incoming edges renders the dependency graph acyclic.
- State-Controllability: This is a more stringent requirement. Beyond acyclicity, every node must be uniquely reachable from a control node at some time step without conflicting with other nodes.
The proposed control laws are highly efficient. Steering a system to a specific orbit takes at most $n + p^* - 1$ steps (where $n$ is the number of genes and $p^*$ is the loop number), while reaching a specific state takes time proportional to the longest path in the derived graph.
Discussion and Future Directions
While the paper provides a rigorous foundation, several challenges remain. The current analysis of orbit-controllability largely assumes "strongly connected" graphs. Furthermore, identifying the minimum number of control nodes is equivalent to the "Feedback Vertex Set" problem, which is known to be NP-hard.
Future research will focus on developing efficient algorithms for finding minimal controlling sets and extending these results beyond "AND" logic to include "OR" and "NOT" operations, which are also prevalent in biological systems.
Note: This paper is a theoretical study; experimental biological datasets were not utilized.
Summary updated