Combinatorial Algorithms for Control of Biological Regulatory Networks
This work provides theoretical foundations and efficient algorithms for control of biological regulatory networks, which is crucial for applications in synthetic biology and disease intervention.
The paper addresses the problem of finding a minimum set of control nodes to steer a Boolean biological network toward a desired attractor. It proves the problem is inapproximable unless P=NP, but provides polynomial-time algorithms for networks with specific dynamics and topologies, achieving polylogarithmic approximation bounds.
Biological processes, including cell differentiation, organism development, and disease progression, can be interpreted as attractors (fixed points or limit cycles) of an underlying networked dynamical system. In this paper, we study the problem of computing a minimum-size subset of control nodes that can be used to steer a given biological network towards a desired attractor, when the networked system has Boolean dynamics. We first prove that this problem cannot be approximated to any nontrivial factor unless P=NP. We then formulate a sufficient condition and prove that the sufficient condition is equivalent to a target set selection problem, which can be solved using integer linear programming. Furthermore, we show that structural properties of biological networks can be exploited to reduce the computational complexity. We prove that when the network nodes have threshold dynamics and certain topological structures, such as block cactus topology and hierarchical organization, the input selection problem can be solved or approximated in polynomial time. For networks with nested canalyzing dynamics, we propose polynomial-time algorithms that are within a polylogarithmic bound of the global optimum. We validate our approach through numerical study on real-world gene regulatory networks.