基于半Markov决策过程的概率布尔网络模型

刘秋丽，杨 洁

(1．华南师范大学数学科学学院，广东广州510631;2．北京信息科技大学理学院，北京100192)

布尔网络和概率布尔网络(Probabilistic Boolean Networks，简称PBN)能模拟真实世界的基因调控网络［1-2］．PBN本质上是传统布尔网络的概率推广．布尔网络B=(V，F)是由基因节点的集合V={x1，x2，…，xn}，xi{0，1}(i=1，…，n)和函数序列 F={f1，…，fn}，fi:{0，1}n→{0，1}(i=1，…，n)组成的二元组．布尔函数序列F表示基因之间的调控准则，函数fi是基因i的预测函数．假设基因i在时刻t的状态记为xi(t)，xi(t)=0表示基因i没有表达，而xi(t)=1表示基因i表达．在t时所有基因的表达可用状态向量x(t)=(x1(t)，x2(t)，…，xn(t))表示．布尔网络和它的动态都是确定的．但是基因表达是随机的，为了弥补这种模型的不足，有必要将布尔网络推广到PBN．概率布尔网络结合了基因之间的不确定性，因此经常被用来模拟基因调控网的随机性质．给定一个概率布尔网络，从一个状态到其他状态的转移根据固定的转移概率．PBN的动态性质能用马尔可夫链来描述，进而Markov决策过程理论能用来分析和研究PBN中的最优控制问题．

为了避免和疾病相联系的状态，利用最优控制方法设计干预策略，从而影响网络的动态演化［2-6］．本文考虑的优化问题与文献［2］-［6］不同，这导致我们的处理方法跟文献［2］-［6］不同．PBN的最优控制已在 Markov决策过程的框架下刻画［2-3，5-6］，但是半Markov决策过程在PBN的应用至今研究尚少．本文将利用半Markov决策过程的首达目标理论研究PBN中的最优控制问题，给出PBN的定义，建立PBN的半Markov决策过程模型，给出最优问题的算法并用一个数值例子说明如何应用本文所给的方法找到最优治疗方式．

1 概率布尔网络

PBN是布尔网络的推广，本质上是由布尔网络组成的集类．布尔网络中每个基因只有一个预测函数，和布尔网络不同，在PBN中每个基因i的状态由多个预测函数f(i)j(j=1，2，…，l(i))决定．预测函数f(i)j的选取概率为(i=1，2，…，n)．假设fj为第j个可能的网络，则(1≤ji≤l(i)，i=1，2，…，n)．

这样的网络被选取的概率为

其中N=∏ni=1l(i)是布尔网络的个数．

状态(x1，…，xn)与(x'1，…，x'n)之间的转移概率可由下式得到

为了表达方便，通过下列方程可以把二进制数转换为十进制:

由于x(t)取值于{0，1}n，所以 zt取值从1到2n．由于x(t)到zt是一对一的，所以用十进制表示和分量表示是等价的．

本文假设PBN两次状态转移之间的时间间隔是随机的．考虑时刻 tk和tk+1，对所有的tk≤t＜tk+1，PBN的基因状态向量z(tk)=x．在tk+1时，网络到达新的基因状态向量z(tk+1)=y．设Xk+1表示转移到状态向量y之前停留在状态向量x的时间，有Xk+1=tk+1-tk．时间长度Xk+1是随机的，它的分布函数依赖当前的状态向量和将要到达的状态向量．PBN的动态性质可由半马尔可夫过程刻画．

2 概率布尔网络的半M arkov决策过程模型

在这个部分把PBN描述为半Markov决策过程首达目标模型．

首先给出PBN的状态．在任意时刻t≥0，PBN的状态x是基因状态向量的十进制表示．因此，状态空间由所有可能的状态向量组成，即S={1，2，…，2n}．给定PBN，一些状态表示基因调控网的某些性质，比如某些基因的表达与否导致网络到达不想要状态．根据想要状态和不想要状态的定义可以把状态空间分为不同的种类．假设S0⊂S为想要状态的集合，则S1=S-S0对应不想要状态的集合．

第二，在治疗癌症时诸如放射线和化学疗法等外部变量(控制输入)的使用可以使病人远离癌细胞扩散的状态．和PBN中状态的二元表示一致，我们假设外部变量(控制输入)为0或1．特别地假设n基因的PBN有m个控制输入u1，u2，…，um．包含控制输入向量v=(u1，…，um)能被看作行动．与状态向量的表示一致，用控制输入的十进制a表示行动．A(x)表示当PBN在状态xS时行动的集合．换言之，A(x)表示在状态x时对于控制者可选的控制输入a的集合．本文中行动空间为有限集，即A(x)={1，2，…，2m}．

第三，引入半Markov核来描述PBN的动态演化．对任意的tRR+，x，yS，给定的控制输入aA(x)，由文献［7］，半Markov核Q为

第四，为了完成对PBN的半Markov决策过程首达目标模型的描述，需要介绍一个优化准则．首先给出策略的定义．策略实际上是决策者选取行动的操作准则．对所有的xS，策略为作用在S× RR上的函数g且满足g(x，λ)属于A(x)．换言之，函数g(x，λ)是当前状态为x时所选取的行动．设G为所有策略的集合．

设τ表示PBN首次到达不想要的状态集S1的时间，即 τ=inf{t:ZtS1}．

至此，完成了PBN的半Markov决策过程首达目标模型:

定义相应的最优值函数为策略g*G称为最优的，如果对所有的(x，λ)S0×R R有D(x，λ，g*)=D*(x，λ)．对于最优策略g*，称{g*(x，λ)}最优行动．

3 优化问题的算法

在上节建立的PBN的半Markov决策过程首达目标模型的基础上，本节主要给出最优策略的计算方法．具体的算法如下:

由文献［8］可知，最优策略 g*存在．另外，假设{Dn+1，n≥-1}满足上述的值迭代算法，最优值函数D*等于Dn+1，即对每对(x，λ)S0× RR，有D*(x，λ)=Dn+1(x，λ)．详见文献［8］．

4 数值模拟

考虑三基因x1，x2，x3的概率布尔网络．基因x1由2个布尔函数f(1)1、f(1)2预测，基因x2由布尔函数f1(2)、f2(2)预测，基因x3由布尔函数f1(3)、f2(3)预测．假设x1取值为0或1的控制输入．对于新的PBN，变量x1、x2和x3重新命名如下:变量x1为控制输入a而x2和x3分别变为x1和x2．由表1可知有4个布尔网络(f1(1)，f1(2))、(f1(1)，f2(2))、(f2(1)，f1(2))以及(f(1)2，f(2)2)被选的概率P1、P2、P3和P4分别为P1=0．1、P2=0．4、P3=0．1 以及 P4=0．4．因此 c(1)1=0．15，c(1)2=0．85，c(2)1=0．2，c(2)2=0．8．

表1 真值表Table 1 Truth table

由于 n=2．因此变量 z可能取值于 1，2，3，4 中的任一个，状态空间为S={1，2，3，4}．假设最想要的状态是1、2和3，而不想要的状态是4．所以S0={1，2，3}，S1={4}．因为 m=1，所以控制输入 a 可能取1或者2，行动集A(x)={1，2}．报酬函数取值如下:r(1，1)=1，r(1，2)=2，r(2，1)=0．5，r(2，2)=0．8，r(3，1)=0．2，r(3，2)=0．6．

另外取ε=10-12．由上节给出的算法，一些数值结果见图1．

图1 函数Ta D*(x，λ)Figure 1 The function of Ta D*(x，λ)

由图1，最优策略g*为

［1］SHMULEVICH I，DOUGHERTY E R，KIM S，et al．Probabilistic Boolean networks:A rule-based uncertainty model for gene regulatory networks［J］．Bioinformatics，2002，18:261-274．

［2］DATTA A，BITTNER M L，DOUGHERTY E R．External control inmarkovian genetic regulatory networks［J］．Machine Learning，2003，52:169-191．

［3］LIU Q L，GUO X P，ZHOU T S，Optimal control for probabilistic Boolean networks［J］．IET Systems Biology，2010，4(2):99-107．

［4］CHING W，ZHANGhang SQ，JIAO Y，et al．Optimal control policy for probabilistic Boolean networkswith hard constraints［J］．IET Systems Biology，2009，3:90-99．

［5］PAL R，DATTA A，DOUGHERTY ER．Optimal infinite horizon control for probabilistic Boolean networks［J］．IEEE Transactions On Signal Processing，2006，52:169-191．

［6］CHEN PC Y，CHEN JW．A markovian approach to the control of genetic regulatory networks［J］．BioSystems，2007，90:535-545．

［7］GUO X P，HERNANDEZ-LERMA O．Continuous-time markov decision processes:Theory and applications［M］．New York:Springer，2009．

［8］HUANG Y H，GUO X P．Minimizing risk models in denumerable semi-Markov decision processes with a target set［C］∥Proceedings of the 29th Chinese control conference，Beijing，China，2010:1576-1581．