An Open Petri Net Implementation of Gene Regulatory Networks
Yanying Wu
q-bio.MN math.CT



	
	
	
	1,2]Yanying Wuyanying.wu@cncb.ox.ac.uk
	[1]Centre for Neural Circuits and Behaviour, University of Oxford, UK
	[2]Department of Physiology, Anatomy and Genetics, University of Oxford, UK
	
	An Open Petri Net Implementation 
 of Gene Regulatory Networks
    [
    July 24, 2019
==============================================================

empty
	
	
	
		Gene regulatory network (GRN) plays a central role in system biology and genomics. It provides a promising way to model and study complex biological processes. Several computational methods have been developed for the construction and analysis of GRN. In particular, Petri net and its variants were introduced for GRN years ago. On the other hand, Petri net theory itself has been rapidly advanced recently. Especially noteworthy is the combination or treatment of Petri net with the mathematical framework of category theory (categorization), which endows Petri net with the power of abstraction and
		composability. Open Petri net is a state-of-art implementation of such "categorized" Petri nets. Applying open Petri net to GRN may potentially facilitate the modeling of large scale GRNs. In this manuscript, we took a shallow step towards that direction.	
	


roman







arabic



§ INTRODUCTION
 
Human genome contains about 20,000 genes, and those genes undergo diverse expression dynamics in different tissues throughout a life from its development to ageing. In a given cell of any tissue, tens of thousands of various gene products interact with one another, forming an incredibly complicated network, to support certain living processes. Such a network is often referred to as the gene regulatory network (GRN), and it has been a hot research topic for decades in the fields of genomics and system biology.   

Many computational approaches have been developed to model GRN, such as information theory models, boolean networks, differential equations models, Bayesian networks, Petri nets and so on <cit.>. Among them, Petri nets present one of the most promising tools, as Petri nets not only excel in modelling concurrent dynamic systems, but also have a wide application community as well as a strong theoretical support <cit.>.

Standard Petri nets are able to specify clearly the structure and behaviour of a particular process. However, it's not convenient to compose larger nets from smaller ones as Petri nets suffer from a lack of compositionality and abstraction <cit.>. While complex systems such as GRN often need to abstract from internal transitions and focus on the communication behaviour between processes so that a holistic picture of the whole system could be captured. To address the question, putting Petri nets into the framework of category theory provides an optimal strategy. In fact, this line of research has been explored since 1990 and reached its climax in the recent years with the introduction and optimization of open Petri nets <cit.>.

Standard Petri nets and their variants (except open Petri nets) have been employed to model GRN for a while <cit.>. On the other hand, open Petri nets have been successfully applied in modelling electrical circuits <cit.>, Markov processes <cit.>, chemical reaction networks <cit.>, etc. However, open Petri nets haven't been used for GRN so far. Therefore, in this work we attempt to explore the possibility and potential of an open Petri nets implementation for GRNs, with the motivation of bringing a better composability to GRN modelling.



§ GENE REGULATORY NETWORKS
 
  In order to support normal cellular functions of a living organism, genes interact with each other to carry out many crucial molecular processed. These interactions usually involve a regulation of the gene expression. If a change in the expression of gene X could induce a change in the expression of gene Y, we say that gene X regulates gene Y. This regulation can be either up-regulation or down-regulation, and we call it activation or inhibition, respectively. Together, those genes and their regulations form a complex network which is referred to as gene regulatory network (GRN) <cit.>.
  
  GRN could be inferred from gene expression data through computational approaches such as ordinary differential equation, Boolean network, Bayesian network, etc. Each of those methods has its pro and con. Ordinary differential equation (ODE), as its name suggests, uses continuous variables to represent the concentrations of mRNA or protein molecules (the products of gene expression), and it uses differential equations to model the dynamics of concentration changes. Therefore, ODE suits best for an accurate analysis of non-linear features of GRN. However, it's relatively complex and the parameters for the equations are quite often unavailable in the biological reality. On the other hand, Boolean network uses boolean values to represent gene expression level as well as the relationships between genes. In a Boolean network, a gene is either on or off and the interaction between any pairs of genes is either active or inactive. Boolean network has the advantage of simplicity, while it suffers an inability to capture many important details of GRN. Probabilistic Boolean network is an extension of Boolean network which allows more than one transition Boolean functions and each of them is randomly selected during state transitions to update the target gene <cit.>. 
  
  A more sophisticated probabilistic GRN model is Bayesian network. Bayesian network combines probability and graph theory to model the qualitative properties of GRN. It depicts the GRN as a directed acyclic graph (DAG) G=(X,A), X contains a set of nodes {x_1, ..., x_n} which represent the gene variables, and A contains the directed edges which represents the probabilistic dependence interactions among genes. Bayesian network carries out the inference of network structure and parameters through belief propagation, which takes both the prior biological knowledge and the expression data into account. Bayesian network has been successfully applied to improve the quality of predicted GRN <cit.>. 
  
    


§ PETRI NET MODELLING OF GENE REGULATORY NETWORKS
 
Petri nets provide a complementary network modelling to the above mentioned traditional methods. Petri nets were introduced by C.A. Petri in 1962 to model distributed and concurrent systems <cit.>. Petri nets combine a well defined mathematical theory with a graphical representation; the former allows a precise analysis of the system behaviour, while the latter provides an intuitive visualization of the structure and state changes of the system. Due to these advantages, Petri nets have been successfully applied in modelling many kinds of dynamic systems such as computer networks, communication systems, logistic networks, etc. <cit.>

By definition, a Petri net is a bipartite directed graph containing places and transitions connected by directed arcs; arcs can only connect place to transition and vice versa. Figure <ref> shows a simple Petri net with 2 places (P1, P2) and one transition (T1).




A place can hold tokens (in Figure <ref>, P1 holds one token as denoted by a red dot inside the circle), and an arc has its capacity (1 by default, otherwise the capacity is marked on the arc), and transitions have neither capacity, nor tokens. The marking (or state) of a Petri net is its token assignments of places. When the number of tokens in each input place is equal or larger than the arc weight (capacity), a transition is able to fire. When a transition fires, the tokens in input places are transferred to the output places, resulting in a new marking of the net. Figure <ref> illustrates the firing of a transition, which reveals that the firing of a transition removes tokens from its input places and add tokens to its output places according to the capacity of the corresponding arcs. Note that tokens may disappear or appear going through a transition <cit.>. 


As the theory and methodology of Petri nets have been developed for more than 50 years, using Petri nets to model GRN will enrich our ability to analyse the dynamic properties of GRN. Several attempts have been made to model GRN using Petri nets <cit.>. Here we adopt a simple model based on <cit.> and <cit.>. In this model we draw an arrow from gene g2 to gene g1 to represent that g2 activates g1 (Figure <ref>a), and a blunt-end line from g2 to g1 will represent the inhibition of g1 by g2 (Figure <ref>a). For these two elementary GRNs we may construct the corresponding Petri nets, where genes are modelled as places, and the interaction between two genes is modelled by a transition together with directed arcs that connect the places and transitions. 






In both activation and inhibition cases, g2 may or may not be consumed. We use double sided arrow to indicate that g2 activates g1 without itself being consumed (Figure <ref>c and <ref>c), and one sided arrow otherwise (Figure <ref>b and <ref>b). For activation, we draw an arrow pointing towards g1 from transition T_g1, g2, while for inhibition, we draw the arrow the other way round. Figure <ref> and Figure <ref> also describe what happens when T_g1, g2 fires. For example, in Figure <ref>b, before firing there is a token in g2 but none in g1, while after firing the token in g2 is consumed and g1 is activated as indicated by having a token in it.

Once we have these basic building blocks, we are able to convert a normal GRN into its corresponding Petri net. For example, if we have a GRN as shown in Figure <ref>a, then the Petri net for it will look like that in Figure <ref>b.


Note that in this GRN gene A activates gene B and C, gene B activates gene D, and gene C inhibits gene D while activates gene E. Except in the case of C activating E, where C is consumed, all other transitions don't consume the source gene.

Now that we obtain the Petri net modelling of a GRN, we shall be able to simulate and analyse the dynamics of the GRN <cit.>. 



§ A CATEGORICAL TREATMENT OF PETRI NETS

Unfortunately, standard Petri net lacks proper mechanisms for composition and abstraction, which makes it inadequate to model large or multi-scale GRN. The problem can be solved by viewing Petri net from the category theory perspective, i.e., treating Petri nets as monoids (<cit.>). In order to do that, we need to introduce two definitions, following Meseguer and Montanari's work:

(1) A standard Petri net is a triple <S, T, F>, where S is a set of places, T is a set of transitions, and F: (S × T)+(T × S) →ℕ is a multiset which describes the connections between places and transitions. Here ℕ represents natural numbers, × is the Cartesian product of sets, and + denotes the disjoint union of sets. 

(2) A graph G is a set T of arcs, a set V of nodes and two functions ∂_0 and ∂_1 from T to V (∂_0, ∂_1: T → V), called source and target, respectively. A graph morphism from G to G' is a pair of functions <f, g>, f: T → T', g: V → V' such that:
g ∘∂_0 = ∂_0' ∘ f and g ∘∂_1 = ∂_1' ∘ f.

In support of their motto "Petri Nets Are Monoids", Meseguer and Montanani argued that Petri nets can be viewed as ordinary, directed graphs equipped with parallel and sequential composition of transitions <cit.>. Accordingly, they provided a new definition of Petri net:

A Petri net is a graph where the arcs in set are called transitions and where the set of nodes is the free commutative monoid S^⊕ generated by the set of places S. The elements of S^⊕ has the form n_1a_1 ⊕ n_2a_2 ⊕ ...n_ma_m, where a_i ∈ S, n_i ∈ℕ, i ∈ 1..m, and m is the number of elements in S. The source and target functions go from T to S^⊕ (∂_0, ∂_1: T → S^⊕). And a Petri net morphism <f, g> is similar to a graph morphism, except that g is now a monoid homomorphism, which respects the monoid structure of S^⊕.

This definition allows a different representation of the same standard Petri net. For example, if we have a Petri net <S, T, F> as shown in Figure <ref> where S = { g_1, g_2, g_3 }, T = { t }, F(g_1,t)=1, F(g_2,t) = 1, F(t, g_1)=1, F(t, g_3)=1, then we can represent it as S^⊕ = { g_1, g_2, g_3 } ^⊕, T = { t } and  ∂_0(t) = g_1+g_2, ∂_1(t) = g_1+g_3.



Under such a representation, sequential and parallel compositions of Petri nets based on transitions could be obtained in a straightforward way. For example, a sequential composition of two Petri nets is illustrated in Figure <ref>, where the Petri net in Figure <ref>c is a composition of the Petri net in Figure <ref>b after that in Figure <ref>a.



On the other hand, a parallel composition of two Petri nets is shown in Figure <ref>, in which we calculate the products of places and transitions from Figure <ref>a and Figure <ref>b, and got the result Petri net in Figure <ref>c.



With these two compositions at hands, we will be able to combine small Petri nets into large ones for the modelling of large GRNs.

Alternatively, we could construct the "open" Petri net following Baez and Master's recent work (<cit.>).

The basic idea underlies an Open Petri net is that certain places in the Petri net are designated as inputs or outputs via a cospan of sets, which allows tokens to flow in or out of the Petri net and therefore make it open. From the categorical theory point of view, the input and output sets are objects and the open Petri net is the morphism between them, together they form a symmetric monoidal category (<cit.>). Further, in order to better describe vertical composition between sets and horizontal composition between open Petri nets, a symmetric monoidal double category 𝕆pen(Petri) was introduced. 𝕆pen(Petri) has the following components:

(1) objects: sets X, Y, Z, ... 

(2) vertical 1-morphisms: functions from set X to Y (f:X → Y) 

(3) horizontal 1-cells: open Petri nets (P:X ↛ Y), which are cospans in Petri of the form: 



    [commutative diagrams/every diagram]
     (P0) at (90:2.3cm) P;
     (P1) at (90+72:2cm) LX ;
     (P4) at (90+4*72:2cm) LY;
    [commutative diagrams/.cd, every arrow, every label]
    (P1) edge node i (P0)
    (P4) edge node[swap] o (P0);

here L is a functor from Set to Petri.

(4) 2-morphisms: morphisms between open Petri nets. A 2-morphism in 𝕆pen(Petri) has the following form:
 

    LX_1 ri_1[swap]dLf   P_1 [swap]dα   LY_1 [swap]lo_1dLg
    
    LX_2 ri_2    P_2    LY_2 [swap]lo_2


We can compose 2-morphisms vertically by usual composition of functions as well as horizontally via the pushout of cospans. In addition, we can also obtain the tensor products of two 2-morphisms <cit.>. For example, if we have two 2-morphisms as follows:


    LX_1 ri_1[swap]dLf   P_1 [swap]dα   LY_1 [swap]lo_1dLg
    
    LX_2 ri_2    P_2    LY_2 [swap]lo_2







    LX_2 ri_2[swap]dLf'   P_1 [swap]dβ   LY_2 [swap]lo_2dLg'
    
    LX_3 ri_3    P_3    LY_3 [swap]lo_3


we can compose them vertically to get the 2-morphism:

    LX_1 ri_1[swap]dL(f' ∘ f)   P_1 [swap]dβ∘α   LY_1 [swap]lo_1dL(g' ∘ g)
    
    LX_3 ri_3    P_3    LY_3 [swap]lo_3


And, for the following two 2-morphisms:




LX_1 ri_1 [swap]dLf    P_1 [swap]dα     LY_1 [swap]lo_1 dLg     LY_1 ri_1' [swap]dLg    P_1' [swap]dα'     LZ_1 [swap]lo_1' dLh 

LX_2 ri_2    P_2    LY_2 [swap]lo_2    LY_2 ri_2'    P_2'    LZ_2 [swap]lo_2'



we can compose them horizontally to get the following 2-morphism:

    LX_1 ri_1' ∘ i_1[swap]dLf   P_1+_LY_1P_1'[swap]dα +_Lgα'   LZ_1 [swap]lo_1' ∘ o_1dLh
    
    LX_2 ri_2' ∘ i_2   P_2+_LY_2P_2'   LZ_2 [swap]lo_2' ∘ o_2


Moreover, for the two 2-morphism like these:





	LX_1 ri_1 [swap]dLf    P_1 [swap]dα     LY_1 [swap]lo_1 dLg     LX_1' ri_1' [swap]dLf'    P_1' [swap]dα'     LY_1' [swap]lo_1' dLg' 

	LX_2 ri_2    P_2    LY_2 [swap]lo_2    LY_2' ri_2'    P_2'    LY_2' [swap]lo_2'



we can calculate their tensor product to get the following 2-morphism:

    L(X_1+X_1') ri_1+i_1'[swap]dL(f+f')   P_1 +P_1'[swap]dα + α'   L(Y_1+Y_1') [swap]lo_1+o_1'dL(g+g')
    
    L(X_2+X_2') ri_2+i_2'   P_2+P_2'   L(Y_2+Y_2') [swap]lo_2+o_2'




§ OPEN PETRI NETS FOR GENE REGULATORY NETWORKS
 
Finally, we will illustrate with an example on how to compose two GRNs (in the form of open Petri nets). The example presented here is based on that created in <cit.>. Suppose we have the following two GRNs:



To compose them horizontal via pushout, we could first stick them side by side through the set Y and get the following intermediate network: 



Then, we identify those places that are images of the same point in Y, group them together, and randomly choose one place to represent the group, removing set Y meanwhile <cit.>. For example, point 2 in Y has images g3 and g6, so g3 and g6 are grouped together. Similarly, g4 and g6 are grouped together, and therefore we have g3, g4 and g6 all in the same group. Now we could merge those 3 places together, and we use g6 to represent this group. Also we merge g5 and g7 using g7 as representative place for them. We no longer need set Y and will obtain the composed open Petri net:






§ CONCLUSION AND FUTURE WORK

In this preliminary work we attempt to model the gene regulatory networks (GRNs) with open Petri nets (OPNs) <cit.>. OPN incorporates the power of both category theory and Petri nets, therefore it holds the great potential to become an ideal framework for systematic representation of GRNs. At this stage we only provide an example of how to compose two hypothetical GRNs written in the forms of OPNs. In the future we need to formalize on how to convert real GRNs into composable OPNs and further demonstrate that these OPN models facilitate the construction of large GRNs from smaller parts.

apalike



