IEEE/ACM Trans Comput Biol Bioinform. 2020 Nov-Dec;17(6):1932-1945. doi: 10.1109/TCBB.2019.2915081. Epub 2020 Dec 8.
We study the problem of computing a minimal subset of nodes of a given asynchronous Boolean network that need to be perturbed in a single-step to drive its dynamics from an initial state to a target steady state (or attractor), which we call the source-target control of Boolean networks. 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 this view, we derive a decomposition-based solution to the minimal source-target control problem which can be significantly faster than the existing approaches on large networks. We then show that the solution can be further optimized if we take into account appropriate information about the source state. We apply our solutions to both real-life biological networks and randomly generated networks, demonstrating the efficiency and efficacy of our approach.
我们研究了计算给定异步布尔网络中最小节点子集的问题，这些节点需要在单个步骤中被扰动，以将其动力学从初始状态驱动到目标稳定状态（或吸引子），我们称之为布尔网络的源-目标控制。由于状态空间爆炸的现象，在整个网络上执行计算的简单全局方法可能不适用于大型网络。我们相信，对于此类网络，有效的算法必须利用网络的结构及其动态特性。基于这种观点，我们针对最小源-目标控制问题推导出了一种基于分解的解决方案，该方案在大型网络上的速度可以明显快于现有方法。然后我们表明，如果我们考虑到关于源状态的适当信息，该解决方案可以进一步优化。我们将我们的解决方案应用于真实的生物网络和随机生成的网络，展示了我们方法的效率和效果。
