Biology Reference
In-Depth Information
Table 3
Stationary states found for the network in Fig. 9
EMF1 TFL1 AP1 AG AP3 PI
0 0 0 1 1 1
0 0 0 1 0 0
0 0 1 0 1 1
0 0 1 0 0 0
? 1 0 0 0 0
? 1 0 0 1 1
t AP I t AP I t IPA t IPA t AP I <t AP I t IPA <t IPA
superset definition
¬ non conflicting P I ,AP 3 ,t AP I ,t IPA
the superset cannot be non conflicting
( t AP I =0 ( t AP I > 0
PI =1))
( t IPA =0 ( t IPA > 0
AP 3=1))
balance for PI
balance for AP 3
The bound on every place is 1. The subformula non conflicting( PI , AP3 , t AP I , t IPA ) is given by:
(( AP 3
0) ( AP 3 0)) .
Table 3 shows the result of the analysis of the simplified network. All significant states were identified,
and only two insignificant where found (gene TFL1 is active, but EMF1 is not). This proves empirically
that the refined approach is more efficient than the straightforward one.
t AP I ) ( PI
t IPA ) ( PI
DISCUSSION
In this article we proposed a mathematical formalism for identification of stationary states in Petri nets.
We also showed that this approach yields very promising results when applied to a real world example
such as the regulatory network of A. thaliana flower morphogenesis.
The proposed method for identifying stationary states uses Presburger arithmetic.
The complexity
2 2 pn
of present algorithms for testing these formulae is proportional to 2
[see Oppen, 1978] and the
2 pn
problem has a lower bound of 2
as shown in [Fischer and Rabin, 1974]. However the formulae we
have constructed have a relatively simple structure, with only two general quantifiers. This renders it
highly probable that the complexity of computations may be reduced to a satisfactory level in our setting.
Moreover, in the case of bounds equal to one, we get essentially a quantified boolean formula (QBF). It
is an interesting question if symbolic techniques of effectively presenting and solving such formulae can
be applied, for instance BDDs [Bryant, 1992]. Another possibility is to use existing QBF solvers (e.g.,
see Benedetti, 2005). This are the most promising ideas for further investigations, and could result in a
very effective procedure for computing stationary states.
Apart from logical description of stationary states, we also proposed two different approaches to
studying gene regulatory networks, a straightforward one and a refined one. The latter was found to be
more efficient, but requires a human expert intervention. The optimization of the algorithms for finding
stationary states is an issue for further research.
 
Search WWH ::




Custom Search