Computational Methods in Systems Biology

Graph Representations of Monotonic Boolean Model Pools 245

Proof.Since{t}⊆VQDEBooleanis a trap set inGBooleanQDE (Σ),f−^1 (t) is a trap set in
Gasync(f). For eachs∈f−^1 (t) it holdsf(s)=t, so there must exists a path to
tin the trap set. In particular,tis in the trap set, sof(t)=t 

We illustrate the last two corollaries by finding trap-sets and no-return sets
of the Boolean monotonic ensemble in our running example.

Example 7.Consider the sign matrix from our running Example 1 , depicted in
Fig. 1. The graphGBooleanQDE with its strongly connected components is depicted
in Fig. 4. They are:

A 0 ={(0, 0 , 0 ,1)}

A 1 ={(1, 1 , 1 ,0)}

A 2 ={ 0 , 1 }^4 \

(

A 0 ∪A 1 ∪A 3 ∪A 4

)

A 3 ={(1, 0 , 1 ,1)}

A 4 ={(0, 1 , 0 ,0)}.

We can now infer that for anyf∈MB(Σ)thesetsf−^1 (A 1 ),f−^1 (A 0 ) are trap-
sets while the setsf−^1 (A 3 ),f−^1 (A 4 ) are no-return sets.
Both the functionfintroduced in Example 1 as well asg∈MB(Σ) given by
g(x)=(1−x 4 ,x 1 ,x 2 +(1−x 4 )−x 2 ·(1−x 4 )) are elements of the ensemble.
For functionfwe see its asynchronous state transition graphGasync(f)in
Fig. 1 and its quotient graphGasync(f)

/

f in Fig. 3. We easily compute that
f−^1 (A 1 ),f−^1 (A 0 ) are non-empty by checking that (0, 0 , 0 ,1),(1, 1 , 1 ,0) are fixed
points off.

5 The Quotient GraphGasync(f)

/

φF as Discretization

of Continuous Data

In application, the choice of modeling formalism is not always straight forward,
since continuous and discrete approaches have complementing strengths. Bridg-
ing the formalisms is therefore of high interest. The QDE formalism is a suitable
way to do so, as illustrated by the results for piecewise linear systems utilizing
similar ideas with successful applications in systems biology [ 3 ].
The results we presented here give a precise link between a Boolean model
fand a QDE system, since the ESTGGBooleanQDE (Σ) of a Boolean monotonic
ensemble coincides with the QDE state transition graph corresponding toΣ,
and the quotient graphGasync(f)

/

φf is a subgraph of this ESTG. Trajecto-
ries inGasync(f)

/

φfthus capture the qualitative behavioral patterns encoded in
abstractions of ODEs. The−1 and 1 values ofφfreflect the decreasing or increas-
ing tendencies of a continuous trajectory, taking into account that for example a
negative value of (φf)ifor somei∈{ 1 ,...,n}is either caused by a component
iin the Boolean system switching from 1 to 0 or by remaining 0, which is nor-
mally in a continuous system realized by an asymptotically decreasing behavior.