Cui Su

Soumya Paul, Cui Su, Jun Pang et al.

We study the problem of computing a minimal subset of nodes of a given asynchronous Boolean network that need to be controlled to drive its dynamics from an initial steady state (or attractor) to a target steady state. Due to the phenomenon of state-space explosion, a simple global approach that performs computations on the entire network, may not scale well for large networks. We believe that efficient algorithms for such networks must exploit the structure of the networks together with their dynamics. Taking such an approach, we derive a decomposition-based solution to the minimal control problem which can be significantly faster than the existing approaches on large networks. We apply our solution to both real-life biological networks and randomly generated networks, demonstrating promising results.

Soumya Paul, Jun Pang, Cui Su

Given a Boolean network BN and a subset A of attractors of BN, we study the problem of identifying a minimal subset C of vertices of BN, such that the dynamics of BN can reach from a state s in any attractor As in A to any attractor At in A by controlling or toggling a subset of vertices in C in a single time step. We describe a method based on the decomposition of the network structure into strongly connected components called blocks. The control subset can be locally computed for each such block and the results then merged to derive the global control subset C. This potentially improves the efficiency for many real-life networks that are large but modular and well-structured. We are currently in the process of implementing our method in software.