Motivated by the graded posteriorization during the AP axis development in the frog Xenopus laevis, we propose an abstract Petri net model for the formation of a gradient of proteins in a chain of cells. Recent Advances in Petri Nets and Concurrency, S. Donatelli, J. Kleijn, R.J. Machado, J.M. Fernandes (eds.), CEUR Workshop Proceedings, ISSN 1613-0073, Jan/2012, pp. 39{53.
Petri nets have been shown to be very promising for molecular and cellular
biology, in particular for metabolic, signalling and gene- regulatory networks (see
e.g. [
Currently, we are working on a case study: the embryonic development of
the anterior-posterior i.e., head-to-tail axis (AP axis) i n the model organism
Xenopus laevis, the African clawed frog. The development of this model embryo
has been studied thoroughly and a huge amount of literature is available to
draw from when building and validating the model, see references in [
In this paper we present a fundamental approach to modelling a particular
subprocess: the formation of a morphogen gradient, which helps instigate the
differentiation of the cells along the developing axis. This subprocess is a good
starting point, since it is relatively simple conceptually, in comparison to the
other subprocesses in the case study. In early development, gradients are
crucial ([
Throughout this paper the emphasis will be on abstraction and modelling decisions, as opposed to implementation of specific biological data; we present a basic Petri net modelling gradient formation, which serves as a proof of concept for our approach. In the remainder of this paper we outline the biological background of gradient formation in general and in this particular case study. Subsequently we describe our modelling decisions and we present the model. In the last section the possibilities of the model and future work are discussed. 2
For a general introduction to Petri nets we refer to [
Petri nets are defined by an underlying structure consisting of places and transitions. These basic elements are connected by directed, weighted arcs. In the Petri net model considered in this paper, there are moreover activator arcs connecting places to transitions. In modelling, places are usually the passive elements, representing local states, and transitions the active elements. Here, global states, referred to as markings, are defined as mappings assigning to each place a natural number (of tokens corresponding to available resources).
A PTA-net , is a tuple N = (P, T, W, Act, m0) such that: – P and T are finite disjoint sets, of the places and transitions of N , resp. – W : (T × P ) ∪ (P × T ) → N is the weight function of N . – Act ⊆ P × T is the set of activator arcs of N .
– m0 : P → N is the initial marking of N .
In diagrams, places are drawn as circles, and transitions as boxes. Activator arcs are indicated by black-dot arrowheads. If W (x, y) ≥ 1, then (x, y) is an arc leading from x to y; it is annotated with its weight if this is greater than one. A marking m is represented by drawing in each place p exactly m(p) tokens as small black dots. We assume that each transition t has at least one input place (there is at least one place p such that W (p, t) ≥ 1).
When a single transition t occurs (fi‘res’) at a marking, it takes tokens from its input places and adds tokens to its output places (with the number of tokens consumed/produced given by the weights of the relevant arcs). Moreover, if there Modelling Gradients Using Petri Nets 3 is an activator arc (p, t) ∈ Act , then transition t can only be executed at the given marking if p contains at least one token, without the implication of tokens in p being consumed or produced when t occurs. Thus, the difference with a self-loop , i.e., an arc from p to t and vice versa, is that the activator arc only tests for the presence of tokens in p.
We define the executions of N in the more general terms of simultaneously occurring transitions. A step is a multiset of transitions U : T → N. Thus U (t) specifies how many times transition t occurs in U . (Note that if we exclude the empty multiset, single transitions can be considered as minimal steps.) Step U is enabled (to occur) at a marking m if m assigns enough tokens to each place for all occurrences of transitions in U and, moreover, all places tested through an activator arc by a transition in U , contain at least one token.
Formally, step U is enabled at marking m of N if, for all p ∈ P : m(p) ≥ Pt∈T U (t) · W (p, t) m(p) ≥ 1 whenever there is a transition t such that U (t) ≥ 1 and (p, t) ∈ Act .
If U is enabled at m, it can be executed leading to the marking m′ obtained from m throught the accumulated effect of all transition occurrences in U : – m′(p) = Pt∈T U (t) · (W (t, p) − W (p, t)) for all p ∈ P .
Finally, a step U is said to be max-enabled at m if it is enabled at m and there is no step U ′ that strictly contains U (meaning that U ′ 6= U and U (t) ≤ U ′(t) ′ for all transitions t) and which is also enabled at m. We denote this by m[U im . A (max-enabled) step sequence is then a sequence σ = U1 . . . Un of non-empty steps Ui such that m0 [U1i m1 · · · mn−1 [Uni mn, for some markings m1, . . . , mn of N . Then mn is said to be a reachable marking of N (under the maximally concurrent step semantics).
To conclude this preliminary section, we elaborate a bit on the choice of this particular net model. First, it should be observed that it follows from the above definitions that the semantics allows auto-concurrency , the phenomenon that a transition may be executed concurrently with itself. This approach makes it possible to use transitions for a faithful modeling of natural events like the independent (non-sequential) occurrence in vast numbers o f a biochemical reaction in a living cell. Note that the degree of auto-concurren cy of a transition can easily be controlled by a dedicated place with a fixed, say k, number of tokens connected by a self-loop with that transition implying that never more than k copies of that transition can fire simultaneously.
Activator arcs were introduced in [
L.M.F.Bertens, J.Kleijn, M.Koutny and F.J.Verbeek testing for the presence of a token in place p by transition t indicates that after a step in which t participates has been executed, p must still contain a token which precludes the occurrence in the same step of transitions that have p as an output place. A read arc is also different, but less demanding in that there must exist a way to execute sequentially (i.e., one-by-one) all t ransition occurrences in the step, without violating the read arc specification. In both cases, one can easily see that activator arcs are most permissive since they only check for the presence of a token before the step is executed (this is often referred to as a priori testing). We feel that a priori testing is more appropriate for biological applications as the ‘lookahead’ implied by the other two kin ds of test arcs is hard to imagine in reality.
Finally, we rely in this paper on maximal concurrency in the steps that are
executed which reflects the idea that execution of transitions is never delayed.
This may also be viewed as a version of time-dependent Petri n ets where all
transitions have a firing duration of 1. However, the maximal concurrency we
apply in this paper does not derive from Petri nets with time, but rather from
Petri nets with localities [
In biology, the term gradient is used to describe a gradual and directed change in
concentration of a morphogen through a group of cells, e.g., a tissue. Morphogens
are signalling molecules that cause cells in different places in the body to adopt
different fates and thereby help establish embryonic axes. Morphogens are
produced in a localized source of a tissue, the source cell(s), and emanate from this
region, forming a concentration gradient ([
The mechanisms by which the morphogen travels through a cell layer have
been the topic of some debate and are not yet fully understood. Three
mechanisms have been described, shown schematically in Figure 1: (A) diffusion
through the extracellular matrix ([
A B C
sequential ACTIVATION
TRANSFORMATION
concurrent
means of tentacle-like threads of cytoplasm, called cytone mes, connecting the
cells ([
Unfortunately, knowledge of the exact concentrations and shapes of most
gradients is limited. This is mainly due to the transient nature of morphogen
gradients and the low concentrations at which they are effective, both of which
make it difficult to visualize the morphogens ([
AP axis formation in Xenopus laevis: a case study. The AP axis
formation in Xenopus laevis takes place during the early embryonic stage of
gastrulation and ensures the development of anterior structures near the head and
posterior structures towards the tail. The process can be seen as divided into
two steps, which take place sequentially ([
During the second step, transformation, the axis is formed in the
neurectoderm by means of two mechanisms: vertical and planar signalling between
neighbouring cells ([
Modelling decisions. We have chosen cells as the elementary units in our
model to be represented as places in a Petri net. Earlier studies ([
Tokens are used to represent a certain level of concentration (see [
quantitative morphogen concentrations ([
Implementation. In the organism, gradient ratios arise passively as a consequence of physical laws. However, to accurately reflect the biological process of gradient formation underlying the spread of morphogens from cell to cell, our formal model has to compute the number of tokens passed on based on the ratio ρ. Hence the model includes explicit separate computational units for the necessary calculations. In particular, these parts of the net control the transport of tokens between places. In this way a close relation to the biological process can be maintained in one part of the net, with the underlying computations performed by a subnet in the background. At all times, the marking of the net will be consistent with biological observations of (the effect of) the gradient, i.e., the ratio is maintained and places corresponding to cells further away from the source will never have more tokens than places (cells) closer to it. Another important feature of the model is the use of concurrent steps rather than individually occurring transitions. Cells only react to their environment and have no knowledge of other cells than their immediate neighbours. Non-adjacent cells can be simultaneously involved in the transport of morphogens. This leads to an execution mode consisting of concurrent steps. Moreover, these steps are maxi8
mal to reflect that also in the net model morphogens are moved to a next cell as soon as possible. 4
Following the ideas outlined in the previous section, we will propose a formal model for the formation of a gradient.
Our assumptions regarding the biological process of gradient formation are as follows. Given is a segment of k adjacent cells with the i-th cell immediate neighbour of the (i + 1)-th cell. Morphogens can be transported only between immediate neighbours. Morphogens move from cells with higher concentration to neighbours with lower concentration, as long as their concentration ratio does not exceed a given gradient ratio 0 < ρ < 1. We assume that ρ is a rational number, i.e., ρ = MN , where M > N ≥ 1. Initially, the first cell x1 contains a quantity (has concentration level) K of a morphogen. These assumptions lead to the following modelling problem.
Given are k ≥ 1 places x1, . . . , xk, representing a segment of k cells with place xi corresponding to the i-th cell. In the initial marking m0, the first place x1 contains K tokens and there are no tokens in the other places.
In the net modelling the mechanism of gradient formation, we need to shift tokens from x1 in the direction of the last place xk. Places and/or transitions may be added, but in such a way that for any reachable marking m the following hold. 1. The number of tokens in the xi’s remains constant, i.e., m(x1) + · · · + m(xk) = K token preservation 2. The tokens are distributed monotonically along the sequence of k places, i.e., m(x1) ≥ . . . ≥ m(xk) monotonicity 3. The ratio of the numbers of tokens in two neighbouring places does not exceed ρ, i.e., for every 1 ≤ i < k with m(xi) ≥ 1: mm(x(xi+i)1) ≤ ρ mm(x(xi+i)1−)+11 > ρ 4. Shifting continues until moving even one token would violate the above, i.e., if no tokens are shifted after marking m was reached, then for every 1 ≤ i < k with m(xi) > 1: Moreover, the relative position of a place within the sequence plays no role. In particular, the mechanism should be easily scalable and insensitive to the specific values of k and K. ⊓⊔ ratio termination
If we look at the above formulation of properties (2) and (3) — monotonicity and preservation of the gradient ratio — and recall that ρ = MN and M > N , it is easy to observe that these two properties are together equivalent to stating that, for every 1 ≤ i < k, N ·m(xi) − M ·m(xi+1) ≥ 0. We will call a marking m satisfying this inequality consistent and denote αi =df N ·m(xi) − M ·m(xi+1), for every 1 ≤ i < k. Note that the initial marking is consistent.
Similarly, if we look at the above formulation of properties (2) and (4) — monotonicity and termination — it is easy to observe that tog ether they are equivalent to the statement that, for every 1 ≤ i < k, N ·m(xi) − M ·m(xi+1) < M + N . We will call a consistent marking m satisfying this inequality stable. Note that for a given ρ, k and K, there may be more than one stable marking. For example, if ρ = 12 , k = 5 and K = 111, then the following are two different stable markings: We are now ready to propose a generic solution for the above problem. For a given consistent marking m and each 1 ≤ i < k, move βi tokens from xi to xi+1 where βi ≤ j Mα+iN k, and at least one βi must be non-zero if at least one of the values j αi k is non-zero. We denote the resulting marking by mβ1...βk−1.
M+N
An intuitive reason for proposing such a mechanism for shifting tokens is that the number of tokens in xi that are ‘balanced’ by tokens in xi+1 is MN ·m(xi+1), because each token in xi+1 is equivalent to MN tokens in xi. Hence there are m(xi) − MN ·m(xi+1) unbalanced tokens in xi. The ‘portion’ of each unbalanced N token that could be safely transferred to xi+1 is M+N . Hence in total we may safely transfer j MN+N ·(m(xi) − MN ·m(xi+1))k tokens, which is precisely j Mα+iN k tokens. Clearly, some of the numbers β1, . . . , βk−1 can be zero, and by the condition above, all βi’s are zeros if and only if the marking is stable: Proposition 1. β1 = · · · = βk−1 = 0 if and only if m is stable.
Crucially, by the mechanism proposed consistent markings are always transformed into consistent markings.
Proposition 2. If m is a consistent marking then mβ1...βk−1 is also consistent.
According to the above, any number of tokens not exceeding j αi k can be M+N moved simultaneously from xi to xi+1 (for every i < k), and consistency will be preserved. Clearly, the new consistent marking is different from the previous one if and only if, for at least one i, we have βi ≥ 1. The idea now is to keep changing the marking on x1, . . . , xk until a marking m has been reached such that j Mα+iN k = 0, for all 1 ≤ i < k, which is equivalent to αi < M + N , for all 1 ≤ i < k. In other words, this m is a stable marking. Since tokens cannot 10
be shifted forever, this procedure will always terminate in a stable marking (formally, we can show this by considering a weighted distance to the end of the chain of the K tokens; it never increases and always decreases in a non-sta ble state).
Looking now from the point of view of a Petri net implementation of the proposed mechanism, what we are after is a net Nshift comprising the places x1, . . . , xk and such that if m is a marking of Nshift whose projection on these k places is consistent, then a step U can occur at m if – it moves at most j αi k tokens from xi to xi+1, for all 1 ≤ i < k;
M+N – at least one token is moved from xi to xi+1 for at least one 1 ≤ i < k, unless the projection of m onto x1, . . . , xk is stable.
In fact, in the proposed implementation, we will be preceding the t‘oken-shifting’ with a p‘re-processing’ stage which seems to be unavoidable unless one uses some kind of arcs with complex weights depending on the current net marking. Implementation. In the implementation of the proposed shifting mechanism, as many tokens as possible should be shifted from one neighbour to the next. That means that, at each stage we have, for every 1 ≤ i < k, βi = j Mα+iN k. Moreover, tokens are shifted from a place without any assumptions whether new tokens will come to that place from its other neighbour. Thus we need to provide a Petri net structure capable of c‘alculating’ the value of e xpressions like N ·m(xi) − M ·m(xi+1)
M + N .
Our proposed gradient forming mechanism distinguishes three phases: I, II and III. An auxiliary net N3phase , shown in Figure 2(b), is used to schedule the transitions implementing the calculations. It controls these transitions via the places wI and wII and activator arcs. For the full picture of the system one should combine the figures for all pairs (xi, xi+1) with a single copy of the net in Figure 2(b). Note that all places with identical label (in particular wI , wII , and wIII ) should be identified. That other parts of the encompassing net model do not interfere with the calculations carried out during phases I and II can be ensured by connecting the relevant transitions with the place wIII using activator arcs.
For every 1 ≤ i < k, transition ti is intended to shift tokens from xi to xi+1 (phase III). To achieve this, we use two disjoint sets of new, auxiliary places, x′1, . . . , x′k and x′1′, . . . , x′k′. These places are initially empty. The idea is to fill x′i ′′ with N ·m(xi) tokens and xi+1 with M ·m(xi+1) tokens (phase I). The latter are used for the removal of M ·m(xi+1) tokens from x′i (phase II). After this, there are αi tokens remaining in xi. Finally, for each group of N + M tokens in x′i, one ′ token is shifted from xi to xi+1. The construction (for xi and xi+1) is shown in Figure 2(a).
The overall mechanism operates in cycles of three consecutive, maximally concurrent steps such that for every 1 ≤ i < k:
Modelling Gradients Using Petri Nets 11 wI wI e′i c′i xi
N x′i wII di ti M+N wIII x′i′+1
M (a) e′i′+1 c′i′+1 xi+1 wI wI wII
wIII wI (b) Fig. 2. (a) The main part of the construction for the solution (note that e′i′+1 is introduced for later use when one might want to remove or add tokens to the xis’ from o‘utside;’ in the standard (consistent) situation it is nev er activated as after phase 2, place x′i′+1 is empty.); and (b) the subnet N3phase enforcing the three phases.
I. Transition c′i, inserts (in m(xi) auto-concurrent occurences) N ·m(xi) tokens into x′i. In the same step, transition c′i′+1, inserts (in m(xi) auto-concurrent occurences) M ·m(xi+1) tokens into xi+1. Simultaneously, transitions e′i and ′′ e′i′+1 empty x′i and x′i′+1 of any residual tokens left from the previous cycle. ′′ II. Next, transition di (in M ·m(xi+1) auto-concurrent occurences) empties xi+1 and leaves in x′i the difference αi = N ·m(xi) − M ·m(xi+1).
III. In the third step, the occurrences of transition ti transfer βi = j αi k M+N tokens from xi to xi+1.
Proposition 3. Each cycle results in transferring βi tokens from xi to xi+1.
Note that in this implementation with the control net N3phase , neighbouring pairs are either all involved in calculations (step 1 and 2 of the cycle) or tokens are transferred between neighbours (step 3). During the whole operation of the adjustment process (except for the transfer phase), the token counts in the places xi representing the cells are unchanged and they can be accessed for reading by other transitions (and thus influence neighbouring cells). In other words, calculations are orthogonal to the basic operation of the net (the gradient formation).
As an example, let us consider the case when ρ = 12 , k = 4 and K = 100. Then executing the constructed net in a maximally concurrent manner leads to the following sequence of markings on the xi after each cycle and eventually to a stable marking: x1 100 67 67 60 60 57 57 56 56 55 54 x2 0 33 22 29 25 28 26 27 26 25 26 x3 0 0 11 8 12 10 12 12 13 12 12 x4 0 0 0 3 3 5 5 5 5 6 6 12
The next example shows what happens if we start from a (non-in itial) consistent marking (again ρ = 12 ):
The construction works without any problems, if we start with a consistent marking. In case 0 > αi for some i, then transition ti is not executed, but the transitions ti−1 and ti+1 may still be executed and lead to an adjustment of the marking causing ti to become active in the next cycle. A further observation is that adding (or removing) tokens at some point, will trigger a re-adjustment process which tries to re-establish the correct ratios betw een the markings of adjacent places xi. This process is unpredictable, but to deal with that case ′′ we have included transition ei+1 which in the standard (consistent) situation is ′′ never activated since then, after phase 2, place xi+1 is empty.
An important characteristics of the proposed solution is that it is purely local and does not assume anything about the number of tokens which may appear in the xis’ nor the length of the chain. In other words, it is truly gene ric. Whats’ more it also works if M and N are different for different pairs of neighbouring places, i.e., if rather than a uniform gradient ratio ρ there is a ratio ρi for each pair of neighbours xi and xi+1.
Another feature of our solution is the maximal concurrency semantics intended to reflect the idea of morphogens (simultaneously) moving from cell to neighbouring cell whenever that is possible. The preliminary sequential semantics model we developed (but not reproduced here) is more complicated as it also needs inhibitor arcs which test for absence of tokens (to decide whether or not tokens should still be shifted). Moreover, one needs to decide that xi either receives or sends tokens at each stage. In a step model it can both receive and send. Also, with the maximal concurrency semantics, the number of states of the model is dramatically reduced.
The auxiliary net N3phase is used to partly sequentialize the behaviour in order to separate the pre-processing phases from the actual shift ing phase. This net could also have been made local to the subnet in Figure 2(a), with different copies of it assigned to different localities. This would have given the additional possibility of controlling the degree of synchronisation between different parts of the gradient model by using a locally maximal step semantics.
Finally, we would like to point out that the activator arcs in our implementation are used only to control the calculation and can actually be avoided in case there would be a limit on the number of tokens in each place xi at any time. (Then the activator arcs can be eliminated basically by having separate copies of N3phase for each 1 ≤ i < k, transfer around sufficiently many tokens in a bundle, and replace activator arcs by self-loops). This assumption corresponds to having (or knowing) some capacity bound on the concentration levels of morphogens in a cell and so may be biologically sound!
5
Starting from gradient formation in the AP axis development in the model organism Xenopus laevis, we have presented a novel approach to using Petri nets in developmental biology by focusing on the cellular rather than subcellular levels and abstracting from concrete proteins and genes. This has led to a parameterized Petri net model for the general process of gradient formation through diffusion and endocytosis.
Assumptions regarding gradient formation have been formulated based on
essential features of this process as reported in the literature. These assumptions
underlie the precise requirements given that should be satisfied by an abstract
Petri net model of gradient formation. A crucial point here is the consistency
that is maintained during the execution of the model. Hence the realization
of the gradient is faithfully reflected. Moreover the close relationship between
biological process and evolution of the formal model makes it possible to apply
existing Petri net techniques to analyse what happens during gradient formation.
In particular cause-effect relations should be properly refl ected in the process
semantics of the modelling Petri net ([
Another main contribution of this approach is its generic nature, leading to a model that is scalable and applicable to a plethora of specific gradients. Also scalability is a consequence of the faithful reflection of the biological process. Since the final token (morphogen) distribution is not directly computed from the initial amount of morphogen and the length of the chain of cells, but rather simulates the communication between neighbouring cells, the length plays no role in the occurrence of the steps. The model as presented here represents a one-morphogen system without relying on quantitative data , but exact values could be assigned to ratio and individual tokens. Moreover, it provides a basis for simulation of simultaneous gradient formation (different morphogens with different experimental initial markings) and for inhibiting/activating interactions between them. Simulation with actual biological data to validate the model should be a next step. In addition, we will focus our attention on the extension of this still rather basic model to more dimensions, e.g., rather than having just a single line of cells, we consider the spread of morphogens from a source throughout a tissue plane or volume.
In [
expected to be particularly suitable not only in this ‘verti cal’ linking processes, but also for the ‘horizontal’ connections between processe s taking place on the same cellular level. Having molecules or genes as places would result in specific net models for certain processes, as would taking tissue structures, such as the neurectoderm. Cells however can play a role in different processes simultaneously.
The next step in the modelling of the AP axis development in Xenopus laevis will focus on the vertical signalling (see Figure 1). This process occurs concurrently with the planar signalling of gradient formation and involves the same cells. This will challenge us to explore further the possibilities of Petri nets as a model for concurrent and independent processes in high level developmental biology.
Acknowledgments We are grateful to all referees for their remarks and suggestions which helped us to improve the paper. We would like to express also our appreciation to A.Durston and H.Jansen for discussing Xenopus biology.