Controllability of Conjunctive Boolean Networks With Application to Gene Regulation

Zuguang Gao, Xudong Chen, Tamer Basar

This paper, titled "Controllability of Conjunctive Boolean Networks with Application to Gene Regulation," provides a rigorous mathematical framework for "steering" simplified biological models. Authors Zuguang Gao, Xudong Chen, and Tamer Başar bridge the gap between graph theory and systems biology to determine exactly how many—and which—genes we need to control to force a biological system into a desired state.

TL;DR

The researchers establish the necessary and sufficient conditions to control Conjunctive Boolean Networks (CBNs), a class of models used to simulate gene regulation. By using a graphical approach, they provide explicit algorithms to steer these systems from any initial state into any desired periodic cycle or specific final configuration.

What Problem Does This Paper Address?

In systems biology, modeling the "on/off" nature of gene expression is often done using Boolean Networks (BNs). While ordinary differential equations (ODEs) provide high detail, they are computationally expensive and often lack explicit solutions for large networks. BNs simplify this: a gene is either expressed (1) or not (0).

A specific subset, Conjunctive Boolean Networks (CBNs), uses only logic "AND" operations. In a CBN, a gene turns on only if all its regulators were on in the previous time step. While we understand how these systems behave naturally—they eventually settle into "periodic orbits" (repeating cycles)—we haven't had a clear roadmap for controllability.

The authors tackle two specific questions:

  1. Orbit-controllability: How can we force the system into a specific repeating cycle?
  2. State-controllability: How can we force the system to reach one specific, fixed state?

Methods

The authors move away from traditional algebraic methods (like semi-tensor products) in favor of a graphical approach. They represent the network as a "dependency graph" where nodes are genes and edges are regulatory interactions.

Key methodological innovations include:

  • The Derived Graph ($D'$): To analyze control, the authors create a modified graph where the "natural" incoming edges to control nodes are deleted (since an external controller now dictates their value).
  • Graph Decomposition: For orbit-controllability, they decompose strongly connected graphs into "irreducible components" to understand the underlying "loop number" of the system.
  • Necessary and Sufficient Conditions: They prove that for a system to be controllable, the derived graph must be acyclic (containing no cycles). This essentially means the control nodes must "break" all natural feedback loops in the system.
  • Control Algorithms: They provide two explicit algorithms (Algorithm 1 for orbits, Algorithm 2 for states) that dictate exactly what values (0 or 1) to feed the control nodes at each time step to reach the target.

Datasets

Not discussed in the paper. As a theoretical mathematics and control theory paper, the authors use illustrative "toy" graphs and simulated dependency structures rather than experimental biological datasets.

Key Insights and Ideas

  • Breaking the Loops: The fundamental insight is that cycles are the enemy of controllability. To steer a CBN, your chosen control nodes must be positioned such that they interrupt every existing cycle in the dependency graph.
  • Orbit vs. State: The paper highlights that state-controllability is a much "stronger" (harder to achieve) requirement than orbit-controllability. To reach a specific state, not only must the graph be acyclic, but every node in the network must be uniquely reachable from a control node in a way that doesn't "clash" with other nodes.
  • The "Feedback Vertex Set" Connection: The authors identify that finding the minimum number of control nodes is equivalent to the "Feedback Vertex Set" problem in computer science—a known NP-hard problem. This connects gene regulation directly to fundamental complexity theory.

Key Results

  • Theorem 1 (Orbit Control): A set of nodes can control the system's orbit if and only if removing their incoming edges makes the graph acyclic.
  • Theorem 2 (State Control): For state control, the graph must be acyclic AND every node $v$ must have at least one control node $u$ that can reach it uniquely at some time step $k$ without affecting other nodes in a conflicting way.
  • Efficiency: The proposed control laws are fast. Steering a system to an orbit takes at most $n + p^* - 1$ steps (where $n$ is the number of genes and $p^*$ is the loop number), while steering to a state takes time proportional to the longest path in the derived graph.

Limitations and Future Work

  • Strong Connectivity Assumption: Much of the orbit-controllability analysis assumes the dependency graph is "strongly connected" (every node can reach every other node). While the authors mention recent progress on "weakly connected" graphs, a universal theory for all graph types is still in development.
  • Minimal Control Sets: While the paper tells you if a set of nodes works, it doesn't provide an efficient way to find the smallest possible set of nodes to control a massive network (due to the NP-hard nature of the problem).
  • Beyond "AND" Logic: The results are specific to conjunctive (AND) logic. Real biological systems often involve "OR" or "NOT" logic, which would require more complex "Monotonic" or general Boolean analysis.
  • Future Directions: The authors plan to develop algorithms to find minimal controlling sets and explore the tradeoff between the number of control nodes and the time required to reach the target state.

Summary updated

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.
BibTeX
@article{gao2018controllability,
  author = {Zuguang Gao and Xudong Chen and Tamer Basar},
  title = {{Controllability of Conjunctive Boolean Networks With Application to Gene Regulation}},
  journal = {IEEE Trans. Control. Netw. Syst.},
  year = {2018},
  doi = {10.1109/tcns.2017.2746345},
}

Loading related content...

Figure