# Robust Invariant Set Analysis of Boolean Networks

Authors: Bowen Li; Jungang Lou; Yang Liu; Zhen Wang
Journal: Complexity
 (2019)

---

## Abstract

In this paper, the robust invariant set (RIS) of Boolean (control) networks with disturbances is investigated. First, for a given fixed point, consider a special set called immediate neighborhoods of the fixed point; then a discrete derivative of Boolean functions at the fixed point is used to analyze the robust invariance, based on which a sufficient condition is obtained. Second, for more general sets, the robust output control invariant set (ROCIS) of Boolean control networks (BCNs) is investigated by semitensor product (STP) of matrices. Then, under a given output feedback controller, we obtain a necessary and sufficient condition to check whether a given set is robust control invariant set (RCIS). Furthermore, output feedback controllers are designed to make a set to be a RCIS. Finally, the proposed methods are illustrated by a reduced model of the lac operon inE. coli.


---

## Body

## 1. Introduction

In 1969, Kauffman [1] firstly used Boolean networks (BNs), which are a kind of logical networks to study genetic regulatory networks. Then, BNs have attracted extensive attention and have become abstract modeling schemes in other different fields such as neural networks [2] and immune response [3]. In BNs, each gene expression has two states as “1” and “0” to represent “on” and “off,” respectively. Moreover, interactions between the states of each gene depend on Boolean functions, which are composed of logical operators such as disjunction and conjunction and so on. The state evolution for each gene is updated by a Boolean function about the states of current neighborhoods.When control inputs are added into BNs, then BNs can be called BCNs. Similarly, control inputs take two values: “0” implies that the application of that intervention is ceased at that time point, and “1” means that some interventions are applied in BNs. A new matrix product called semitensor product (STP) of matrices was proposed to investigate BNs and BCNs [4]. Based on this, a BN (or BCN) can be converted into the corresponding algebraic form by calculating its unique transition matrix. Therefore, many fundamental and interesting problems have been investigated for BNs and BCNs, such as the controllability [5, 6], stabilization [7–15], observability [16–19], disturbance decoupling problem [20] synchronization [21], function perturbations [22], optimal control [23–26], normalization problem [27], and others. The STP has also been widely applied in games [28, 29] and asynchronous sequential machines [30, 31]. In detail, [28] investigated the evolutionarily stable strategy of finite evolutionary networked games by STP and then designed event-triggered controllers such that systems could converge globally. In [29], the stochastic set stabilization of random evolutionary Boolean games was further investigated, and a constructive algorithm was proposed to calculate stochastic reachable sets. On the other hand, [30] and [31] investigated the reachability and skeleton matrix by STP, respectively.Usually, some external disturbance inputs always exist in systems. For example, cancer can be defined as failures in the healthy mechanisms of biological systems, and it has been classified as a kind of genetic uncertainties consisting of mutations [32]. Therefore, designing controllers is of great importance such that the set of desirable cellular states of BCNs with disturbance inputs is robust. In other words, if the trajectories of BCNs with some initial states reach a given set, which is called robust control invariant set (RCIS) [33], then those trajectories will never leave the set no matter what disturbances are. The RCIS has attracted many scholars’ attention and obtained many results [34–37]. In [33], Li et al. used STP to study the RCIS of BCNs and presented an effective procedure to design state feedback controllers. However, due to the limitation of measurement conditions and the impact of immeasurable variables, measured output information rather than state information is always used to analyze and control systems [38]. Therefore, we will design output feedback controllers such that the trajectories of BCNs starting from some initial states in a given set will never leave the given set, which is called robust output control invariant set (ROCIS). On the other hand, Robert analyzed the local convergence of BNs by the discrete derivative of Boolean functions at a fixed point [39], which is a novel approach to investigate BNs. Motivated by this, we use the discrete derivative method to investigate the RIS, which makes the computational complexity reduced compared with STP. To the best of our knowledge, there is no result concerning the ROCIS of BCNs. The contributions of this paper are listed as follows:(i)
The discrete derivative is used to analyze the robust invariance.(ii)
A necessary and sufficient condition is derived to check whether a given set is ROCIS under a given output feedback controller.(iii)
Output feedback controllers are designed to make a given set be a ROCIS.The rest of this paper is organized as follows. Section2 reviews some notations and preliminary results, which will be used in the latter. Section 3 presents the main results. Section 4 ends the paper with a brief conclusion.


## 2. Preliminaries

In this section, we give some necessary properties of the STP and list some useful notations.(i)
Let[a,b] be the set {a,a+1,…,b} for integers b>a.(ii)
Denote by matrixMm×n the set of m×n real matrices.(iii)
SetΔn:={δnk:1≤k≤n}, where δnk is the k-th column of identity matrix In.(iv)
LetColi(B) stand for the i-th column of the matrix B.(v)
MatrixL=[δmi1,δmi2,…,δmin] is called a logical matrix, and simply denote it by L=δm[i1,i2,…,in].(vi)
Let12k denote the row vector of length 2k with all entries being 1.Definition 1 ([4]).
For any given two matricesA∈Mm×n and B∈Mp×q, the STP of A and B is defined as (1)A⋉B=A⊗Il/nB⊗Il/p,where l=lcm(n,p) is the least common multiple of n and p and ⊗ is the Kronecker product.Proposition 2 ([4]).
LetX∈Rm be a column and N be any matrix. Then (2)X⋉N=Im⊗N⋉X.Definition 3 ([40]).
LetM∈Mp×m,N∈Mq×m. Then, the Khatri-Rao product is defined as (3)M∗N=Col1M⋉Col1N⋯ColmM⋉ColmN∈Mpq×m.The notation∨¯ represents that when the two values denoted by A and B taking from D are the same, then A∨¯B=0. Otherwise, the result equals 1.A logical domain, denoted byD is defined as D={0,1}, and Dn=D×⋯×D︸n. If identifying 0~δ22 and 1~δ21, then Δ2~D, and Δ2n~Dn, where “~” represents two different forms of the same object. If X∈Dn, then we say X is in a scalar form. If X∈Δ2n, we say X is in a vector form. In the sequel, to distinguish the scalar form and the vector form of a variable, we use the notation X for a variable in Dn, while we use the notation x for its vector variable in Δ2. In short, X∈D, but x∈Δ2.The following lemma is important for the algebraic expressions of logical functions.Lemma 4 ([4]).
Consider a logical functionf(X1,X2,…,Xn):Dn→D. There exists a unique matrix Mf∈L2×2n, called the structure matrix of f, such that (4)fX1,X2,…,Xn=Mf⋉⋉i=1nxi,where ⋉i=1nxi=x1⋉x2⋯⋉xn∈Δ2n.For example, the structure matrix of logical function∨ is δ2[1,1,1,2]. And the structure matrix of logical function ∧ is δ2[1,2,2,2].Definition 5.
Assume that there aren-dimensional row vectors X1=(X11,X12,…,X1n) and X2=(X21,X22,…,X2n), Xij∈D, i∈[1,2], j∈[1,n], respectively. The distance vector denoted by d(X1,X2) between X1 and X2 is defined; that is, d(X1,X2)=((X11∨¯X21),(X12∨¯X22),…,(X1n∨¯X2n))T.Assume thatX=(X1,X2,…,Xn)T∈Dn, and then define a bijection J:Dn→Δ2n [4], where(5)JX=⋉s=1nδ22-xs=δ2nkwith k=(1-X1)2n-1+(1-X2)2n-2+⋯+(1-Xn-1)2+(2-Xn). Furthermore, we can also define J-1:Δ2n→Dn, where(6)J-1δ2nk=X1,X2,…,XnTwith X1=2-⌈k/2n-1⌉ and Xi=2-⌈k-(∑j=1i‍(1-Xj)2n-j)/2n-i⌉, i∈[2,n].For example, assume thatX=(1,0,0,1)∈D4; then, by (5), one has that J(X)=δ167.


## 3. Main Results

We consider the following system withn disturbance inputs:(7)X1t+1=f1ξ1t,X1t,…,Xnt,⋮Xnt+1=fnξnt,X1t,…,Xnt,where Xi∈D and ξi∈D,i∈[1,n]. fi:Dn+1→D,i∈[1,n] is a logical function.For eachfi, there exists a unique structure matrix Mfi,i∈[1,n], by Lemma 4. Let x(t)=⋉i=1nxi(t)∈Δ2n and ξ(t)=⋉i=1nξi(t)∈Δ2n, then system (7) can be converted into the following forms: (8)x1t+1=Mf1⋉ξ1t⋉xt=Mf1⋉I2⊗12n-1⋉ξt⋉xt≔M¯f1⋉ξt⋉xt,⋮xnt+1=Mfn⋉ξnt⋉xt=Mfn⋉12n-1⋉ξt⋉xt≔M¯fn⋉ξt⋉xt,where M¯fi=Mfi⋉(I2i⊗12n-i),i∈[1,n-1] and M¯fn=Mfn⋉12n-1. Multiplying all the equations in (8) together, we get(9)xt+1=L⋉ξt⋉xt,where L=M¯f1∗M¯f2∗⋯∗M¯fn∈L2n×22n with ∗ is the Khatri-Rao product [40]. Split L into 2n equal blocks denoted by Li∈L2n×2n,i∈[1,2n], and then one has(10)xt+1=L⋉ξt⋉xt,=L1L2⋯L2n⋉ξt⋉xt.Given a state denoted byX∈Dn, we denote the immediate neighborhoods of X by I(X) [39]; that is, (11)IX=X′:dX′,X=ei,i∈1,n,where ei,i∈[1,n] represents the i-th column of identify matrix In. For example, assume that X=(1,0,1)∈D3, and then, based on the above definition, one has that I(X)={(0,0,1),(1,1,1),(1,0,0)}. Assume that I(X)={X1,X2,…,Xn}, where d(Xi,X)=ei, i∈[1,n]. Let I′(X)=I(X)∪{X}.Definition 6.
Assume that twon-dimensional Boolean row vectors X1=(X11,X12,…,X1n) and X2=(X21,X22,…,X2n). We say that X1≤X2 if, for any i∈[1,n], X1i≤X2i.For example, there are two vectors asX1=(1,0,1,1) and X2=(1,0,1,0). We have X11=X21=1,X12=X22=0,X13=X23=1, and X14=1≥X24=0, and then X1≥X2.Definition 7.
Consider system (7), and assume that X is one of the fixed points for any disturbance. If, for any Xi∈I(X) and disturbance input ξ(t)∈Dn, Xi(t+1)∈I′(X), then I′(X) is said to be a RIS.Definition 8 ([39]).
Consider system (7) with disturbance inputs. For any given state X∈Dn and when ξi(t)≡1(orξi(t)≡0), the discrete derivative of Boolean functions at state X, denoted by Dξ1(X)(orDξ0(X)), is an n×n Boolean matrix with its elements given as follows: (12)Dξ1Xi,j=1,iffi1,X≠fi1,Xj,0,otherwise,or (13)Dξ0Xi,j=1,iffi0,X≠fi0,Xj,0,otherwise.Based on Definition8, we further define another n×n Boolean matrix; that is, (14)DXi,j=Dξ1Xi,j∨Dξ0Xi,j.It can be learned from the construction of D(X) that for any Xi∈I(X), i∈[1,n], and ξ(t)=δ2njt∈Δ2n, we get(15)dJ-1LjtJXi,J-1LjtJX≤DX⋉dXi,X.Theorem 9.
Consider system (7) with the fixed point X for any disturbance. If D(X) has at most one 1 in each column, then I′(X) is a RIS.Proof.
If each column ofD(X) can only be zero vector or a basis vector, then it can be learned from (15) that the state can be guaranteed in the set I′(X) beginning from any initial state Xi∈I(X), i∈[1,n], in every step, which completes the proof.Example 10.
Consider a BN with the fixed pointX being (1, 1) for any disturbance:(16)X1t+1=X1t∨ξ1t,X2t+1=X1t∨X2t∨ξ2t.One has I((1,1))={(0,1),(1,0)} and I′((1,1))={(0,1),(1,0),(1,1)}. Let ξ1=ξ2=1 and ξ1=ξ2=0, respectively, and we can get (17)Dξ11,1=0000and (18)Dξ01,1=1000.Therefore, (19)D1,1=1000.Since Col1(D((1,1)))=(1,0)T and Col2(D((1,1)))=(0,0)T, then Theorem 9 holds. Therefore, I′((1,1)) is a RIS.Remark 11.
It is learned from Theorem9 that matrix D(X) with dimension n×n (not 2n×2n) can be constructed, based on which the RIS is analyzed. Therefore, compared with the results obtained by STP in [35], the computational complexity is reduced from O(2n) to O(n2). Unfortunately, the method of discrete derivative can only be used to analyze some special systems in the form of (7). In the sequel, we will further analyze more general sets and design output feedback controllers such that the set is robust for any disturbance inputs.In the following, consider a BCN withn nodes, p outputs, q disturbance inputs, and m inputs as(20)X1t+1=f1ξ1t,…,ξqt,U1t,…,Umt,X1t,…,Xnt,⋮Xnt+1=fnξ1t,…,ξqt,U1t,…,Umt,X1t,…,Xnt,Y1t=h1X1t,…,Xnt,⋮Ypt=hpX1t,…,Xnt,where fi:Dq+m+n→D and hα:Dn→D are logical functions, i∈[1,n], α∈[1,p].Then, the definition of a ROCIS of BCNs is presented as follows.Definition 12.
Consider system (20). A nonempty set S⊆Dn is said to be a ROCIS, if there exists an output feedback control as(21)U1t=g1Y1t,…,Ypt,⋮Umt=gmY1t,…,Ypt,where gβ:Dp→D,β∈[1,m] are Boolean functions such that, for the closed-loop system consisting of (20) and (21), X(t)∈S implies X(t+1)∈S.It can be learned from Lemma4 that we can find unique structure matrices Mfi, Mhα, and Mgβ for logical functions fi, hα, and gβ in (20) and (21), respectively, i∈[1,n], α∈[1,p],β∈[1,m]. Then the equivalent forms of (20) and (21) are(22)x1t+1=Mf1⋉ξt⋉ut⋉xt,⋮xnt+1=Mfn⋉ξt⋉ut⋉xt,y1t+1=Mh1⋉xt,⋮ypt+1=Mhp⋉xt,and(23)u1t=Mg1⋉yt,⋮umt=Mgm⋉yt,respectively, where x(t)=⋉i=1nxi(t), y(t)=⋉i=1pyi(t), ξ(t)=⋉i=1qξi(t), and u(t)=⋉i=1mui(t).Multiply the equations in (22), and (23), respectively; then (20) and (21) can be converted into the following forms:(24)xt+1=L⋉ξt⋉ut⋉xt,yt=K⋉xt,and(25)ut=G⋉yt,respectively, and L=Mf1∗⋯∗Mfr∈L2r×2n, K=Mh1∗⋯∗Mhr∈L2p×2n, and G=Mg1∗⋯∗Mgm∈L2m×2p.Assume that a given nonempty setS=δ2ni1,δ2ni2,…,δ2nir with 1≤i1<i2<ir≤2n, and we analyze the following two problems:(i)
Problem 1: For a given output feedback matrixG∈L2m×2p, analyze whether the set S is a ROCIS of system (20) under control system u(t)=Gy(t).(ii)
Problem 2: Design output feedback controllers such thatS is a ROCIS of system (20).Plug (25) into (24), then one has that(26)xt+1=L⋉ξt⋉G⋉yt⋉xt=L⋉ξt⋉G⋉K⋉xt⋉xt=L⋉ξt⋉G⋉K⋉Φn⋉xt=L⋉I2q⊗G⋉K⋉Φn⋉ξt⋉xt,≔L~⋉ξt⋉xt, where L~=L(I2q⊗GKΦN), and Φn=Diagδ2n1,δ2n2,…,δ2n2n∈L22n×2n is the power-reducing matrix satisfying x(t)⋉x(t)=Φnx(t).SplitL~ into 2q equal blocks as (27)L~=L~1L~2⋯L~2q,where L~μ∈L2n×2n+m, μ∈[1,2q], and then it follows from (26) that(28)xt+1=L~1L~2⋯L~2q⋉ξt⋉xt.Therefore, based on Definition 12, we have the following result.Theorem 13.
For a given setS=δ2ni1,…,δ2nir and an output feedback gain matrix G, set S is a ROCIS of system (20) under the output feedback control u(t)=G⋉y(t) if and only if, for any μ∈[1,2q], x(t)∈S, and then L~μ⋉x(t)∈S.Proof.
It is easy to see that the sufficiency holds, and we only need to prove the necessity. Consider (28); since S=δ2ni1,…,δ2nir is a ROCIS of system (20) under the output feedback control u(t)=Gy(t), then, for any ξ(t)=δ2qμ, μ∈[1,2q], and any x(t)∈S, one has(29)xt+1=L~1L~2⋯L~2q⋉δ2qμ⋉xt=L~μ⋉xt∈S.From the arbitrariness of ξ(t) and x(t), the conclusion holds.Remark 14.
As mentioned above that setDn is equivalent to Δ2n. Based on STP, the algebraic expression of system (20) can be obtained. Therefore, it will be better to write set S in vector form in Theorem 13 compared with Definition 12.In the following, we discuss Problem 2, and then controller (25) will be designed. Suppose that K=δ2p[k1k2⋯k2n]∈L2p×2n and G=δ2m[b1b2⋯b2p]∈L2m×2p, which will be designed. On one hand, for system (26) with u(t)=Gy(t), ξ(t)=δ2qμ, and x(t)=δ2niv∈S,μ∈[1,2q],v∈[1,r], one has that(30)xt+1=L⋉ξt⋉G⋉K⋉xt⋉xt=L⋉δ2qμ⋉G⋉K⋉δ2niv⋉δ2niv=Lμ⋉δ2m⋉bk1bk2⋯bk2n⋉δ2niv⋉δ2niv=Lμ⋉δ2mbkiv⋉δ2niv=Colbkiv-12n+ivLμ. On the other hand, we define the following sets: (31)S′=ij:δ2nij∈S. Obviously, S′={i1,i2,…,ir}. For each kiv∈[1,2p],v∈[1,r], (32)ϑkiv=λ:ColλK=δ2pkiv,λ∈1,2n,and then denote (33)φkiv=ϑkiv∩S′.For any integerv∈[1,r], define(34)Γiv=bkiv∈1,2m:Colbkiv-12n+ivLμ∈S,foranyμ∈1,2q.For each φ(kiv), we construct a set, denoted by W(kiv), as(35)Wkiv=⋂λ∈φkivΓλ,φkiv≠∅,1,2m,φkiv=∅.Then, the result about the existence of output feedback controllers can be obtained.Theorem 15.
S = δ 2 n i 1 , … , δ 2 n i r is a ROCIS of system (20) by an output feedback control, if and only if, for any kiv∈[1,2p], v∈[1,r],(36)Wkiv≠∅.Moreover, if (36) holds, then output feedback matrices under which S is a ROCIS are constructed as(37)G=δ2mb1b2⋯b2p with (38)bι∈Wkiv,ifι=kiv,v∈1,r,1,2m,otherwise.Proof.
(Sufficiency): Suppose that (36) holds. We construct controller (37). Then, for K=δ2p[k1k2⋯k2n], one has (39)GK=δ2mbk1bk2⋯bk2n.Moreover, for any ξ(t)=δ2qμ, μ∈[1,2q], and x(t)=δ2niv∈S, v∈[1,r], we have that bkiv∈W(kiv)⊆Γiv, and then it can be learned from (34) that x(t+1)=Col(bkiv-1)2n+iv(Lμ)∈S, for all μ∈[1,2q]. Therefore, S is a ROCIS of system (20).
(Necessity): Suppose thatS is a ROCIS of system (20) with control u(t)=Gy(t), and then, for any ξ(t)=δ2qμ, μ∈[1,2q], one can obtain that x(t)=δ2niv∈S, v∈[1,r], which means that (36) holds.
In fact, if (36) does not hold, then there exists an integer v1∈[1,r] such that W(kiv1)=∅. In this case, it can be learned from (35) that φ(kiv1)≠∅ and ⋂λ∈φ(kiv1)Γλ=∅. Assume that φ(kiv1)={j1,j2,…,jϵ}, i.e., kj1=kj2=⋯=kjϵ=kiv1, then we have bkj1=bkj2=⋯=bkjϵ=bkiv1. Since S is a ROCIS of system (20) with control u(t)=G⋉y(t), then bkiv1∈⋂λ∈φ(kiv1)Γλ, which is a contradiction to ⋂λ∈φ(kiv1)Γλ=∅. As a result, for any v∈[1,r], W(kiv)≠∅.Example 16.
Let us consider a reduced model of the lac operon inE. coli [33, 41]:(40a)X1t+1=¬U1t∧X2t∨X3t,X2t+1=¬U1t∧U2t∧X1t∧ξt,X3t+1=¬U1t∧U2t∨U3t∧X1t,where X1,X2, and X3 are state variables denoting the lac mRNA, the lactose in high concentrations, and the lactose in medium concentrations, respectively; U1,U2, and U3 are inputs variables representing the extracellular lactose, the high extracellular lactose, and the medium extracellular lactose, respectively; ξ is an external disturbance. The output equations are given by(40b)Y1t=¬X1t∧X2t∨X3t,Y2t=X1t∧X3t∨¬X1t∧X2t∧X3t,Y3t=¬X1t∧X3t. And the robust set S={(X1,X2,X3):X1=1,X2∨X3=1}.
Obviously,S={δ81,δ82,δ83}, and then S′={1,2,3}. Let x(t)=x1(t)⋉x2(t)⋉x3(t), u(t)=u1(t)⋉u2(t)⋉u3(t), and y(t)=y1(t)⋉y2(t)⋉y3(t), and then we have(41)xt+1=L⋉ξt⋉ut⋉xt,yt=K⋉xt, where (42)L=δ888888888888888888888888888888888111533371115333733374448444844488888888888888888888888888888888833373337333733373337444844484448,and (43)K=δ813132357.
In this example, one can getk1=k3=1, and k2=3, and then we have ϑ(1)={1,3} and ϑ(3)={2,4}. Therefore, φ(1)=S′∩ϑ(1)={1,3}, and φ(3)=S′∩ϑ(3)={2}. From (34), we have Γ1=Γ2=Γ3={5,6,7}, which means that W(1)={5,6,7}, and W(3)={5,6,7}. By Theorem 15, S is a ROCIS of system 40a and 40b with the disturbance ξ, and the output feedback gain matrices are (44)G=δ8b1b2⋯b8with b1∈W(1), b3∈W(3), and bi∈[1,8], i=2,4,5,6,7,8. For example, let b1=b3=6, b4=b5=5, and b2=b6=b7=b8=1, and then the corresponding output feedback control is(45)U1t=X1t∧¬X2t→X3t∨¬X1t∧¬X2t∨X3t,U2t=1,U3t=X1t∧¬X3t.


## 4. Conclusion

In this paper, the RIS of BNs (BCNs) with disturbances was investigated. A special set called immediate neighborhood of a given fixed point was considered; then the discrete derivative of Boolean functions at the fixed point was used to analyze the robust invariance; based on this a sufficient condition was obtained. Furthermore, the ROCIS of BCNs was considered by STP. A necessary and sufficient condition was obtained to check whether a given set is RCIS under a given output feedback controller. Finally, for a given set, output feedback controllers were designed such that the set is RCIS.



---

*Source: 2731395-2019-02-03.xml*