A coloured Petri net approach for spatial Biomodel Engineering based on the modular model composition framework Biomodelkit Mary Ann Blätke1ú and Christian Rohr2ú 1 Otto-von-Guericke University Magdeburg, Chair of Regulatory Biology Universitätsplatz 2, D-39106 Magdeburg, Germany mary-ann.blaetke@ovgu.de http://www.regulationsbiologie.de/ 2 Brandenburg University of Technology Cottbus-Senftenberg, Chair of Data Structures and Software Dependability, Postbox 10 13 44, D-03013 Cottbus, Germany, christian.rohr@b-tu.de, http://www-dssz.informatik.tu-cottbus.de Abstract. Systems and synthetic biology require multiscale biomodel engineering approaches to integrate diverse spatial and temporal scales in order to understand and describe the various interactions in biological systems. Our BioModelKit framework for modular biomodel engineering allows to compose multiscale models from a set of modules, each describ- ing an individual molecular component in the form of a Petri net. In this framework, we do now propose a feature for spatial modelling of molec- ular biosystems. Our spatial modelling methodology allows to represent the local positioning and movement of individual molecular components represented as modules. In the spatial model, interactions between com- ponents are restricted by their local positions. In this context, we use coloured Petri nets to scale the modular composed spatial model, such that each molecular component can exist in an arbitrary number of in- stances. Thus, a modular composed spatial model can be mapped to the cellular arrangement and different cell geometries. Keywords: Modular Model Composition, Spatial Modelling, Multiscale Biomodel Engineering, Coloured Petri nets 1 Introduction Systems biology aims at describing and understanding complex biological pro- cesses on a systems level. Therefore, systems biology employs modelling and simulation as indispensable tools to describe, predict and understand biological systems in an integrative and quantitative context. Besides complex interactions, ú Corresponding authors M Heiner, AK Wagler (Eds.): BioPPN 2015, a satellite event of PETRI NETS 2015, CEUR Workshop Proceedings Vol. 1373, 2015. 38 MA Blätke, C Rohr models do also need to integrate diverse temporal and spatial scales spanning the biological systems. Multiscale biomodel engineering goes beyond standard modelling approaches in systems biology and addresses physical problems as im- portant features at multiple scales in time and space [1]. Current challenges and methodologies used so far in multiscale biomodel engineering have been reviewed in [2] and [3]. Here, we focus on the spatial aspects in multiscale biomodel engineering, which have been mostly neglected in the description of intracellular processes until now [1]. In particular, we demonstrate, based on the BioModelKit frame- work for modular biomodel engineering [4], how to extend plain models of intra- cellular processes to spatial models without their reimplementation. The models in our case are composed from modules, where each module describes the func- tionality of a certain molecular component in the form of a Petri net. The use of coloured Petri nets in our approach allows to represent different numbers of module instances for each component. To our knowledge, the methodology for spatial modelling in the context of modular model composition, which we suggest in this paper, is unique. As modelling tool, we chose Snoopy [5], because it supports low-level and coloured Petri net network classes, as well as the concept of logical (fusion) nodes and hierarchical modelling. In the next section, we will shortly describe the BioModelKit framework and summarize the use of coloured Petri nets for multiscale modelling. Afterwards, in Section 3, we introduce our spatial modelling methodology as a new feature of the BioModelKit framework. Section 4 applies the introduced methodology for spatial modelling to a simple example of a molecular interaction between two proteins represented as modules. In the last section, we give a short summary and outlook. 2 Previous Work 2.1 BioModelKit Framework for Modular Model Composition The BioModelKit framework (BMK framework) is a tool for modular biomodel engineering [4], see Fig. 1. The main motivation behind BMK framework was to develop a modelling environment, where modules are specifically designed for the purpose of model composition. The modularisation approach used in BMK framework was inspired by the natural composition of biomolecular systems, where molecular components (genes, mRNAs and proteins) are the main build- ing blocks. Thus, each molecular component is represented as a self-contained module, describing the underlying functionality using the formal language of Petri nets. Interface networks, which are part of each module describe the inter- actions with other molecular components and are used to automatically couple respective modules [4]. Since, the functionality of genes, mRNAs and proteins is diverse, different module types have been defined in BMK framework, as well as allelic influence Proc. BioPPN 2015, a satellite event of PETRI NETS 2015 Spatial modelling based on modular modelling 39 Model-based Biomolecular Systems Predictions ... Molecular Experimental Boolean SBML Mechanisms Data Networks Models Forward Reverse Transformation Transformation Engineering Engineering High-Throughput Analysis Modules Gene mRNA Protein Protein Causal Allelic Modules Modules Modules Degrdation Influence Influence Modules Modules Modules Model Composition Upload Wildtype/ Add Modules to Collection + Algorithmic Mutation Alternative Biomodelkit Set of Database Modules Models + Space-Attributes Spatial Models Fig. 1: Overview of the BioModelKit Framework for Modular Model Composi- tion. modules and causal influence modules to capture also correlations with missing mechanistic descriptions [6,7]. Modules can be generated by forward and reverse engineering approaches or by transforming boolean models or models provided in the systems biology markup language (SBML) into modules [8,9], see Fig. 1. The web-interface of BMK framework (www.biomodelkit.com [4]) includes a feature to submit modules and to create a model annotation file in the BMK markup language (BMKml, unpublished work). The submitted module and its annotation have to be curated by an administrator before publicly releasing them by storing their content in a relational MySQL database (BMKdb). Another feature of the BMK framework is a model composition algorithm, which allows to automatically compose comprehensive models from a set of chosen modules. In addition, the composed model can also be modified by applying algorithms mimicking single/double gene knock-outs or structural mutations of the included molecular components (unpublished work). Proc. BioPPN 2015, a satellite event of PETRI NETS 2015 40 MA Blätke, C Rohr 2.2 Coloured Petri Nets We use Petri nets (PN ) as modelling paradigm, which gives us a complete formalised and standardised framework, as well as an intuitive way of modelling concurrent behaviour. In systems biology, as well as in other fields, it’s quite common that parts of larger models have similar structures. In such a case simplifying the model via reusing that part, instead of having redundant structures is demanded. Coloured Petri nets (PN C ) are a modelling paradigm that fits well in such a case. We are using Snoopy [10] as modelling and simulation tool, thus we describe PN C how they are defined there. coloursets: enum species := red, green, blue product complex := species, species variables: species x species y species 2‘red++ 1‘green species 2‘red x x A A complex (x,y) complex (x,y) 1‘(green,blue) y [x<>y] AB [x<>y] AB y species species 2‘green++ 2‘green B 1‘blue B (a) Before Firing (b) After Firing Fig. 2: Example PN C of abstract complex formation. We use the coloured Petri net in Fig. 2 as an example. It represents an ab- stract complex formation of two species of different kind into one complex. The model contains two coloursets, first a simple colourset named species of type enum, including the colours red, green and blue. Second a product colourset named complex, its colours are 2-tuples of the species colourset. The net consists of three places A, B and AB and one transition. The colourset species is asso- ciated with the places A and B and the place AB has colourset complex. The variables x and y are used in the arc inscriptions and the transition guard. The transition guard x <> y determines that only tokens of different colour are valid bindings for the variables x and y. The arc inscriptions x and y on the incoming We summarize the following net classes together under the term Petri net (PN ): Qualitative Petri net (QPN ), eXtended Petri net (X PN ), Continuous Petri net (CPN ), Stochastic Petri net (SPN ) and Hybrid Petri net (HPN ). The same goes for the coloured Petri nets (PN C ). Proc. BioPPN 2015, a satellite event of PETRI NETS 2015 Spatial modelling based on modular modelling 41 arcs of the transition define its precondition, i.e. there have to be at least one token on place A and one token on place B and they have to be of different colour due to the guard. The arc inscription (x, y) on the outgoing arc of the transition defines the production of one complex token. In Fig. 2a the place A has two tokens of colour red and one token of colour green and the place B has two tokens of colour green and one token of colour blue. This gives the following bindings for the variables x and y: (red, green), (red, blue), (green, blue). We se- lected the binding (green, blue) and let the transition fire. One green token from place A and one blue token from place B are consumed and one (green, blue) token is produced on place AB, see Fig. 2b. Much more extensive descriptions how to use coloured Petri nets in systems biology are given in [11,12,13]. Besides the animation of the coloured Petri net, it is possible to unfold every PN C into an uncoloured PN [11]. So it is possible to apply any analysis and simulation technique available for uncoloured Petri nets on coloured Petri nets too. Up to this, modelling biochemical systems using coloured Petri nets did not incorporate spatial aspects or movement in space. But this can be included in the model as shown by Gilbert et al. [14]. Therefore the space is discretised into a grid of one, two or three dimensions and a position in the grid is represented by a single place. This works fine if there is no need to distinguish between the entities on each position. One can model the diffusion of substances using this approach quite well, as presented in [14]. This can be extended to more complex reaction-diffusion systems, as shown in [15]. More examples of using coloured Petri nets for modelling of biological systems including spatial aspects are [16,17]. All models above have in common that they model space by discretisation into a grid and having one subnet (ranging from a single place to a complex network) per grid position. This is handy, if the entities moving around have no internal behaviour or state and there is no need to distinguish them. But if that is the case, the internal network has to move around as well and this leads to some issues on modelling and simulation. Parvu et al. [17] used this approach for a model of phase variation in bacterial colony growth. The bacteria have two different states, i.e. two places A and B representing the two states and two transitions for changing the state are needed. In order to let the bacteria move around, the whole subnet is needed in every grid position. Incorporating this in the coloured model is straightforward, but the size of the unfolded model increases drastically. This has an impact on the analysis and simulation of the model and may lead to inconvenient run times. While the approaches of representing space via discretisation into grid-places fit well in the shown cases, it is not practical in our use case, because we have complex subnets moving around. We present our approach of incorporating space by adding coordinate places in the following section. Proc. BioPPN 2015, a satellite event of PETRI NETS 2015 42 MA Blätke, C Rohr 3 Spatial Modelling Methodology for Modular Composed Models Before we start with the formal description of the spatial transformation al- gorithm, we have to introduce some general definitions which apply to our modular modelling approach. A module Mi is defined by a quintuple Mi = (Pi , Ti , fi , vi , m0,i ) according to the general definition of quantitative Petri nets. Each module Mi consists of nci + 1 components, the main component C0 and nci interacting components. Thus, each module Mi represents a set of compo- nents Ci = {C0 , C1 , . . . , Cnci }. The mapping of a place pij œ Pi of a module pi Mi to a set of components Ci j ™ Ci is given by the relation g : Pi æ Ci , pi such that g(pij ) = Ci j . A place pij with |g(pij )| > 1 represents a complex pi of |g(pij )| components. The set Ki = {Ci j | |g(pij )| > 1} contains all com- plexes among the components in Ci . A transition tij œ Ti of a module Mi with |g(•tij ) fl g(tij •)| > 1 represents an interaction with at least two different involved components. The total set of all interacting transitions in a Module Mi is given by TiIA = {’tij œ Ti : |g(•tij ) fl g(tij •)| > 1}. A set of modules defines a modular composed model M = {M1 , . . . , Mn }, where n is the number of modules. Consequently, the modular composed model can also be defined as M = (P M , T M , f M , v M , mM 0 ) according to the general definition of quantitative Petri nets with the following relations: t – P M = t Pi , where Mi œ M - total finite and non-empty set of places. – T M = t Ti , where Mi œ M - total finite and non-empty set of transitions. – f M = fi , where Mi œ M - total set of directed arcs, weighted by a non- negative t integer value. – v M :t Ti æ H, where Mi œ M - total set of firing rates. – mM 0 Pi æ N0 , ÷pikÕ , pjkÕÕ with pikÕ œ Pi , pjkÕÕ œ Pj , where pkÕ = pjkÕÕ , {pikÕ : pjkÕÕ } æ pM i k œP M , mM 0 (pk ) = max(m0,i (pkÕ ), m0,j (pkÕÕ )) M i j In addition to the definitions above, the following relations can be derived: t – CM = t Ci ,twhere Mi œ M - total set of components – g M : Pi æ tCi , where Mi œ M - total set of place component relations – TIA M ™ TtM = TiIA , where Mi œ M - total set of all interacting transitions – K M = Ki , where Mi œ M - total set of complexes. Spatial Transformation Algorithm For the spatial transformation of the flat modular composed model the following procedure needs to be executed. Step 1: Explicit Encoding of Local Positions. The position of each component Ci œ C M is explicitly encoded by d places pC 1 , . . . pd (termed coordinate places), i Ci which can be interpreted as coordinates, where d, d Ø 1, defines the number of axes (e.g. 1D, 2D or 3D grid). The marking m(pC j ) of a place pj defines the i Ci current coordinate value, which must be restricted by a lower mL (pC j ) and i Proc. BioPPN 2015, a satellite event of PETRI NETS 2015 Spatial modelling based on modular modelling 43 upper bound mU (pC j ) to represent the boundaries of the encoded grid, such i that, mL/U (pj ) > 0 and mL (pC Ci j ) < mU (pj ). i Ci Step 2: Local Restriction of Interactions. To restrict the executability of each transition t œ TIAM , the firing rate h(t) must be multiplied by a boolean relation b(t) describing a defined neighbourhood relation: hIA (t) = b(t) ú h(t), t œ TIA M . If the neighbourhood relation claims that the distance between components in- volved in the interaction represented by a transition t œ TIA M must be zero, b(t) has to I be defined as follows: q|g(•t)fig(t•)|≠1 q|g(•tfig(t•)| qd Cj 2 1, k=1 (m(pk ) ≠ m(pk )) = 0 Ci b(t) = qi=1 qj=i+1 q Cj 2 0, k=1 (m(pk ) ≠ m(pk )) ”= 0 |g(•t)fig(t•)|≠1 |g(•t)fig(t•)| d Ci i=1 j=i+1 In addition, read edges, connecting each transition t œ TIA M and the coordinate places of the respective components have to be added, such that fReadEdge (p1≠d , t) = 1. g(•t)fig(t•) Step 3: Explicit Encoding of Local Position Changes. To encode the position changes for a component Ci œ C M two different scenarios have to be considered dependent on the state of interaction: 1. Local position change of individual components: For each component Ci œ CM and each coordinate place pC Ci Ci j œ {p1 , . . . , pd } i two transitions tj,L and tj,U are needed to incrementally decrease or increase Ci Ci the amount of tokens. The transition tC j,L subtracts tokens from the coordi- i nate place pj till m(pj ) = mL (pj ). Therefore, the following edges have Ci Ci Ci to be introduced f M (pC j , tj,L ) = 1 and fReadEdge (pj , tj,L ) = mL (pj ) + 1. i Ci M Ci Ci Ci The transition tj,U adds tokens to the coordinate place pj till m(pC Ci Ci j ) = i mU (pCj ). Therefore, the following edges have to be introduced i f (tj,U , pC M Ci j ) = 1 and fInhibitorEdge (pj , tj,U ) = mU (pj ). To ensure that i M Ci Ci Ci the position of the component Ci can only be changed if it does not in- teract with another component Cj , i ”= j, additional inhibitory edges for each transition tCj,L/U have to be introduced: fInhibitorEdge (PIS , tj,L/U ) = 1, i Ci Ci where PIS Ci ™ P M and PIS Ci = {’p œ P M : Ci œ g(p) · |g(p)| > 1}. 2. Local position change of complexes: The local position of components forming a complex ki œ K M have to be updated consistently during the local position change. For each complex ki œ K M and each dimension j, 1 Æ j Æ d, two transitions tkj,L i and tkj,U i are needed to incrementally decrease or increase the amount of t tokens. The tran- sition tkj,L i removes tokens from the set of coordinate places Ch œki pC j till at h least for one component Ch œ C the condition m(pj ) = mL (pj ) is ful- M Ch Ch filled. Therefore, for each component Ch œ ki the following edges have to be introduced f M (pC j , tj,L ) = 1 and fReadEdge (pj , tj,L ) = mL (pj ) + 1. The h ki M C h ki Ch t transition tj,U adds tokens to the set of coordinate places Ch œki pC ki j h till at least for one component Ch œ C the condition m(pj ) = mU (pj ) is ful- M Ch Ch filled. Therefore, for each component Ch œ ki the following edges have to be Proc. BioPPN 2015, a satellite event of PETRI NETS 2015 44 MA Blätke, C Rohr introduced f M (tkj,U i j ) = 1 and fInhibitorEdge (pj , tj,U ) = mU (pj ). To , pC h M Ch ki Ch ensure that the position of the complex ki can only be changed if it is actually formed additional read edges for each transition tkj,L/U i have to be introduced: fReadEdge (PIS , tj,L/U ) ki ki = 1, where ki PIS ™ PM and ki PIS = {’p œ P M | ki = g(p)}. Furthermore, it must be excluded for each component Ch œ ki that interacts with other components using a different binding site. Therefore, all co-existing interactions have to be determined ki Kcoex = {’kj œ K M : ki fl kj ”= ? | kj ”= ki }. All places representing a complex kj œ Kcoex ki have to be added to each transition tkj,L/U i using an inhibitory edge: fInhibitoryEdge (PCOEX ki , tkj,L/U i ) = 1, where PCOEX ki = {’p œ P : g(p) = k, k œ Kcoex }. M ki To allow the movement of co-existing complexes which use different interac- tion sites simultaneously, the above described procedure has to be applied to all possible combination of co-existing complexes, compare Section 4. For simplicity reasons the firing rate of each transition tkj,L/U i and tC h j,L/U is given by Fick’s laws of diffusion [18]. Furthermore, we assume equidistant subvolumes with the width and hight h = 1 and set all diffusion coefficient to one. Please note, it is straightforward to define the diffusion coefficients more precisely based on experimental results. Step 4: Encoding of Component Instances by Applying Coloured Petri nets. A colourset ‡C simple i with 1 ≠ qCi colours needs to be specified for each component Ci œ C , where qCi œ N defines the number of instances for a component Ci . M The total set of simple coloursets is given by À simple = {‡Csimple 1 simple , . . . , ‡|C M | }. For each ‡C simple i œ À simple a variable aCi needs to be specified. All edges f (p, t) and f (t, p) of the flat model M for which it is true, that a component Ci œ CM , where Ci œ g(p) and |g(p)| = 1 are extended to the multiset expression aCi ‘f (p, t), or respectively aCi ‘f (t, p). The total set of simple coloursets À simple is mapped to a subset of places according to the relation S simple : À simple æ P M , such that S simple (‡C simple i ) = {p œ P M | Ci œ g(p) · |g(p)| = 1}. Each complex ki œ K , where ki represents a subset of components, such M that ki ™ C r , is represented M by a compound colourset of type product compound ‡ ki = Cj œki ‡C simple j . The total set of compound coloursets is given by À compound = {‡kcompound 1 compound , . . . , ‡|K M| }. The total set of compound coloursets À compound is mapped to remaining subset of places according to the relation S compound : À compound æ P M, such that S (‡ki compound compound ) = {p œ P | ki = g(p)}. All edges f (p, t) and f (t, p) of M the flat model M for which its is true, that a t complex ki œ K M , where ki = g(p) are extended to the multiset expression Cj œki aCj ‘f (p, t), or respectively t Cj œki a ‘f (p, t). The marking and firing rates are kept constant over all place Cj and transition instances, such that marking of each place p œ P M is represented Proc. BioPPN 2015, a satellite event of PETRI NETS 2015 Spatial modelling based on modular modelling 45 by all()‘m0 (p) and the firing rates of each transition t œ T M all()‘h(t), where all() is a function that extracts all instances of a coloured node. 4 Example For demonstration purposes we introduce in Fig. 3 a running example of a mod- ular composed model, which consists of two modules, a module for Protein A and a module for Protein B. The module of Protein A describes the complex for- mation and cleavage between the two ligand binding domains of Protein A and Protein B (P roteinA_LBD, P roteinB_LBD). The formation of the complex be- tween Protein A and Protein B (P roteinA_LBD__P roteinB_LBD) is the trig- ger for the phosphorylation of a tyrosine residue at Protein B (P roteinB_T Y R, P roteinB_T Y Rp). To phosphorylate Protein B, the catalytic domain of Protein A needs to be in an active state (P roteinA_CD_active). The catalytic domain of Protein A can switch between being active or inactive (P roteinA_CD_active, P roteinA_CD_inactive). In the module of Protein B, the subnet describing the interaction between Protein A and Protein B is redundant. Redundant subnets are called interface networks (indicated by logical (fusion) places and transitions shaded in grey), and are used to automatically couple modules. An additional subnet in the module of Protein B explains the complex formation and cleavage between the phosphorylated Tyrosine of Protein B (P roteinB_T Y Rp) and a SH2 domain of Protein C (P roteinC_SH2). The Module of Protein C is not given in this example. Since this paper is not dealing with kinetic aspects, we assume mass action kinetics and set all kinetic coefficient to one. It is straightforward to replace this assumption with more detailed kinetic descriptions. Module of Protein A Module of Protein B ProteinA LBD ProteinA LBD ProteinB LBD ProteinB LBD AB t1 AB t2 AB t1 AB t2 ProteinA LBD ProteinB LBD ProteinA LBD ProteinB LBD BC t1 AB t3 AB t3 ProteinB TYRp ProteinB TYR ProteinB TYRp ProteinC SH2 ProteinC SH2 ProteinB TYR ProteinB TYRp ProteinA CD active ProteinA CD active BC t2 A t2 A t1 ProteinA CD inactive Fig. 3: Running example with two protein modules. The module of Protein A (M1 ) contains two components C1 = { P roteinA, P roteinB } and the module of Protein B (M2 ) contains three Proc. BioPPN 2015, a satellite event of PETRI NETS 2015 46 MA Blätke, C Rohr components C2 = {P roteinA, P roteinB, P roteinC }. For the composed Model M = {M1 , M2 }, we get the following mapping of places to the components: – g M ({P roteinA_LBD, P roteinA_CD_active, P roteinA_CD_inactive}) =P roteinA – g M ({P roteinB_LBD, P roteinB_T Y R, P roteinB_T Y Rp}) =P roteinB – g M ({P roteinB_SH2}) =P roteinC – g M ({P roteinA_LBD__P roteinB_LBD}) = {P roteinA, P roteinB } – g M ({P roteinB_T Y Rp__P roteinC_SH2}) = {P roteinB, P roteinC } Furthermore places P roteinA_LBD__P roteinB_LBD and P roteinB_T Y Rp__P roteinC_SH2 represent two complexes k1 = {P roteinA, P roteinB } and k2 = {P roteinB, P roteinC }. The set of inter- acting transitions is given by TIA M = {AB_r1, AB_r2, AB_r3, BC_r1, BC_r2}. For the spatial model we assume a two dimensional grid (d = 2) of the size 5 ◊ 5 for each component given by the constants xDimA = xDimB = xDimC = 5 and yDimA = yDimB = yDimC = 5. Step 1 of the spatial transformation algorithm introduces two coordinate places representing the x- and y-coordinate of each component, e.g. for com- ponent P roteinA we add two places P roteinA_X and P roteinA_Y , see Fig. 4. We chose the marking of the places representing the local position according to the following assumption: component P roteinA is initially positioned at (1,1), component P roteinB at (3,3) and component P roteinC at (4,4). XY-Position of Protein A XY-Position of Protein B XY-Position of Protein C 4 4 ProteinA X ProteinA Y ProteinB X ProteinB Y ProteinC X ProteinC Y Fig. 4: Encoding of the local positions for each component in the composed modular model. Step 2 of the spatial transformation algorithm restricts the interaction of components dependent on their local position. The restriction applies only to transitions in the set TIAM . We assume that components can only interact, if their local positions are identical, meaning the distance between them must be zero. Therefore, the firing rates of transitions AB_t1, AB_t2 and AB_t3 must be multiplied I with the boolean expression bAB (t): 1, distAB = 0 bAB (t) = with 0, distAB ”= 0 distAB = (m(P roteinA_X)≠m(P roteinB_X))2 +(m(P roteinA_Y )≠m(P roteinB_Y ))2 The places representing the local positions of component P roteinA and compo- nent P roteinB have to be connected by read edges to the transitions AB_t1, AB_t2 and AB_t3, compare Fig. 5. Accordingly, the firing rates of transitions BC_t1 and BC_t2 must be multiplied with the boolean expression bBC (t): Proc. BioPPN 2015, a satellite event of PETRI NETS 2015 Spatial modelling based on modular modelling 47 I 1, distBC = 0 bAB (t) = with 0, distBC ”= 0 distBC = (m(P roteinB_X)≠m(P roteinC_X))2 +(m(P roteinB_Y )≠m(P roteinC_Y ))2 . The places representing the local positions of component P roteinB and com- ponent P roteinC have to be connected by read edges to the transitions BC_t1 and BC_t2, compare Fig. 5. Restricted Interaction - Only if ProteinA (X,Y) = ProteinB (X,Y) ProteinA X ProteinB X ProteinA X ProteinB X ProteinA X ProteinB X AB t1 AB t2 AB t3 ProteinA Y ProteinB Y ProteinA Y ProteinB Y ProteinA Y ProteinB Y Restricted Interaction - Only if ProteinB (X,Y) = ProteinC (X,Y) ProteinB X 4 ProteinC X ProteinB X 4 ProteinC X BC t1 BC t2 ProteinB Y 4 ProteinC Y ProteinB Y 4 ProteinC Y Fig. 5: Restriction of interactions depending on the local position of the involved components. Step 3 of the spatial transformation algorithm encodes the local position change in respect to the interaction state of the components. In our example we assume only movement along the horizontal and vertical axes. For each axis two transitions are needed to either increase or decrease the marking value of the respective coordinate place of a component with respect to the grid size. A component can only move as a single entity if it is not interacting at the same time with other components. Therefore we have to check if the cor- responding places representing the interaction states (complexes) are empty, e.g. in case of component P roteinB it can only move as single entity if places P roteinA_LBD__P roteinB_LBD and P roteinB_T Y Rp__P roteinC_SH2 are empty, see Figure 6(A). To move components forming a complex or which build co-existing complexes, the coordinates of all involved components have to be updated simultaneously, see Figure 6(B). Form the definitions above, we know that component P roteinB can form a complex with P roteinA and P roteinC . Thus, these two complexes can co-exist because component P roteinB uses different interaction sites. To move the complex of component P roteinA and component P roteinB we need to check whether the corresponding place P roteinA_LBD__P roteinB_LBD is marked and if the place P roteinB_T Y Rp__P roteinC_SH2 is empty. In contrast, to move the complex of component P roteinB and component P roteinC we need to check whether the place P roteinB_T Y Rp__P roteinC_SH2 is marked and if place P roteinA_LBD__P roteinB_LBD is empty. And to move the co-existing com- Proc. BioPPN 2015, a satellite event of PETRI NETS 2015 48 MA Blätke, C Rohr plex of component P roteinA, component P roteinB and component P roteinC , we need to check if both places P roteinA_LBD__P roteinB_LBD and P roteinB_T Y Rp__P roteinC_SH2 are marked. Step 4 of the spatial transformation algorithm has to be applied to represent more than one instance of each component, compare Fig. 7 and 8. In our example the number of instances for each component is three, which we represent by the constants numA = numB = numC = 3. For each component Ci œ CM we define a simple colourset: – int csProteinA := 1 - numA, – int csProteinB := 1 - numB, – int csProteinC := 1 - numC where colourset csP roteinA is mapped to the places with the relation g(p) =P roteinA, colourset csP roteinB is mapped to the places with the rela- tion g(p) =P roteinB and colourset csP roteinC is mapped to the places which fulfil relation g(p) =P roteinC . The coordinate places of each component have to be bound to the respective colourset as well. Furthermore, we need to define a variable for each simple colourset: – csProteinA A – csProteinB B – csProteinC C All in-going and out-going arcs of places bound to one of the simple coloursets de- fined above have to carry the respective variable as arc expression. Since, we have two binary complexes k1 = {P roteinA, P roteinB } and k2 = {P roteinB, P roteinC }, we need to define a compound colourset for each as product of the respective simple coloursets: – product csProteinA_ProteinB := csProteinA, csProteinB – product csProteinB_ProteinC := csProteinB, csProteinC where colourset csP roteinA_P roteinB is mapped to the places with the relation g(p) = {P roteinA, P roteinB } and colourset csP roteinB_P roteinC is mapped to the places with the relation g(p) = {P roteinB, P roteinC }. All in-going and out- going arcs of places bound to one of the compound coloursets defined above have to carry a 2-tuple of respective variables as arc expression. Fig. 9 presents one exemplifying stochastic simulation run of the final spatial model of Fig. 7 and 8. In Fig. 9(A), we depict the movement of all instances of components P roteinA, P roteinB and P roteinC on separate two-dimensional grids of the size 5◊5. During the simulation time three complexes between instances of component P roteinA and component P roteinB could be obtained (P roteinA_1 + P roteinB_1,P roteinA_1+P roteinB_2,P roteinA_3+P roteinB_3), as well as two complexes between instances of component P roteinB and component P roteinC (P roteinB_1 + P roteinC_1,P roteinB_3 + P roteinC_3). The simulation result also shows that the distance between the corresponding instances of compo- nents forming a complex is zero, which means that they can only move has one entity. Subfigure (1) and (2) of Fig. 9(B) shows that the instance P roteinB1 is interacting with instance P roteinA1 and instance P roteinC1 at the same time near the end of the simulation run, thus the two complex states co-exist. Proc. BioPPN 2015, a satellite event of PETRI NETS 2015 Spatial modelling based on modular modelling 49 (A) Movement of Protein A Movement of Protein B Movement of Protein C ProteinC X ProteinA X ProteinB X XL A XR A XL B XR B XL A 4 XR A 2 xDimA 2 xDimB 2 xDimC ProteinA LBD ProteinB LBD ProteinA LBD ProteinB LBD ProteinB TYRp ProteinC SH2 ProteinB TYRp ProteinC SH2 ProteinC Y ProteinA Y ProteinB Y YD A YU A YL B YD A 4 YU A YD B 2 yDimA 2 yDimB 2 yDimC ProteinA LBD ProteinB LBD ProteinA LBD ProteinB LBD ProteinB TYRp ProteinC SH2 ProteinB TYRp ProteinC SH2 (B) Movement of complex ProteinA ProteinB Movement of complex ProteinB ProteinC Movement of complex ProteinA ProteinB ProteinC 2 xDimA ProteinA X ProteinB X ProteinB X ProteinB X 2 xDimB xDimB xDimB 2 ProteinA X ProteinC X ProteinC X XL AB XR AB XL BC 4 XR BC XL ABC 4 XR ABC 2 xDimA 2 xDimC 2 xDimC ProteinA LBD ProteinB LBD ProteinA LBD ProteinB LBD ProteinA LBD ProteinB LBD ProteinB TYRp ProteinC SH2 ProteinB TYRp ProteinC SH2 ProteinB TYRp ProteinC SH2 2 yDimA ProteinA Y ProteinB Y ProteinB Y ProteinB Y 2 yDimB yDimB yDimB 2 ProteinA Y ProteinC Y ProteinC Y YL AB YD AB YD BC 4 YU BC YD ABC 4 YU ABC 2 yDimA 2 yDimC 2 yDimC ProteinA LBD ProteinB LBD ProteinA LBD ProteinB LBD ProteinA LBD ProteinB LBD ProteinB TYRp ProteinC SH2 ProteinB TYRp ProteinC SH2 ProteinB TYRp ProteinC SH2 Fig. 6: Local position change dependent on the state of interaction. (A) compo- nents are not in complex, (B) components are in complex with each other. Proc. BioPPN 2015, a satellite event of PETRI NETS 2015 50 MA Blätke, C Rohr Module of Protein A Module of Protein B csProteinA csProteinA 1‘all() ProteinA LBD 1‘all() ProteinA LBD A A A A csProteinB ProteinB LBD 1‘all() csProteinB ProteinB LBD 1‘all() AB t1 AB t2 AB t1 AB t2 B B B B (A,B) (A,B) (A,B) (A,B) csProteinA ProteinB csProteinA ProteinB ProteinA LBD ProteinB LBD ProteinA LBD ProteinB LBD BC t1 (B,C) B AB t3 (A,B) C csProteinC AB t3 (A,B) csProteinB csProteinB csProteinB csProteinB ProteinC ProteinB TYRp ProteinB TYR 1‘all() ProteinB TYRp ProteinC SH2 ProteinC SH2 ProteinB TYR 1‘all() B B 1‘all() csProteinBB B A C B ProteinB TYRp A csProteinA (B,C) csProteinA ProteinA CD active ProteinA CD active A BC t2 A A t2 A t1 A A csProteinA ProteinA CD inactive 1‘all() XY-Position of Protein A XY-Position of Protein B XY-Position of Protein C 9 9 12 12 csProteinA csProteinA csProteinB csProteinB csProteinC csProteinC ProteinA X ProteinA Y ProteinB X ProteinB Y ProteinC X ProteinC Y 1‘all() 1‘all() 3‘all() 3‘all() 4‘all() 4‘all() Restricted Interaction - Only if ProteinA (X,Y) = ProteinB (X,Y) csProteinA csProteinB csProteinA csProteinB csProteinA csProteinB ProteinA X 9 ProteinB X ProteinA X 9 ProteinB X ProteinA X 9 ProteinB X 1‘all() AB t1 3‘all() 1‘all() AB t2 3‘all() 1‘all() AB t3 3‘all() A B A B A B A csProteinA A csProteinA A csProteinB csProteinA B csProteinB B csProteinB B ProteinA Y 9 ProteinB Y ProteinA Y 9 ProteinB Y ProteinA Y 9 ProteinB Y 1‘all() 3‘all() 1‘all() 3‘all() 1‘all() 3‘all() Restricted Interaction - Only if ProteinB (X,Y) = ProteinC (X,Y) csProteinB csProteinC csProteinB csProteinC ProteinB X 9 12 ProteinC X ProteinB X 9 12 ProteinC X 3‘all() BC t1 4‘all() BC t2 4‘all() B C 3‘all() B C B C csProteinB B C csProteinB csProteinC csProteinC ProteinB Y 9 12 ProteinC Y ProteinB Y 9 12 ProteinC Y 3‘all() 4‘all() 3‘all() 4‘all() – simple coloursets: – constants: • int ProteinA := 1 - numA • int numA := 3 • int ProteinB := 1 - numB • int numB := 3 • int ProteinB := 1 - numC • int numC := 3 – compound coloursets: • int xDimA := 5 • product ProteinA_ProteinB := Pro- • int yDimA := 5 teinA, ProteinB • int xDimB := 5 • product ProteinB_ProteinC := Pro- • int yDimB := 5 teinB, ProteinC • int xDimC := 5 – variables: • int yDimC := 5 • ProteinA A • ProteinB B Fig. 7: Part 1: Instantiation of modules using coloured Petri nets. 5 Conclusions & Outlook We presented a new approach for incorporating spatial aspects into modular composed models. A new approach was necessary, because existing techniques (see Section 2.2) are not suitable for model composition. In particular, we demon- Proc. BioPPN 2015, a satellite event of PETRI NETS 2015 Spatial modelling based on modular modelling 51 Movement of Protein A Movement of Protein B Movement of Protein C csProteinB csProteinC csProteinA ProteinC X ProteinA X ProteinB X XL A A A XL B B B XL C C C XR A 9 XR B 12 XR C 1‘all() 3‘all() 4‘all() 2‘A xDimA‘A 2‘B xDimB‘B 2‘C xDimC‘C (A,all()) (A,all()) (all(),C) (all(),C) (all(),B) (all(),B) csProteinA ProteinB csProteinB ProteinC csProteinA ProteinB ProteinA LBD ProteinB LBD ProteinA LBD ProteinB LBD ProteinB TYRp ProteinC SH2 (B,all()) (B,all()) csProteinB ProteinC ProteinB TYRp ProteinC SH2 csProteinA csProteinC csProteinB ProteinA Y ProteinB Y ProteinC Y A A B B C C YD A YU A YD B 9 YD C 12 YU C YU B 1‘all() 3‘all() 4‘all() 2‘A yDimA‘A 2‘B yDimB‘B 2‘C yDimC‘C (A,all()) (A,all()) (all(),C) (all(),C) (all(),B) (all(),B) csProteinA ProteinB csProteinA ProteinB csProteinB ProteinC ProteinA LBD ProteinB LBD ProteinA LBD ProteinB LBD ProteinB TYRp ProteinC SH2 (B,all()) (B,all()) csProteinB ProteinC ProteinB TYRp ProteinC SH2 Movement of complex ProteinAProteinB Movement of complex ProteinBProteinC Movement of complex ProteinAProteinB ProteinC csProteinA 2‘A ProteinA X xDimA‘A 1‘all() csProteinB csProteinB csProteinB ProteinB X ProteinB X ProteinB X 3‘all() A A 9 B 9 B 9 B B B B 2‘B 3‘all() 2‘B 3‘all() csProteinA xDimB‘B csProteinC xDimB‘B 2‘B csProteinC xDimB‘B ProteinA X ProteinC X ProteinC X XL AB A A XL BC C C XR BC XL ABC C C XR AB 12 12 XR ABC 1‘all() 4‘all() 4‘all() 2‘A xDimA‘A 2‘C xDimC‘C 2‘C xDimC‘C (A,B) (A,B) (all(),B) (all(),B) (A,B) (A,B) csProteinA ProteinB csProteinA ProteinB csProteinA ProteinB ProteinA LBD ProteinB LBD ProteinA LBD ProteinB LBD ProteinA LBD ProteinB LBD (B,all()) (B,all()) (B,C) (B,C) (B,C) (B,C) csProteinB ProteinC csProteinB ProteinC csProteinB ProteinC ProteinB TYRp ProteinC SH2 ProteinB TYRp ProteinC SH2 ProteinB TYRp ProteinC SH2 csProteinA 2‘A ProteinA Y yDimA‘A 1‘all() csProteinB csProteinB csProteinB A ProteinB Y ProteinB Y A ProteinB Y 9 9 9 B B 2‘B B B B B 2‘B 3‘all() yDimB‘B 3‘all() yDimB‘B 2‘B 3‘all() yDimB‘B csProteinA csProteinC csProteinC ProteinA Y ProteinC Y ProteinC Y YD AB A A YD BC C C C C YU AB 12 YU BC YD ABC 12 YU ABC 1‘all() 4‘all() 4‘all() 2‘A yDimA‘A 2‘C yDimC‘C 2‘C yDimC‘C (A,B) (A,B) (all(),B) (all(),B) (A,B) (A,B) csProteinA ProteinB csProteinA ProteinB csProteinA ProteinB ProteinA LBD ProteinB LBD ProteinA LBD ProteinB LBD ProteinA LBD ProteinB LBD (B,all()) (B,all()) (B,C) (B,C) (B,C) (B,C) csProteinB ProteinC csProteinB ProteinC csProteinB ProteinC ProteinB TYRp ProteinC SH2 ProteinB TYRp ProteinC SH2 ProteinB TYRp ProteinC SH2 Fig. 8: Part 2: Instantiation of modules using coloured Petri nets. strated based on the BioModelKit framework for modular biomodel engineer- ing [4], how to extend plain models of intracellular processes to spatial models without their reimplementation. The models in our case are composed from mod- ules, where each module describes the functionality of a certain molecular com- Proc. BioPPN 2015, a satellite event of PETRI NETS 2015 52 MA Blätke, C Rohr (A) (1) ProteinA (2) ProteinB (3) ProteinC Instanz1 Instanz1 Instanz1 5 Instanz2 5 Instanz2 5 Instanz2 Instanz3 Instanz3 Instanz3 4 4 4 3 3 3 y y y 2 2 2 1 1 1 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 x x x (B) (1) Complex of ProteinA_1 and ProteinB_1 (2) Complex of ProteinA_1 and ProteinB_2 1 4 1 4 Distance Distance Marking Marking 0.5 2 0.5 2 0 0 0 0 0 1 2 3 4 5 0 1 2 3 4 5 Time Time (3) Complex of ProteinA_3 and ProteinB_3 1 4 Distance Marking 0.5 2 0 0 0 1 2 3 4 5 Time (4) Complex of ProteinB_1 and ProteinC_1 (5) Complex of ProteinB_3 and ProteinC_3 1 4 1 4 Distance Distance Marking Marking 0.5 2 0.5 2 0 0 0 0 0 1 2 3 4 5 0 1 2 3 4 5 Time Time Fig. 9: Stochastic Simulation of the Spatial Model. ponent in the form of a Petri net. To transform a flat modular composed model into a spatial model the following steps have to be performed: (1) components have to be equipped with individual spatial attributes to represent their localisa- tion and movement in the biomolecular system, (2) components are only allowed to interact if they fulfil certain neighbourhood conditions, (3) the movement of Proc. BioPPN 2015, a satellite event of PETRI NETS 2015 Spatial modelling based on modular modelling 53 components depends on their state of interaction, e.g. interacting components forming a complex can only move as one entity. The use of coloured Petri nets in our approach allows us to represent individual numbers of module instances for each component. In our approach we use d different places per module to hold the spatial informations. The value of d is usually 1, 2 or 3 for one-, two- or three-dimensional space. The position of a module is characterized by the number of tokens on these places, e.g. ProteinA_X = 3 and ProteinA_Y = 2 is position (3,2) in two- dimensional space. Furthermore, we add transitions to each module to enable movement and interaction of modules. The structure of the non-spatial modules remains the same, while converting it into a spatial module. So it is possible to revert it back again easily. The use of places holding spatial information does not restrict our approach to discrete space, but allows us to model continuous space as well by using continuous places. This is not possible using the grid-places approach presented in Section 2.2. The whole process does not depend on the module and can be applied easily to any module of the BMKdb. Thus it fits quite well in the BMK framework presented in Section 2.1. The spatial transformation algorithm will be a new feature in the next release of the BMK online tool. Further investigation is needed in terms of simulation. Adding space surely increases the computational complexity and the question is, how can we challenge this. References 1. Heiner, M., Gilbert, D.: Biomodel engineering for multiscale systems biology. Progress in Biophysics and Molecular Biology 111(2-3) (April 2013) 119–128 2. Dada, J.O., Mendes, P.: Multi-scale modelling and simulation in systems biology. Integrative Biology 3(2) (February 2011) 86–96 3. Qu, Z., Garfinkel, A., Weiss, J.N., Nivala, M.: Multi-scale modeling in biology: How to bridge the gaps between scales? Progress in Biophysics and Molecular Biology 107(1) (October 2011) 21–31 4. Blätke, M.A., Dittrich, A., Rohr, C., Heiner, M., Schaper, F., Marwan, W.: JAK/STAT signalling–an executable model assembled from molecule-centred mod- ules demonstrating a module-oriented database concept for systems and synthetic biology. Molecular BioSystems 9(6) (2013) 1290–1307 5. Rohr, C., Marwan, W., Heiner, M.: Snoopy–a unifying Petri net framework to investigate biomolecular networks. Bioinformatics 26(7) (2010) 974–975 6. Marwan, W., Blätke, M.A.: A module-based approach to biomodel engineering with Petri nets. In: Proceedings of the 2012 Winter Simulation Conference (WSC 2012), Berlin. 978-1-4673-4781-5/12, IEEE (2012) 7. Blätke, M.A., Heiner, M., Marwan, W.: Predicting phenotype from genotype through automatically composed Petri nets. In: Proc. 10th International Con- ference on Computational Methods in Systems Biology (CMSB 2012), London. Volume 7605 of LNCS/LNBI., Springer (2012) 87–106 Proc. BioPPN 2015, a satellite event of PETRI NETS 2015 54 MA Blätke, C Rohr 8. Jehrke, L.: Modulare Modellierung und graphische Darstellung boolscher Netzw- erke mit Hilfe automatisch erzeugter Petri-Netze und ihre Simulation am Beispiel eines genregulatorischen Netzwerkes (2014) 9. Soldmann, M.: Transformation monolithischer SBML-Modelle biomolekularer Net- zwerke in Petri-Netz Module (2014) 10. Heiner, M., Herajy, M., Liu, F., Rohr, C., Schwarick, M.: Snoopy – a unifying Petri net tool. In: Proc. PETRI NETS 2012. Volume 7347 of LNCS., Springer (June 2012) 398–407 11. Liu, F.: Colored Petri Nets for Systems Biology. PhD thesis, BTU Cottbus, Dep. of CS (January 2012) 12. Liu, F., Heiner, M., Yang, M.: Colored Petri Nets for Multiscale Systems Biology – Current Modeling and Analysis Capabilities in Snoopy. In: Proc. 7th International Conference on Systems Biology (ISB 2013), IEEE (August 2013) 24 – 30 13. Liu, F., Heiner, M.: 9. In: Petri Nets for Modeling and Analyzing Biochemical Reaction Networks. Springer (2014) 245–272 14. Gilbert, D., Heiner, M., Liu, F., Saunders, N.: Colouring Space - A Coloured Framework for Spatial Modelling in Systems Biology. In Colom, J., Desel, J., eds.: Proc. PETRI NETS 2013. Volume 7927 of LNCS., Springer (June 2013) 230–249 15. Liu, F., Blätke, M., Heiner, M., Yang, M.: Modelling and simulating reac- tion–diffusion systems using coloured Petri nets. Computers in Biology and Medicine 53 (October 2014) 297–308 online July 2014. 16. Gao, Q., Gilbert, D., Heiner, M., Liu, F., Maccagnola, D., Tree, D.: Multiscale Mod- elling and Analysis of Planar Cell Polarity in the Drosophila Wing. IEEE/ACM Transactions on Computational Biology and Bioinformatics 10(2) (2013) 337–351 online 01 August 2012. 17. Parvu, O., Gilbert, D., Heiner, M., Liu, F., Saunders, N.: Modelling and Analysis of Phase Variation in Bacterial Colony Growth. In Gupta, A., Henzinger, T., eds.: Proc. CMSB 2013. Volume 8130 of LNCS/LNBI., Springer (September 2013) 78–91 18. Fick, A.: V. on liquid diffusion. Philosophical Magazine Series 4 10(63) (1855) 30–39 Proc. BioPPN 2015, a satellite event of PETRI NETS 2015