Yang Cong, Wai-Ki Ching, Nam-Kiu Tsing, Ho-Yin Leung
Advanced Modeling and Applied Computing, Department of Mathematics, The University of Hong Kong, Hong Kong.
BMC Syst Biol. 2010 Sep 13;4 Suppl 2(Suppl 2):S14. doi: 10.1186/1752-0509-4-S2-S14.
Probabilistic Boolean Networks (PBNs) provide a convenient tool for studying genetic regulatory networks. There are three major approaches to develop intervention strategies: (1) resetting the state of the PBN to a desirable initial state and letting the network evolve from there, (2) changing the steady-state behavior of the genetic network by minimally altering the rule-based structure and (3) manipulating external control variables which alter the transition probabilities of the network and therefore desirably affects the dynamic evolution. Many literatures study various types of external control problems, with a common drawback of ignoring the number of times that external control(s) can be applied.
This paper studies the intervention problem by manipulating multiple external controls in a finite time interval in a PBN. The maximum numbers of times that each control method can be applied are given. We treat the problem as an optimization problem with multi-constraints. Here we introduce an algorithm, the "Reserving Place Algorithm'', to find all optimal intervention strategies. Given a fixed number of times that a certain control method is applied, the algorithm can provide all the sub-optimal control policies. Theoretical analysis for the upper bound of the computational cost is also given. We also develop a heuristic algorithm based on Genetic Algorithm, to find the possible optimal intervention strategy for networks of large size.
Studying the finite-horizon control problem with multiple hard-constraints is meaningful. The problem proposed is NP-hard. The Reserving Place Algorithm can provide more than one optimal intervention strategies if there are. Moreover, the algorithm can find all the sub-optimal control strategies corresponding to the number of times that certain control method is conducted. To speed up the computational time, a heuristic algorithm based on Genetic Algorithm is proposed for genetic networks of large size.
概率布尔网络（PBNs）为研究基因调控网络提供了一种便捷工具。开发干预策略主要有三种方法：（1）将PBN的状态重置为期望的初始状态，然后让网络从该状态开始演化；（2）通过最小程度地改变基于规则的结构来改变基因网络的稳态行为；（3）操纵外部控制变量，这些变量会改变网络的转移概率，从而理想地影响动态演化。许多文献研究了各种类型的外部控制问题，但共同的缺点是忽略了外部控制可以应用的次数。
本文研究了在有限时间间隔内通过操纵PBN中的多个外部控制来解决干预问题。给出了每种控制方法可以应用的最大次数。我们将该问题视为一个具有多个约束条件的优化问题。在此，我们引入一种算法，即“预留位置算法”，以找到所有最优干预策略。给定某种控制方法应用的固定次数，该算法可以提供所有次优控制策略。还给出了计算成本上限的理论分析。我们还基于遗传算法开发了一种启发式算法，以找到大型网络可能的最优干预策略。
研究具有多个硬约束的有限时域控制问题是有意义的。所提出的问题是NP难问题。如果存在多个最优干预策略，预留位置算法可以提供多个。此外，该算法可以找到与某种控制方法执行次数相对应的所有次优控制策略。为了加快计算时间，针对大型基因网络提出了一种基于遗传算法的启发式算法。
