  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.
