Modèles pour l'inférence de paramètres temporels des réseaux de régulation biologiques - cours de mars 2012

Modeles pour l’inference de parametres temporels desreseaux de regulation biologiques

Morgan [email protected]

Travail conjoint avec :G. Bernot, JP. Comet, A. Richard, O. Roux (demarche et application a

la biologie)D. Lime, P. Molinaro et O.H. Roux (theorie sur les reseaux de Petri)

Ecole Centrale de NantesIRCCyN - Equipe � MeForBio �

Ecole Jeunes Chercheurs en Informatique Mathematique - 20/03/12

M. Magnin (IRCCyN) Expose EJCIM 2012 20/03/2012 1 / 66

Introduction

Contexte (1/2)

Pourquoi modeliser informatiquement des systemes biologiques ?

Comprendre finement le systeme... // Structure

et ses comportements // Dynamique

Analyser les proprietes // Prediction de comportements

Aider a la conception de nouvelles experiences // Inference deparametres

Differents niveaux d’abstraction dependant :

Des questions biologiques

De la nature et de la qualite des donnees disponibles


Introduction

Contexte (2/2)

Differents niveaux de modelisation

Au niveau moleculaire : reseau biochimique, transduction du signal

Au niveau de la regulation entre genes : reseau genetique

Au niveau inter-cellulaire : differenciation cellulaire, tissus, schemas

Au niveau macroscopique : organes, physiologie

Etat de l’art

Graphes de regulation

Modelisation qualitative : modeles booleens/logiques, reseaux de Petri

Modelisation quantitative : equations aux derivees partielles,equations stochastiques, etc.


Introduction

Objectifs

Comprendre l’enrichissement progressif d’un modele... et sesinconvenients

Saisir l’introduction de la dimension temporelle

Discuter la semantique de temps la plus appropriee au cas etudie


Introduction

Pourquoi des reseaux de Petri ?

Formalisme mathematique et graphique

Representation aisee de la concurrence/du parallelisme

Des proprietes structurelles (P-invariants, T-invariants, ...)

Des proprietes dynamiques (vivacite, bornitude, accessibilite, ...)

Des outils matures : Snoopy, ginSIM, Romeo, etc.


Modelisation a l’aide de RdP

Sommaire

1 Introduction a la modelisation a base de reseaux de Petri

2 Modelisation des reactions biochimiques

3 Modelisation des reseaux de regulation biologiques

4 Modelisation des delaisEnrichissement des modeles formelsExploration de l’espace d’etatsIntegration des delais biologiques dans la modelisation



Reseaux de Petri : une large famille de modeles

Discrets [SBSW07]

Continus [KH08]

Hybrides [MDNM00]

Stochastiques [GP98] : le tir d’une transition se fait au travers d’unefonction de probabilite, ce qui correspond ainsi aux sensibilisationschimiques suivant la concentration

Colores [GKP10] : les jetons sont differenties

Temporels et chronometriques : travaux en cours IRCCyNMeForBio/I3S BioInfo



Reseaux de Petri - Presentation

P1

t1

P2

t2

P4

t4

P3

t3

Figure: Un RdP

{P1,P2,P4}




P1

t1

P2

t2

P4

t4

P3

t3

Figure: Un RdP

{P1,P2,P4} t2→ {P1,P3,P4} t1→ . . .




P1

t1

P2

t2

P4

t4

P3

t3

Figure: Un autre RdP

{P1,P2,P4}




P1

t1

P2

t2

P4

t4

P3

t3

Figure: Un autre RdP

{P1,P2,P4} t2→ {P3,P4} . . .



Reseaux de Petri avec arcs de reset - Presentation

P1

t1

P2

t2

P4

t4

P3

t3

Figure: Un RdP avec arcs de reset

{P1,P2, 5× P4} t2→ . . .



Reseaux de Petri avec arcs de reset - Presentation

P1

t1

P2

t2

P4

t4

P3

t3

Figure: Un RdP avec arcs de reset

{P1,P2, 5× P4} t2→ {P1,P3} t1→ . . .




Definition

Un ensemble de places

Un ensemble de transitions

Une fonction d’incidence amont

Une fonction d’incidence aval

Un etat initial




Quelques proprietes structurelles

T-invariant : sequence de transitions qui fait revenir dans le memeetat/marquage.

P-invariant : invariant de marquage (par exempleqi M(pi ) + qj M(pj ) + qk M(pk ) = c pour tout etat du reseau).




Quelques proprietes dynamiques

Vivacite

Marquage mort

Accessibilite d’un marquage (etant donne un etat initial)



Reseaux de Petri - Applications

Systemes de production (usine)

Systemes de deploiement logistique

Systemes embarques

Jeu video (modelisation d’une I.A.)

Et bien sur la biologie !



Petite reflexion sur le sens des elements d’un RdP

Marquage d’une place : presence/absence ou quantite d’uncomposant

Arc : precedence ou succession

Transition : evenement et/ou transformation

Poids : quantite necessaire, consommee et/ou produite


Modelisation des reactions biochimiques

Sommaire







Reseaux de Petri pour la modelisation de reseauxbiochimiques

Principe de la modelisation qualitative

Places : reactants, produits, enzymes

Transitions : reactions, catalyse

Poids sur les arcs : stochiometrie



Application a la modelisation des reactions biochimiques

2NAD+ + 2H2O → 2NADH + 2H+ + O2

NAD+

H2O

r

H+

NADH

O2

2

2

2

2

Figure: Un exemple de traduction



Proprietes des RdP pour la modelisation de reseauxbiochimiques

Proprietes structurelles

Matrice d’incidence : matrice de stochiometrie

P-invariants : relations de conservations

T-invariants : modes de flux elementaires

Proprietes dynamiques

Vivacite : les composants sont suffisants pour declencher les reactions

Marquage mort : etat stable


Modelisation des reseaux de regulation biologiques

Sommaire







Bref rappel sur les Reseaux de Regulation Biologiques

Activations et inhibitions entre les genes

Les genes ont un ensemble de niveaux logiques d’expression

Regulation effective au-dela d’un certain seuil ; effet inverse en deca[R. Thomas].

f

c a

(Rmq. reseau booleen)



Des reseaux de regulation aux reseaux de Petri

Principe

Une place par gene

Le marquage : niveau discret de concentration

c aka,{} ka,{c}

sc→a,+

Figure: Un reseau de regulation simple

Points critiques

Comment tester le niveau de concentration sans le decrementer ?

Comment modeliser une action qui n’a lieu qu’en dessous d’unecertaine concentration ?

→ Introduction de nouveaux arcs



Reseaux de Petri avec arcs de lecture

P1

t1

P2

t2

P4

t4

P3

t3

Figure: Un RdP avec arc de lecture

{P1,P2,P4}



Reseaux de Petri avec arcs de lecture

P1

t1

P2

t2

P4

t4

P3

t3

Figure: Un RdP avec arc de lecture

{P1,P2,P4} t2→ {P1,P3,P4} . . .



Reseaux de Petri a hyperarcs inhibiteurs (logiques)

P1

t1

P2

t2

P4

t4

P3

t3

Figure: RdP a hyperarcs inhibiteurs

{P1,P2,P4}




P1

t1

P2

t2

P4

t4

P3

t3

Figure: RdP a hyperarcs inhibiteurs : t1 inhibee lorsque (M(P3) ≥ 1 etM(P4) ≥ 1)

{P1,P2,P4} t2→ {P1,P3,P4}




P1

t1

P2

t2

P4

t4

P3

t3


{P1,P2,P4} t2→ {P1,P3,P4} t3→ {P1,P4} t1→ . . .




cNaN

t+a,{}

t−a,{}

sc−>a

sc−>a

ka,{} + 1

ka,{} + 1

sc−>a

sc−>a

ka,{c} + 1

ka,{c} + 1

t+a,{c}

t−a,{c}

c aka,{} ka,{c}

sc→a,+

Figure: Traduction vers les reseaux de Petri




Analyse

Traduction automatisee

Reseau borne → moindre cout des arcs de lecture et hyperarcsinhibiteurs logiques


Modelisation des delais

Sommaire







Limites des modelisations discretes

ca−

f

a

c

f

a

c

δfa+ δ

δfc+

1

2

0

1

0

2

1

0



Enjeux de la synthese de parametres temporels

Problemes

Inferer les delais de production et degradation

Prendre en compte les mecanismes d’accumulation(ordre/contre-ordre)



Contexte et objectifs (2/2)

Bibliographie : (non exhaustive) :

Extensions temporelles et stochastiques des reseaux de Petri [C.Chaouiya & E. Remy & D. Thieffry] [CRT08],

Contraintes (Biocham) [F. Fages] [RBFS08],

Algebre de processus stochastique (BioSpi et Spim) [C. Priami et A.Regev] [PRSS01]

Model Checking probabiliste (Prism) [M. Kwiatkowska & D. Parker][HKN+08],

Automates temporises [H. Siebert & A. Bockmayr] [SB08] etautomates lineaires hybrides [J. Ahmad & O. Roux] [ABC+07],


Modelisation des delais Enrichissement des modeles formels

Enrichissement des modeles

Adapter le modele aux enjeux biologiques

Introduction de delais ⇒ systemes de transitions temporisees

Necessite de modeliser des taches avec suspension/reprise ⇒ integrerla notion de chronometres

Compromis expressivite/decidabilite



Problematique (2/2)

Choix d’un modele de temps approprie pour S

Temps dense ?

Temps discret ?

Inference et verification de proprietes temporelles quantitatives

⇒ Methodes efficaces d’exploration de l’espace d’etats⇒ Structures de donnees compactes pour la representation et le calculde l’espace d’etats



Problematique (2/2)

Choix d’un modele de temps approprie pour S

Temps dense ?

Temps discret ?

Inference et verification de proprietes temporelles quantitatives

⇒ Methodes efficaces d’exploration de l’espace d’etats⇒ Structures de donnees compactes pour la representation et le calculde l’espace d’etats



Reseaux de Petri temporels - Presentation

P1

t1 [5,6]

P2

t2 [0,1]

P4

t4 [2,4]

P3

t3 [1,2]

Figure: Un RdPT en temps dense

{P1,P2,P4}θ(t1) = 0θ(t2) = 0θ(t4) = 0

0.2→{P1,P2,P4}θ(t1) = 0.2θ(t2) = 0.2θ(t4) = 0.2




P1

t1 [5,6]

P2

t2 [0,1]

P4

t4 [2,4]

P3

t3 [1,2]

Figure: Un RdPT en temps dense

{P1,P2,P4}θ(t1) = 0θ(t2) = 0θ(t4) = 0

0.2→{P1,P2,P4}θ(t1) = 0.2θ(t2) = 0.2θ(t4) = 0.2

t2→{P1,P3,P4}θ(t1) = 0.2θ(t3) = 0θ(t4) = 0.2

0.9→ . . .




P1

t1 [5,6]

P2

t2 [0,1]

P4

t4 [2,4]

P3

t3 [1,2]

Figure: Un RdPT en temps discret

{P1,P2,P4}θ(t1) = 0θ(t2) = 0θ(t4) = 0

1→{P1,P2,P4}θ(t1) = 1θ(t2) = 1θ(t4) = 1

t2→{P1,P3,P4}θ(t1) = 1θ(t3) = 0θ(t4) = 1

1→{P1,P3,P4}θ(t1) = 2θ(t3) = 1θ(t4) = 2

1→ . . .



Reseaux de Petri temporels - A propos des arcs de lecture

P1

t1 [5,6]

P2

t2 [0,1]

P4

t4 [2,4]

P3

t3 [1,2]

Figure: Un autre RdPT (en temps dense)

{P1,P2,P4}θ(t1) = 0θ(t2) = 0θ(t4) = 0

0.2→{P1,P2,P4}θ(t1) = 0.2θ(t2) = 0.2θ(t4) = 0.2




P1

t1 [5,6]

P2

t2 [0,1]

P4

t4 [2,4]

P3

t3 [1,2]

Figure: Un autre RdPT (en temps dense)

{P1,P2,P4}θ(t1) = 0θ(t2) = 0θ(t4) = 0

0.2→{P1,P2,P4}θ(t1) = 0.2θ(t2) = 0.2θ(t4) = 0.2

t2→{P1,P3,P4}θ(t1) = 0θ(t3) = 0θ(t4) = 0.2

0.9→ . . .




P1

t1 [5,6]

P2

t2 [0,1]

P4

t4 [2,4]

P3

t3 [1,2]

Figure: Un RdPT avec arcs de lecture

{P1,P2,P4}θ(t1) = 0θ(t2) = 0θ(t4) = 0

0.2→{P1,P2,P4}θ(t1) = 0.2θ(t2) = 0.2θ(t4) = 0.2




P1

t1 [5,6]

P2

t2 [0,1]

P4

t4 [2,4]

P3

t3 [1,2]


{P1,P2,P4}θ(t1) = 0θ(t2) = 0θ(t4) = 0

0.2→{P1,P2,P4}θ(t1) = 0.2θ(t2) = 0.2θ(t4) = 0.2

t2→{P1,P3,P4}θ(t1) = 0.2θ(t3) = 0θ(t4) = 0.2

0.9→ . . .




P1

t1 [5,6]

P2

t2 [0,1]

P4

t4 [2,4]

P3

t3 [1,2]


Theoreme

Les RdPT avec arcs de lecture sont plus expressifs que les RdPT.



Reseaux de Petri a chronometres - SwPN

Objectif

Pouvoir memoriser l’etat d’une action qui est suspendue

Solution

Etendre les RdPT avec la notion de chronometre

Ressources et priorites sur les places [RD01] ou les transitions[BFSV04]

Arcs activateurs [BLRV07]

Hyperarcs inhibiteurs [RL04] :

Si t est sensibilisee par le marquage M :

t est inhibee par M ⇒ θ(t) = 0t n’est pas inhibee par M ⇒ θ(t) = 1



Reseaux de Petri a chronometres - SwPN

Objectif

Pouvoir memoriser l’etat d’une action qui est suspendue

Solution

Etendre les RdPT avec la notion de chronometre

Ressources et priorites sur les places [RD01] ou les transitions[BFSV04]

Arcs activateurs [BLRV07]

Hyperarcs inhibiteurs [RL04] :

Si t est sensibilisee par le marquage M :

t est inhibee par M ⇒ θ(t) = 0t n’est pas inhibee par M ⇒ θ(t) = 1



Reseaux de Petri temporels a hyperarcs inhibiteurs

P1

t1 [5,6]

P2

t2 [0,1]

P4

t4 [2,4]

P3

t3 [1,2]

Figure: Les SwPN : modele de RdP a chronometres

{P1,P2,P4}θ(t1) = 0θ(t2) = 0θ(t4) = 0

0.2→{P1,P2,P4}θ(t1) = 0.2θ(t2) = 0.2θ(t4) = 0.2




P1

t1 [5,6]

P2

t2 [0,1]

P4

t4 [2,4]

P3

t3 [1,2]

Figure: Un SwPN : t1 inhibee lorsque (M(P3) ≥ 1 et M(P4) ≥ 1)

{P1,P2,P4}θ(t1) = 0θ(t2) = 0θ(t4) = 0

0.2→{P1,P2,P4}θ(t1) = 0.2θ(t2) = 0.2θ(t4) = 0.2

t2→{P1,P3,P4}θ(t1) = 0.2θ(t3) = 0θ(t4) = 0.2

1→{P1,P3,P4}θ(t1) = 0.2θ(t3) = 1θ(t4) = 1.2




P1

t1 [5,6]

P2

t2 [0,1]

P4

t4 [2,4]

P3

t3 [1,2]

Figure: Un SwPN : apres que t1 a ete � reactivee �

{P1,P2,P4}θ(t1) = 0θ(t2) = 0θ(t4) = 0

0.2→{P1,P2,P4}θ(t1) = 0.2θ(t2) = 0.2θ(t4) = 0.2

t2→{P1,P3,P4}θ(t1) = 0.2θ(t3) = 0θ(t4) = 0.2

1→{P1,P3,P4}θ(t1) = 0.2θ(t3) = 1θ(t4) = 1.2

t3→{P1,P4}θ(t1) = 0.2θ(t4) = 1.2




P1

t1 [5,6]

P2

t2 [0,1]

P4

t4 [2,4]

P3

t3 [1,2]

Figure: Un SwPN en temps discret

{P1,P2,P4}θ(t1) = 0θ(t2) = 0θ(t4) = 0

1→{P1,P2,P4}θ(t1) = 1θ(t2) = 1θ(t4) = 1

t2→{P1,P3,P4}θ(t1) = 1θ(t3) = 0θ(t4) = 1

1→{P1,P3,P4}θ(t1) = 1θ(t3) = 1θ(t4) = 2

t3→{P1,P4}θ(t1) = 1θ(t4) = 2



Semantiques

Hypotheses fondamentales

Semantique mono-serveur

Semantique intermediaire

Semantique forte

Choix d’un modele de temps approprie

Semantique en temps dense : evolution continue du temps

Semantique en temps discret : le temps � saute � d’un entier al’autre lors d’un tic d’horloge



Semantiques




Semantique forte






Semantiques




Semantique forte






Semantiques




Semantique forte






Semantiques




Semantique forte






Synthese sur les arcs ”logiques”

Modeles discrets

Les arcs de lecture n’ajoutent pas d’expressivite aux RdP.

Les arcs de reset ajoutent de l’expressivite aux RdP.

Les arcs inhibiteurs logiques ajoutent de l’expressivite aux RdP.

Modeles temporels

Les arcs de lecture ajoutent de l’expressivite aux RdPT (mais pas auxSwPN).

Les arcs de reset ajoutent de l’expressivite aux RdPT (mais pas auxSwPN).

Les arcs inhibiteurs logiques ajoutent de l’expressivite aux RdPT(mais pas aux SwPN).



Synthese sur les arcs ”logiques”

Modeles discrets

Les arcs de lecture n’ajoutent pas d’expressivite aux RdP.

Les arcs de reset ajoutent de l’expressivite aux RdP.

Les arcs inhibiteurs logiques ajoutent de l’expressivite aux RdP.

Modeles temporels

Les arcs de lecture ajoutent de l’expressivite aux RdPT (mais pas auxSwPN).

Les arcs de reset ajoutent de l’expressivite aux RdPT (mais pas auxSwPN).

Les arcs inhibiteurs logiques ajoutent de l’expressivite aux RdPT(mais pas aux SwPN).




Probleme

En temps dense, l’accessibilite d’etat d’un SwPN, meme borne, estindecidable [BLRV07].

De la traduction des RdPT en temps discret en RdP non-temporise, nouspouvons deduire :

Theoreme

En temps discret, l’accessibilite d’etat d’un SwPN borne est decidable.




Probleme

En temps dense, l’accessibilite d’etat d’un SwPN, meme borne, estindecidable [BLRV07].

De la traduction des RdPT en temps discret en RdP non-temporise, nouspouvons deduire :

Theoreme

En temps discret, l’accessibilite d’etat d’un SwPN borne est decidable.



Resultats de decidabilite

RdPT SwPNTemps dense Temps discret Temps dense Temps discret

General Bornes General Bornes General Bornes General Bornes

Bornitude I D I (thm 6.5) D I I I (thm 6.7) D (thm 6.9)

k-bornitude I D D D I I D (thm 6.9) D (thm 6.9)

Vivacite I D I (thm 6.5) D I I I (thm 6.7) D (thm 6.9)

Access. marquage I D I (thm 6.5) D I I I (thm 6.7) D (thm 6.9)

Access. d’etat I D I (thm 6.5) D I I I (thm 6.7) D (thm 6.8)

Table: Decidabilite pour les RdPT et les SwPN


Modelisation des delais Exploration de l’espace d’etats

Probleme

L’espace d’etats d’un RdPT/SwPN est infini (en general)

Determination de l’espace d’etats des SwPN en temps dense

Techniques d’abstractions (semi-algorithmes) ⇒ Regrouper les etats enclasses d’equivalence

Determination de l’espace d’etats des SwPN en temps discret

Enumerer l’ensemble des etats

Adapter les methodes symboliques du temps dense au temps discret



Probleme









Probleme









Quel rapport entre temps discret et discretisation du tempsdense ?

Question

Peut-on envisager l’espace d’etats des reseaux en temps discret comme ladiscretisation de l’espace d’etats du modele associe en temps dense ?

Problemes

Identifier les cas ou la discretisation est correcte

Proposer un algorithme calculant symboliquement l’espace d’etats

Verifier les proprietes TCTL du SwPN a l’aide de cet algorithme



Quel rapport entre temps discret et discretisation du tempsdense ?

Question

Peut-on envisager l’espace d’etats des reseaux en temps discret comme ladiscretisation de l’espace d’etats du modele associe en temps dense ?

Problemes

Identifier les cas ou la discretisation est correcte

Proposer un algorithme calculant symboliquement l’espace d’etats

Verifier les proprietes TCTL du SwPN a l’aide de cet algorithme



Abstraction de l’espace d’etats des RdPT en temps dense

Probleme

Regrouper les etats en classes d’equivalence (abstraction)

⇒ Utilisation du graphe des classes [BM83]

RdPT et certaines classes d’etats des SwPN : encodage du domaine parune Difference Bound Matrix (DBM) [dij ]i ,j∈[0..n] :{−d0i ≤ θi − 0 ≤ di0,θi − θj ≤ dij



Abstraction de l’espace d’etats des SwPN en temps dense

SwPN : Polyedres generaux Aθ ≤ B



Graphe des classes d’etats

SwPN

P1

t1 [5,6]

P2

t2 [0,1]

P4

t4 [2,4]

P3

t3 [1,2]

Graphe des classes



Classes d’etats pour les SwPN en temps discret

Objectif

Etendre le principe des classes d’etats au temps discret



Classes d’etats pour les SwPN en temps discret

⇒ Definir des classes d’etats symboliques



Classes d’etats symbolique pour les SwPN en temps discret



Probleme pose par la discretisation des classes symboliques

Question

Le successeur en temps discret d’une classe symbolique (M,Poly)coıncide-t-il avec la discretisation du successeur en temps dense de cetteclasse ?




Question


Reponse

Oui dans le cas des RdPT [Pop91, PZ96].

Et pour les SwPN ?




Question


Reponse

Oui dans le cas des RdPT [Pop91, PZ96].

Et pour les SwPN ?




(a)

θ(t)

θ(c)(b)

θ(t)Poly

θ(u)

nextdense(Poly, c)

Question

Tous les points issus de la discretisation de nextdense(Poly , c) possedent-ilsun predecesseur aux coordonnees toutes entieres ?nextdiscret(Disc(Poly)) = Disc(nextdense(Poly)) ?




(a)

θ(t)

θ(c)(b)

θ(t)Poly

A

nextdiscret(A, c)

θ(u)

nextdense(Poly, c)

Question





(a)

θ(t)

θ(c)(b)

θ(t)Poly

A

B

nextdiscret(A, c)

nextdiscret(B, c)

θ(u)

nextdense(Poly, c)

Question





(a)

θ(t)

θ(c)(b)

θ(t)Poly

A

B

nextdiscret(A, c)

nextdiscret(B, c)

θ(u)

nextdense(Poly, c)

Question





Question


Notre reponse

Oui dans le cas de DBM

Identification de la forme des premiers polyedres non-DBMapparaissant au cours du calcul : x + y (−z) ∼ c

Non des l’apparition d’un tel polyedre non-DBM !




Question


Notre reponse







Question


Notre reponse






Theoreme

L’espace d’etats d’un RdPT dote d’une semantique de temps discret et ladiscretisation de l’espace d’etats du reseau associe en temps densecoıncident.

⇒ Et pour les reseaux a chronometres ?

Theoreme

L’espace d’etats d’un SwPN dote d’une semantique de temps discret n’estpas la discretisation de l’espace d’etats du reseau associe en temps dense.



Theoreme

L’espace d’etats d’un RdPT dote d’une semantique de temps discret et ladiscretisation de l’espace d’etats du reseau associe en temps densecoıncident.

⇒ Et pour les reseaux a chronometres ?

Theoreme

L’espace d’etats d’un SwPN dote d’une semantique de temps discret n’estpas la discretisation de l’espace d’etats du reseau associe en temps dense.



Probleme

Calculer symboliquement l’espace d’etats des RdP a chronometres ?

Theoreme

Aussi longtemps que le graphe des classes d’un RdP a chronometres nefait pas intervenir de polyedre non-DBM :

La discretisation de l’espace d’etats du reseau en temps dense conduita des etats appartenant tous a l’espace d’etats en temps discret ;

Ensemble des traces non-temporisees du reseau en temps dense ⊆Ensemble des traces non temporisees en temps discret.



Probleme

Calculer symboliquement l’espace d’etats des RdP a chronometres ?

Theoreme

Aussi longtemps que le graphe des classes d’un RdP a chronometres nefait pas intervenir de polyedre non-DBM :

La discretisation de l’espace d’etats du reseau en temps dense conduita des etats appartenant tous a l’espace d’etats en temps discret ;

Ensemble des traces non-temporisees du reseau en temps dense ⊆Ensemble des traces non temporisees en temps discret.



Calcul symbolique de l’espace d’etats en temps discret

Principes

Calculer l’espace d’etats du reseau associe en temps dense tantqu’un polyedre non-DBM n’apparaıt pas ;

Tout polyedre non-DBM Poly est decompose en union de DBM,DBM split(Poly), telle que Disc(Poly) = Disc(DBM split(Poly))




Principes






Principes






Principes





Theoreme

L’algorithme de calcul symbolique de l’espace d’etats des reseaux en tempsdiscret est correct en termes d’accessibilite et de langage.

Theoreme

La terminaison de l’algorithme est assuree pour les SwPN bornes en tempsdiscret.


Modelisation des delais Integration des delais biologiques dans la modelisation

Des reseaux de regulation vers les extensions temporellesdes reseaux de Petri

Principe

Discretiser finement les niveaux de concentration (donc les seuils) dechaque gene

Associer les delais de production et de degradation aux transitionsapparues sur la traduction discrete




cNaN

t+a,{}

t−a,{}

nc.sc−>a

nc.sc−>a

na.ka,{} + 1

na.ka,{} + 1

nc.sc−>a

nc.sc−>a

t+a,{c}

t−a,{c}

c a

ka,{} ka,{c}

sc→a,+

Paramètres logiques

Délais

δ+a,{}

δ−a,{}

δ+a,{c}

δ−a,{c}

[δ−a,{c}, δ−a,{c}]

[δ+a,{c}, δ

+a,{c}]

[δ+a,{}, δ

+a,{}]

[δ−a,{}, δ−a,{}]

nc.ka,{c} + 1

nc.ka,{c} + 1

Figure: Traduction vers les reseaux de Petri temporelsM. Magnin (IRCCyN) Expose EJCIM 2012 20/03/2012 53 / 66



Analyse

Ouverture au model-checking de formules TCTL

Possibilite d’inferer les parametres temporels associes a une transition

Automatisation de la traduction et export vers le logiciel Romeo



Validation d’un modele

Objectif : verification formelle de proprietes sur des modeles

Modeliser le systeme S :→ reseaux de Petri, reseaux de Petri temporels, reseaux de Petri achronometres, . . .

Formaliser la specification ϕ :→ observateurs, logique temporelle (LTL, CTL, TCTL),. . .

Est-ce que S |= ϕ ?

Algorithmes implementes dans Romeo en temps dense et en temps discret



Validation d’un modele

Objectif : verification formelle de proprietes sur des modeles

Modeliser le systeme S :→ reseaux de Petri, reseaux de Petri temporels, reseaux de Petri achronometres, . . .

Formaliser la specification ϕ :→ observateurs, logique temporelle (LTL, CTL, TCTL),. . .

Est-ce que S |= ϕ ?

Algorithmes implementes dans Romeo en temps dense et en temps discret



Application : reseau p53-MdM2

P D

2, -

NC1, -

1, -

1, -

2, +

1, +

Figure: Reseau tire de [WAjK09]



Application : reseau p53-MdM2

Figure: Traduction en reseau de Petri temporel



Analyse biologique

Validation du modele

Verification de proprietes (oscillations entretenues, amorties, etc.)

Model-checking de formules TCTL

Inference des delais

Model-checking de formules TCTL parametriques



Analyse biologique

Limites

Indecidabilite du model-checking de formules TCTL, meme pour desRdPT parametriques bornes [TLR09]

Explosion combinatoire des etats

Limitation en taille des reseaux et en nombre de parametres

Methodologie

Identification de sous-problemes interessants

Inference progressive de certains delais


Conclusion intermediaire

Apports des reseaux de Petri

Bilan

Modele intuitif, qui s’adapte facilement aux systemes biologiques

Introduction progressive des delais, jusqu’a leur inferenceparametrique

Mais explosion combinatoire de l’espace d’etats

Perspectives

Analyse de reseaux multi-echelles

Application a l’horloge circadienne (projet CirClock)

Tirer profit des possibilites offertes au niveau chronometrique

Developper de nouvelles approches pour l’etude de grands reseaux



Jamil Ahmad, Gilles Bernot, Jean-Paul Comet, Didier Lime, andOlivier Roux.Hybrid modelling and dynamical analysis of gene regulatory networkswith delays.ComPlexUs, 3(4) :231–251, October 2007.

Beatrice Berard, Franck Cassez, Serge Haddad, Didier Lime, andOlivier (H.) Roux.Comparison of the expressiveness of timed automata and time Petrinets.In 3rd International Conference on Formal Modelling and Analysis ofTimed Systems (FORMATS 05), volume 3829 of Lecture Notes inComputer Science, Uppsala, Sweden, September 2005. Springer.

B. Berthomieu and M. Diaz.Modeling and verification of time dependent systems using time Petrinets.IEEE transactions on software engineering, 17(3) :259–273, 1991.



G. Bucci, A. Fedeli, L. Sassoli, and E. Vicario.Time state space analysis of real-time preemptive systems.IEEE transactions on software engineering, 30(2) :97–111, February2004.

Bernard Berthomieu, Didier Lime, Olivier (H.) Roux, and FrancoisVernadat.Reachability problems and abstract state spaces for time Petri netswith stopwatches.Journal of Discrete Event Dynamic Systems (DEDS), 17(2), 2007.To appear.

B. Berthomieu and M. Menasche.An enumerative approach for analyzing time Petri nets.IFIP Congress Series, 9 :41–46, 1983.

B. Berthomieu and F. Vernadat.State class constructions for branching analysis of time Petri nets.In TACAS’03, pages 442–457. Springer–Verlag, Apr 2003.



Claudine Chaouiya, Elisabeth Remy, and Denis Thieffry.Petri net modelling of biological regulatory networks.J. of Discrete Algorithms, 6(2) :165–177, 2008.

Jean-Louis Giavitto, Hanna Klaudel, and Franck Pommereau.Qualitative modelling and analysis of regulations in multi-cellularsystems using petri nets and topological collections.In 4th Workshop on Membrane Computing and Biologically InspiredProcess Calculi (MeCBIC’10), number 40 in EPTCS, pages 1–16,2010.

P. J. Goss and J. Peccoud.Quantitative modeling of stochastic systems in molecular biology byusing stochastic Petri nets.Proceedings of the National Academy of Sciences of the United Statesof America, 95(12) :6750–6755, June 1998.

John Heath, Marta Kwiatkowska, Gethin Norman, David Parker, andOksana Tymchyshyn.Probabilistic model checking of complex biological pathways.



Theoretical Computer Science, 391(3) :239–257, 2008.

I Koch and M Heiner.Petri Nets, chapter 7, pages 139–179.Wiley Book Series on Bioinformatik. John Wiley & Sons, 2008.Series Eds. Yi Pan, Albert Y. Zomaya.

H Matsuno, A Doi, M Nagasaki, and S Miyano.Hybrid petri net representation of gene regulatory network.Pacific Symposium On Biocomputing, 349(338-349) :341–352, 2000.

Louchka Popova.On time petri nets.Journal Inform. Process. Cybern., EIK (formerly : Elektron. Inform.verarb. Kybern.), 27(4) :227–244, 1991.

Corrado Priami, Aviv Regev, Ehud Shapiro, and William Silverman.Application of a stochastic name-passing calculus to representationand simulation of molecular processes.Inf. Process. Lett., 80(1) :25–31, 2001.



L. Popova-Zeugmann.Essential states in time petri nets, 1996.

Aurelien Rizk, Gregory Batt, Francois Fages, and Sylvain Soliman.On a continuous degree of satisfaction of temporal logic formulae withapplications to systems biology.In Monika Heiner and Adeline Uhrmacher, editors, CMSB’08 :Proceedings of the fourth international conference on ComputationalMethods in Systems Biology, volume 5307 of Lecture Notes inComputer Science, pages 251–268. Springer-Verlag, October 2008.

Olivier H. Roux and Anne-Marie Deplanche.Extension des reseaux de Petri t-temporels pour la modelisation del’ordonnancement de taches temps-reel.In 3e congres Modelisation des Systemes Reactifs (MSR’2001), pages327–342, Toulouse, France, 2001. Hermes Science.

Olivier (H.) Roux and Didier Lime.Time Petri nets with inhibitor hyperarcs. Formal semantics and statespace computation.



In The 25th International Conference on Application and Theory ofPetri Nets, (ICATPN’04), volume 3099 of Lecture Notes in ComputerScience, pages 371–390, Bologna, Italy, June 2004. Springer.

Heike Siebert and Alexander Bockmayr.Temporal constraints in the logical analysis of regulatory networks.Theoretical Computer Science, 391(3) :258–275, 2008.

L. Jason Steggles, Richard Banks, Oliver Shaw, and Anil Wipat.Qualitatively modelling and analysing genetic regulatory networks : apetri net approach.Bioinformatics, 23 :2006, 2007.

Louis-Marie Traonouez, Didier Lime, and Olivier (H.) Roux.Parametric model-checking of stopwatch petri nets.Journal of Universal Computer Science, 15(17) :3273–3304, December2009.

D. A. Ouattara W. Abou-jaoude and M. Kaufman.From structure to dynamics : Frequency tuning in the p53-mdm2network. i. logical approach.


Annexes

Journal of Theoretical Biology, 258 :561–577, 2009.


Annexes

Inhibitions en OU : arcs inhibiteurs

P1

t1

P3

t3

P2

t2

P4

{P1,P2, P3}

{P1, P3}

{P3}

{}

t2

t1

t3

Figure: RdP a arcs inhibiteurs

Inhibition

t3 inhibee si ((M(P1) ≥ 1) OU (M(P2) ≥ 1))


Annexes

Inhibitions en ET : hyperarcs inhibiteurs

P1

t1

P3

t3

P2

t2

P4

{P1,P2, P3}

{P1, P3}

{P3}

{}

t2

t1

t3

t3

t1


Inhibition

t3 inhibee si ((M(P1) ≥ 1) ET (M(P2) ≥ 1))


Annexes

Abstractions en temps dense

Differents types de proprietes

Proprietes temporelles non quantitatives :

Propriete sur des traces (LTL) : graphe des classes [BD91]

Propriete arborescentes (CTL) : graphe des classes atomiques [BV03]

Proprietes temporelles quantitatives

Observateurs puis calcul d’accessibilite

Traduction en automate temporise puis utilisation des outils demodel-checking sur les AT

Verification a la volee de proprietes TCTL


Annexes

Abstractions en temps dense

Differents types de proprietes

Proprietes temporelles non quantitatives :

Propriete sur des traces (LTL) : graphe des classes [BD91]

Propriete arborescentes (CTL) : graphe des classes atomiques [BV03]

Proprietes temporelles quantitatives

Observateurs puis calcul d’accessibilite

Traduction en automate temporise puis utilisation des outils demodel-checking sur les AT

Verification a la volee de proprietes TCTL


Annexes

Apparition de polyedres non-DBM (1/2)

SwPN

P1

t1 [5,6]

P2

t2 [0,1]

P4

t4 [2,4]

P3

t3 [1,2]

Graphe des classes


Annexes

Apparition de polyedres non-DBM (2/2)

SwPN

P1

t1 [5,6]

P2

t2 [0,1]

P4

t4 [3,4]

P3

t3 [1,2]

Graphe des classes


Annexes

Traduction des bornes vers les saufs (1/2)

Theoreme

[BCH+05] ont prouve que les RdPT bornes et les RdPT 1-saufs � a laMerlin � sont d’expressivite equivalente en termes de bisimulationtemporelle.


Annexes

Traduction des bornes vers les saufs (1/2)

Theoreme

[BCH+05] ont prouve que les RdPT bornes et les RdPT 1-saufs � a laMerlin � sont d’expressivite equivalente en termes de bisimulationtemporelle.

Notre contribution

Generalisation aux intervalles ouverts

Extension aux SwPN


Documents

Modèles pour l'inférence de paramètres temporels des réseaux de régulation biologiques - cours de mars 2012