Formalizzazione e confronto di algoritmi di simulazione stocastici con ritardo

Università Di Pisa

Facoltà di Scienze Matematiche Fisiche e Naturali

Corso di Laurea Specialistica in Informatica

Formalizzazione e confronto di algoritmi

di simulazione stocastica con ritardo

RELATORE

Prof. Andrea Maggiolo Schettini

CORRELATORI

TESI DI LAUREA DI

Dott. Paolo Milazzo

Giovanni Cambria

Dott. Giulio Caravagna

Matr. N. 228179

Indice

1 Introduzione 5

1.1 Struttura della tesi . . . 8

2 Modelli deterministici di sistemi biologici 11 2.1 Equazioni dierenziali ordinarie . . . 11

2.2 Equazioni dierenziali con ritardi . . . 13

2.2.1 Equazioni dierenziali con ritardo costante . . . 14

2.2.2 Equazioni dierenziali con ritardo variabile . . . 15

3 Modelli stocastici di sistemi biologici 17 3.1 Cenni di teoria della probabilità . . . 17

3.2 Modelli stocastici senza ritardi . . . 19

3.2.1 Introduzione generale e notazione . . . 19

3.2.2 Chemical Master Equation . . . 21

3.2.3 Algoritmo SSA . . . 22

3.3 Modelli stocastici con ritardi . . . 24

3.3.1 Delay Chemical Master Equation . . . 24

3.4 Algoritmo DSSA nelle varianti PDA e DPF . . . 26

3.4.1 Algoritmo DSSA PDA . . . 27

3.4.2 Algoritmo DSSA DPF . . . 30

4 Confronto sperimentale tra DSSA DPF e DSSA PDA 33 4.1 Esperimento 1 . . . 34

4.2 Esperimento 2 . . . 36

4.3 Esperimento 3 . . . 37

5 Confronto formale tra DSSA DPF e DSSA PDA 41 5.1 Algoritmi DPFD, PDAD e PDAR . . . 43

5.1.1 Algoritmo DPFD . . . 44

5.1.2 Algoritmo PDAR . . . 45

5.1.3 Algoritmo PDAD . . . 47

5.2 Sistemi di transizione . . . 48

5.2.1 Denizione (Sistema di transizione) . . . 49

5.2.2 Denizione (Sistema di transizioni etichettate) . . . 49

5.2.3 Sistema di transizione per DPFD . . . 49

5.2.4 Sistema di transizione per PDAR . . . 54

5.3 Confronto tra sistemi di transizioni etichettate . . . 58

5.4 Confronto tra PDAR e PDAD . . . 65

5.5 Conclusioni . . . 67

Capitolo 1

1 Introduzione

La biochimica è una scienza che studia tutte le forme di vita e utilizza concetti derivati dalla Biologia, dalla Chimica, dalla Fisica e dalla Matematica per raggiun-gere i suoi obbiettivi. Un importante campo della ricerca in biochimica è la biologia cellulare che studia la morfologia e l'organizzazione funzionale delle cellule. L'in-formatica e la Matematica possono aiutare la ricerca in biologia cellulare in diversi modi: possono, ad esempio, fornire ai biologi modelli e formalismi capaci di descri-vere e analizzare sistemi complessi come le cellule. Questo nuovo campo di ricerca è chiamato systems biology.

L'approccio tipico utilizzato per risolvere i problemi di systems biology è il seguente: il sistema biologico deve essere identicato in tutti i suoi componenti e devono es-sere identicati tutti gli eventi rilevanti. Questo è uno dei problemi maggiori perchè spesso non tutte le informazioni sono disponibili a causa della non osservabilità di alcuni eventi o della non completa conoscenza del sistema stesso. Parliamo in gen-erale di componenti ed eventi piuttosto che di molecole e reazioni perchè il campo di applicabilità della systems biology è più vasto della sola biochimica. Una volta che il sistema è stato identicato è possibile costruire un modello deterministico o stocastico. Il modello viene costruito usando i dati ottenuti osservando il sistema biologico reale e facendo, se necessario, delle assunzioni che abbiano un concreto signicato biologico. I modelli deterministici sono basati sulle equazioni dierenziali ordinarie che descrivono la variazione delle concentrazioni dei componenti coinvolti [19]. Tali modelli non sono sempre soddisfacenti: quando la dimensione del sis-tema biologico è piccola le simulazioni non mostrano alcuni comportamenti che vengono invece osservati negli esperimenti. In questi casi vengono utilizzati dei

modelli stocastici. I modelli stocastici di cui ci occupiamo nella tesi si basano sulla teoria cinetica delle collisioni molecolari. Tramite questa è possibile, per un dato sistema, denire una Chemical Master Equation (CME): una equazione dieren-ziale che descrive l'evoluzione nel tempo della probabilità che il sistema occupi uno stato determinato in un insieme discreto di stati [16, 17]. Oltre alla CME è stato denito da Gillespie un algoritmo di simulazione stocastica (Stochastic Simulation Algorithm o SSA) che calcola una traiettoria nello spazio degli stati del sistema modellato. Sfortunatamente l'algoritmo di Gillespie sore di problemi di scalabilità. Se il numero dei componenti coinvolti è alto la simulazione può essere estremamente lenta. Una importante estensione dei modelli citati è quella che consente di trattare sistemi biologici in cui le reazioni abbiano associato un ritardo. Per quanto riguar-da i modelli deterministici è possibile denire equazioni dierenziali con ritardi che modellano questo tipo di sistemi. Per quanto riguarda i sistemi stocastici è possi-bile denire una Delay Chemical Master Equation e un Delay Stochastic Simulation Algorithm[6, 25]. Di questo algoritmo possono essere denite diverse varianti. Questa tesi tratta del confronto, sperimentale e teorico, tra due varianti dell'algo-ritmo di simulazione stocastica: il Delay Stochastic Simulation Algorithm Purely Delayed Approach (o DSSA PDA) e il Delay Stochastic Simulation Algorithm De-layed Propensity Function (o DSSA DPF). I due algoritmi simulano l'evoluzione di un sistema biologico in cui avvengono reazioni che hanno associato un ritardo: un intervallo di tempo che intercorre tra l'inizio e la ne della reazione. In entrambi gli algoritmi il sistema biologico viene rappresentato da un vettore di interi, la variabile x, che evolve nel tempo, la variabile t, a seguito dell'esecuzione di reazioni: eventi casuali che vengono generati con una distribuzione nota. Lo scopo del confronto è quello di identicare le condizioni iniziali per cui l'evoluzione del sistema è la stessa nei due algoritmi. Il primo confronto eettuato è stato di tipo sperimentale: i risul-tati hanno mostrato che gli algoritmi, sotto opportune condizioni iniziali, hanno un

comportamento simile. Questo ha portato a supporre che, nelle stesse condizioni, soddisno una proprietà di equivalenza che può essere cosi formalizzata: dati i valori xie ti, le probabilità di raggiungere lo stato x = xi al tempo t = ti sono uguali nei

due algoritmi. Il secondo confronto eettuato è stato di tipo teorico. Sono state denite due versioni con tempo discreto del DPF e del PDA: rispettivamente DPFD e PDAD. Inoltre è stato denito un terzo algoritmo con caratteristiche intermedie tra i due: PDAR. Al DPFD e al PDAR sono stati associati due sistemi di transizioni etichettate che descrivono formalmente l'evoluzione delle variabili x e t e associano ad ogni reazione applicabile una probabilità. Sono state provate alcune proprietà dei due sistemi di transizione: è stato provato per gli algoritmi DPFD e PDAR che, dati i valori xi e ti, le probabilità di raggiungere lo stato x = xi al tempo t = ti

sono uguali a meno di una quantità trascurabile. Inne sono stati confrontati il PDAD e il PDAR e sono state provate alcune proprietà riguardanti la probabilità delle reazioni generate.

Abbreviazioni:

Le abbreviazioni utilizzate nella tesi sono le seguenti: ODE= Ordinary Dierential Equation

DDE= Delay Dierential Equation CME = Chemical Master Equation SSA = Stochastic Simulation Algorithm DCME = Delay Chemical Master Equation DSSA = Delay Stochastic Simulation Algorithm

PDA = Delay Stochastic Simulation Algorithm Purely Delayed Approach DPF = Delay Stochastic Simulation Algorithm Delayed Propensity Function PDAD = Delay Stochastic Simulation Algorithm Purely Delayed Approach Discreto

DPFD = Delay Stochastic Simulation Algorithm Delayed Propensity Function Dis-creto

PDAR = Delay Stochastic Simulation Algorithm Purely Delayed Approach Discreto Rilassato

1.1 Struttura della tesi

Il seguito della tesi è strutturato come segue:

Modelli deterministici di sistemi biologici: Introduce i modelli deterministici di sistemi biologici. Per i sistemi in cui le reazioni non hanno ritardi vengono presentate le equazioni dierenziali ordinarie. Per i sistemi in cui le reazioni hanno associato un ritardo vengono presentate le equazioni dierenziali con ritardi.

Modelli stocastici di sistemi biologici: Introduce i modelli stocastici di sistemi biologici. Per i sistemi in cui le reazioni non hanno ritardi viene introdotta la Chemical Master Equation e lo Stochastic Simulation Algorithm. Per i sistemi con ritardi la Delay Chemical Master Equation e gli algoritmi Delay Stochastic Simulation Algorithm Purely Delayed Approach (PDA) e Delay Stochastic Simulation Algorithm Delayed Propensity Function (DPF). Confronto sperimentale tra DPF e PDA: riporta i risultati del confronto

sper-imentale tra i due algoritmi.

Confronto formale tra DPF e PDA: riporta i risultati del confronto formale tra i due algoritmi. Piuttosto che lavorare sugli algoritmi originali si è preferi-to scrivere lo pseudocodice di tre nuovi algoritmi: il DPF discrepreferi-to, il PDA discreto e il PDA discreto rilassato. Questi algoritmi introducono notevoli

semplicazioni rispetto agli originali ma consentono di provare delle proprietà che possono aiutare a comprenderne il comportamento.

Capitolo 2

2 Modelli deterministici di sistemi biologici

2.1 Equazioni dierenziali ordinarie

I modelli deterministici di sistemi biologici sono i più utilizzati e diusi n dal secolo scorso. Questo tipo di modelli consiste in un insieme di equazioni dierenziali ordi-narie ( Ordinary Dierential Equation o ODE) che descrive, in generale, l'evoluzione nel tempo delle concentrazioni delle specie molecolari contenute in un dato volume. In matematica, una equazione dierenziale ordinaria è una relazione che contiene una funzione di un'unica variabile indipendente ed una o più delle sue derivate rispet-to a quella variabile. La forma generale di una equazione dierenziale ordinaria per X(t) ∈ R è

F (t, X(t), X0(t), X(2)(t), ...., X(n)(t)) = 0 con F : Ω ⊆ Rn+2_{−→ R, Ω 6= ∅ insieme aperto e connesso, n ∈ N}

Molto studio è stato dedicato alla soluzione di equazioni dierenziali ordinarie. Nel caso in cui l'equazione sia lineare può essere risolta con metodi analitici. Sfortu-natamente molte delle equazioni dierenziali interessanti sono non lineari e, con qualche eccezione, non possono essere risolte esattamente. Soluzioni approssimate sono ottenute da simulazioni numeriche sviluppate nello scorso secolo. Come es-empio di modello deterministico consideriamo uno dei primi modelli matematici di immunoterapia tumorale. Le variabili del modello sono la concentrazione di cellule tumorali, T (t), la concentrazione di cellule immunitarie, E(t), e la concentrazione di molecole di IL-2, IL, una citochina interleuchina che si è osservato stimola la

risposta del sistema immunitario ai tumori. Per un esame ravvicinato del modello facciamo riferimento a [19], qui riproduciamo semplicemente il modello e discuti-amo il modo in cui è costruito. Il modello consiste nel seguente insieme di equazioni dierenziali: dE dt = cT (t) − µ2E(t) + p1E(t)IL(t) g1+ IL(t) dT dt = r2T (t) − r2bT T (t) − aE(t)T (t) g2+ T (t) dIl dt = p2E(t)T (t) g3+ T (t) − µ3IL(t)

la prima equazione descrive la velocità di cambiamento per la popolazione di cellule immunitarie. La crescita delle difese immunitarie è stimolata da due termini. Il pri-mo è un termine di arruolamento, cT , dovuto alla presenza diretta del tupri-more, dove il parametro c modella gli antigeni del tumore. Il secondo è un termine di cresci-ta che indica la proliferazione dacresci-ta dallo IL-2 prodotto dalle cellule immunicresci-tarie. Questo termine è nella forma Michaelis Menten per indicare l'eetto di saturazione della risposta immunitaria. Il termine −µ2E modella invece il naturale ciclo di vita

delle cellule immunitarie che è lungo mediamente 1

2k giorni. La seconda equazione

rappresenta la velocità di cambiamento della popolazione di cellule tumorali. La crescita autolimitata viene descritta dal termine r2T − r2bT T. La perdita di cellule

tumorali è descritta dall'ultimo termine che rappresenta l'interazione con le cellule immunitarie al rate a. Questo rate costante a rappresenta l'intensità della risposta immunitaria ed è modellato dalla cinetica di Michaelis Menten. L'ultima equazione descrive la velocità di cambiamento per la concentrazione dello IL-2. Il termine pos-itivo è dato dalle cellule immunitarie che producono IL-2 stimolate dall'interazione con il tumore. Questo termine segue la cinetica di Michaelis Menten per tenere conto di fenomeni di autolimitazione della produzione di IL-2. Il termine −µ3IL

esaminato e, guardando sia all'evoluzione temporale delle simulazioni numeriche sia all'analisi delle posizioni di equilibrio del modello inteso come sistema dinami-co, vengono riportati molti risultati. In particolare vengono esaminati quattro casi dipendenti dai parametri e dalle condizioni iniziali: in un caso vi è una prevalenza della massa tumorale e negli altri tre casi si osservano oscillazioni della massa tu-morale e del numero di cellule immunitarie. In queste oscillazioni vengono raggiunti valori molto piccoli della massa tumorale e questo rappresenta un frangente in cui il modello stocastico serve a scoprire un comportamento interessante. Il modello sto-castico può descrivere evoluzioni in cui la massa tumorale diventa zero e il sistema immunitario eradica spontaneamente il tumore. Questo fenomeno può essere osser-vato in pratica ma non è predicibile esaminando le equazioni dierenziali. Questo genere di risultati rende evidente la motivazione principale per denire modelli sto-castici: il fatto che, sotto certe condizioni, questi modelli mostrano comportamenti che non sono osservabili attraverso le loro controparti deterministiche.

2.2 Equazioni dierenziali con ritardi

In matematica le equazioni dierenziali con ritardi (Delay Dierential Equation o DDE) sono equazioni dierenziali dove la derivata della funzione incognita calcolata al tempo t è espressa in funzione dei valori della funzione incognita in un tempo precedente a t. Le DDEs sono più generali delle ODEs ed è facile notare che le ODEs sono un caso particolare di DDEs in assenza di ritardi. Non tutti i risultati validi per le ODEs sono validi per le DDEs. La forma generale delle equazioni dierenziali con ritardi per X(t)∈ Rn _è:

dX

dove Xt= {X(t0) : t0 ≤ t}rappresenta la traiettoria delle soluzioni nel passato. Si

noti che questa formulazione è abbastanza generale da descrivere tutte le forme di ritardo che analizzeremo nel seguito.

2.2.1 Equazioni dierenziali con ritardo costante

In questa sezione studiamo le DDEs nella loro forma più semplice, ci riferiamo cioè alle DDEs con ritardo costante la cui forma generale è:

dX

dt = fx(t, X(t), X(t − σ1), ...., X(t − σn))

con σ1 > .... > σn ≥ 0 e σi ∈ R. Per introdurre questo strumento inizieremo

con un esempio. Consideriamo il modello di immunoterapia tumorale presentato in [4], una estensione del modello presentato in [19] e discusso nelle sezioni precedenti. Questo modello descrive le interazioni tra le cellule tumorali, le cellule immunitarie e una molecola, la interleuchina IL-2, che stimola la risposta immunitaria. Il modello in [19] è stato esteso aggiungendo un ritardo costante τ alla risposta del sistema immunitario in presenza di cellule tumorali. Questo ritardo è realistico e giusti-cato dalle osservazioni sperimentali. Il ritardo τ rappresenta il tempo necessario al riconoscimento della cellula tumorale e il tempo necessario alle cellule immunitarie per raggiungere il tumore. Il modello con ritardi è il seguente:

dE dt = cT (t − τ ) − µ2E(t) + p1E(t)IL(t) g1+ IL(t) dT dt = r2T (t) − r2bT T (t) − aE(t)T (t) g2+ T (t) dIl dt = p2E(t)T (t) g3+ T (t) − µ3IL(t)

dove il termine con ritardo è c(T − τ). Per una analisi ravvicinata del modello facciamo riferimento a [4].

2.2.2 Equazioni dierenziali con ritardo variabile

In questa sezione proponiamo lo studio di modelli deterministici di sistemi biologici con reazioni a ritardo variabile. In particolare nella letteratura è possibile osservare due tipi di ritardi: il primo riguarda i ritardi che dipendono dalla concentrazione delle specie, cioè le DDEs nella forma

dx

dt = fx(t, x(t), x(t − τ1(t, x(t)), ...., x(t − τn(t, x(t))))

dove τi(t, x(t)) : R+× Rn7→ R+ è una funzione del tempo e dello stato x(t) che

rappresenta il ritardo. La seconda riguarda i ritardi distribuiti cioè le DDEs della forma dx dt = fx(t, x(t), ˆ t −∞ γ(t0, x(t0))dt0) dove´t

−∞γ(t0, x(t0))dt0 è l'integrale sul tempo della funzione γ : R × R n

7→ R+

di tempo e stato. Questo genere di modelli può essere una estensione molto utile di quanto presentato nelle precedenti sezioni. Da un punto di vista applicativo potremmo voler modellare un sistema biologico in presenza di impulsi esterni. Nel caso in cui il tempo necessario a elaborare la risposta agli impulsi esterni sia sso allora aggiungere un ritardo sso dovrebbe essere suciente per modellare questa situazione. Invece se il sistema ha una memoria, cosa tipica dei sistemi cellulari più complessi, allora si può osservare che la risposta a una sequenza di impulsi simili richiede, per ogni impulso, una dierente quantità di tempo. In alcuni casi la quantità di tempo dipende dall'intervallo che intercorre tra due impulsi o dal numero

di risposte già date agli impulsi. Per modellare questo genere di comportamento può essere utilizzata la prima forma di ritardo variabile. Per modelli interessanti di DDE con ritardi variabili facciamo riferimento a [1, 2] dove viene presentato un modello di popolazione dinamica di mammiferi che fa uso di DDE con ritardi dipendenti dallo stato. I ritardi distribuiti, inne, sono una precisa rappresentazione del fatto che il ritardo dipende da più di un singolo stato del sistema. In particolare, dato che l'integrale calcola tutta l'area nell'intervallo di integrazione, questi modelli tengono in conto un insieme denso di stati passati piuttosto che un singolo stato.

Capitolo 3

3 Modelli stocastici di sistemi biologici

In questa sezione deniamo modelli stocastici per i sistemi biologici sia per reazioni senza ritardi che per reazioni che hanno associato un ritardo. Vengono introdotti inizialmente alcuni elementi di teoria della probabilità. Per i sistemi in cui le reazioni non hanno ritardi veongono introdotti la Chemical Master Equation e lo Stochastic Simulation Algorithm. Per i sistemi con ritardi vengono introdotti la Delay Chemical Master Equation e gli algoritmi Delay Stochastic Simulation Algorithm Purely De-layed Approach (PDA) e Delay Stochastic Simulation Algorithm DeDe-layed Propensity Function (DPF).

3.1 Cenni di teoria della probabilità

Una distribuzione di probabilità è una funzione che assegna ad ogni intervallo della retta reale una probabilità P (I) tale che gli assiomi di Kolmogorv siano soddisfatti:

1. per ogni intervallo I P (I) ≥ 0 2. P (R) = 1

3. per ogni insieme numerabile di intervalli I1, I2, ...., In tali che Ii∩ Ij = ∅se

i 6= j vale P (I1∪ I2... ∪ In) = n

P

i=1

P (Ii)

Una variabile casuale a dominio reale è una variabile il cui valore viene determinato casualmente. Ogni variabile casuale ha associata un propria distribuzione di

prob-abilità e questa distribuzione contiene molte delle informazioni importanti riguardo la variabile. Se X è una variabile casuale, la corrispondente distribuzione di prob-abilità assegna all'intervallo [a, b] la probprob-abilità P (a ≤ X ≤ b) cioè la probprob-abilità che la variabile X abbia un valore compreso nell'intervallo [a, b]. La distribuzione di probabilità di una variabile può essere univocamente descritta da una funzione di distribuzione cumulativa F (x) che è denita attraverso F (x) = P (X ≤ x) per ogni x ∈ R. Una distribuzione è chiamata discreta se la sua funzione di distribuzione cumulativa consiste di una serie di salti di ampiezza nita. La variabile casuale con una tale distribuzione è detta discreta: è una variabile i cui valori appartengono tutti ad un insieme numerabile o nito incluso in R. Una distribuzione è chiamata continua se la sua funzione di distribuzione cumulativa è continua. La variabile casuale con una tale distribuzione è tale che P (X = x) = 0 per ogni x ∈ R. Molte delle funzioni di distribuzione continue possono essere espresse da una funzione di densità di probabilità: una funzione non negativa, integrabile secondo Lebesgue, denita sulla retta reale e tale che per ogni a e b:

P (a < X < b) = ˆ b

a

f (x)dx

Il supporto di una distribuzione è il più piccolo insieme chiuso il cui complemento ha probabilità zero. Una importante funzione di distribuzione continua è la dis-tribuzione esponenziale che viene spesso utilizzata per modellare il tempo tra eventi indipendenti che avvengono con una frequenza media costante. Il supporto del-l'esponenziale è [0, ∞). La funzione di densità di probabilità di una distribuzione esponenziale ha la forma:

f (x, λ) = e−λx se x ≥ 0 f (x, λ) = 0se x < 0

dove λ è un parametro della distribuzione chiamato rate. La funzione di dis-tribuzione cumulativa è invece data da:

F (x, λ) = 1 − e−λx se x ≥ 0 F (x, λ) = 0se x < 0

La funzione di distribuzione esponenziale è usata per modellare i processi di Poisson che sono situazioni nelle quali un oggetto è inizialmente nello stato A e può cambiare passando allo stato B con una probabilità per unità di tempo λ. L'integrale da 0 a T di f è la probabilità che l'oggetto sia nello stato B al tempo T . In scenari tratti dal mondo reale l'assunzione di un rate (o probabilità per unità di tempo) costante viene raramente soddisfatta. Per esempio, il rate delle chiamate telefoniche in arrivo cambia durante la giornata. Ma se ci concentriamo su un intervallo di tempo in cui il rate è all'incirca costante, come dalle 2 alle 4 pomeridiane durante i giorni lavorativi, la distribuzione esponenziale può essere usata per modellare con buona approssimazione il tempo da attendere prima dell'arrivo della prossima chiamata. La media di una variabile casuale distribuita esponenzialmente con parametro λ è data da E[X] = 1

λ.

3.2 Modelli stocastici senza ritardi

In questa sezione discuteremo brevemente i modelli stocastici di sistemi biologi-ci. Nell'introduzione presenteremo la struttura dei modelli utilizzati che è comune a tutti gli algoritmi stocastici studiati nella tesi. Nei paragra successivi richiamer-emo la denizione di Chemical Master Equation e l'algoritmo di Gillespie per la simulazione stocastica.

3.2.1 Introduzione generale e notazione

Gli algoritmi di cui trattiamo simulano l'evoluzione nel tempo di un sistema biologico costituito da un insieme di n specie chimiche {S1, ..., Sn}e da m canali

interi non negativi x(t) dove ogni coordinata xi(t)rappresenta il numero di elementi

della specie chimica Si all'istante t. Si noti che il numero di elementi di una

specie chimica in un sistema reale è un intero non negativo e questo giustica le caratteristiche del vettore x. Un canale di reazione Rj è invece rappresentato

dalle seguenti quantità: la costante cinetica kj da cui, come vedremo, si calcola

la probabilità della reazione, il vettore di interi non negativi vr

j che rappresenta i

reagenti e il vettore di interi non negativi vp

j che rappresenta i prodotti. Per applicare

una reazione si eseguono due operazioni: si sottraggono i reagenti dal vettore di stato con x = x−vr

je si sommano i prodotti al vettore di stato con x = x+v p j. Se

lo stato non contiene i reagenti necessari per la reazione cioè se ∃ i : vr

ji> xi allora

la reazione non è applicabile. Si indica con vj la somma algebrica vpj− v r

j. Se una

reazione è applicabile si può aggiornare lo stato con un'unica operazione scrivendo x = x + vj. Un elemento utilizzato da tutti gli algoritmi di cui trattiamo è la

funzione di propensione aj(x(t))che trova la sua giusticazione nella sica teorica

[16] ed, in particolare, nella teoria cinetica delle collisioni. La aj(x(t))è denita

come la funzione tale che, dato dt un intervallo di tempo innitesimo, aj(x(t)) · dt

è la probabilità della funzione Rj di avvenire nell'intervallo [t, t + dt). La forma

generale della funzione di propensione è

aj(x) = kj· n Y i=1  xi vr ji  se ∀ i : vr

ji≤ xialtrimenti aj(x) = 0. Come si vede dalla denizione precedente se

la reazione Rj non è applicabile nello stato x(t) allora aj(x(t)) = 0.

Consideriamo, ad esempio, un sistema composto da quattro specie chimiche A, B, C, D e caratterizzato dalle seguenti reazioni:

R1 : A k1

−→ B e R2 : C k2

−→ 2 D dove k1 e k2 sono le costanti cinetiche delle due

reazioni. Il sistema verrà rappresentato da un vettore in N4_{. La prima componente}

el-ementi di B, la terza il numero di elel-ementi di C e la quarta il numero di elel-ementi di D. La reazione R1 sarà caratterizzata da vr1 = [1, 0, 0, 0] v

p

1 = [0, 1, 0, 0]. La

reazione R2 sarà caratterizzata da v2r= [0, 0, 1, 0] v p

2 = [0, 0, 0, 2]. Applicando la

reazione R1 al vettore x = [1, 1, 1, 1] otteniamo il vettore x − v1r+ v p

1= [0, 2, 1, 1].

3.2.2 Chemical Master Equation

In questa sezione richiamiamo la denizione, data da Gillespie in [16], di Chem-ical Master Equation. La CME è una equazione dierenziale del primo ordine che descrive l'evoluzione temporale della probabilità del vettore di stato del sistema di assumere il valore x al tempo t. Nella denizione data da Gillespie la quantità cruciale è P (x, t| x0, t0) ovvero la probabilità che, data la congurazione iniziale

x(t0) = x0, al tempo t il sistema sia descritto dal vettore di stato x. Per denire la

CME, cioè l'equazione che descrive la variazione di questa probabilità nell'intervallo di tempo innitesimo dt, viene studiata la quantitàP (x, t+dt|x0, t0). Questa

prob-abilità, assumendo che al più una reazione possa avvenire nell'intervallo di tempo [t, t + dt), è denita in termini di questi due eventi:

• al tempo t il sistema è già nello stato x e nell'intervallo innitesimo [t, t + dt) non avviene alcuna reazione.

• al tempo t il sistema è nello stato x−vje nell'intervallo innitesimo [t, t+dt)

avviene la reazione Rj.

Sommando le probabilità di questi due eventi otteniamo

P (x, t+dt|x0, t0) = P (x, t| x0, t0)·(1− m X j=1 aj(x)·dt)+ m X j=1 P (x−vj, t| x0, t0)·aj(x−vj)·dt

ter-mine rappresenta la probabilità del secondo evento. Sottraendo, dividendo per dt e prendendo il limite per dt che tende a zero otteniamo la CME:

∂P (x, t| xo, t0) ∂t = m X j=1 (P (x − vj| x0, t0) · aj(x − vj) − P (x, t| x0, t0) · aj(x))

Come mostrato in [16] questa equazione dierenziale è, in generale, dicile da risolvere, in particolare può essere risolta analiticamente solo per sistemi molto semplici e le soluzioni numeriche possono essere molto dicili da calcolare. Queste dicoltà giusticano l'introduzione di una tecnica di simulazione stocastica dei sistemi biologici alternativa. La CME rimane un'importante base concettuale per studiare i fondamenti matematici dell'algoritmo di simulazione stocastica.

3.2.3 Algoritmo SSA

In questa sezione richiamiamo la denizione di algoritmo di simulazione stocas-tica (Stochastic Simulation Algorithm o SSA) data da Gillespie in [16]. Assumiamo noti i concetti presentati nel paragrafo di introduzione generale. Lo scopo dell'al-goritmo è simulare l'evoluzione nel tempo del vettore di stato x(t) inizializzato con x(t0) = x0. L'algoritmo di Gillespie, dopo aver inizializzato x a x0e t a t0, entra in

un ciclo. Nel ciclo, ad ogni iterazione, genera un valore per τ, che rappresenta l'in-tervallo di tempo in cui nel sistema non avvengono reazioni, aggiorna il tempo con t = t + τ, sceglie una reazione j e aggiorna lo stato con x = x + vj. Esce dal ciclo

quando il valore di t ha superato la durata massima della simulazione T . Denita τ come la variabile casuale che indica la quantità di tempo in cui non avvengono reazioni, questa risulta essere distribuita esponenzialmente con parametro λ uguale a a0(x) =P

m

[0, 1]per estrarre un valore di τ è possibile estrarre un valore di r ed usare la formula

τ = 1 a0(x)

ln(1 r)

Denita j come la variabile casuale che indica la reazione da applicare al ter-mine di un intervallo di tempo in cui non avvengono reazioni, questa risulta essere una variabile discreta a valori in {1, 2, ..., m} tale che ∀i = 1, ..., m P (j = i) = ai(x(t))/a0(x(t)). Data una variabile casuale r distribuita unifomemente in [0, 1]

per estrarre un valore di j è possibile estrarre un valore di r ed usare la formula j =min{n|r ≤ Pn_i=1P (j = i)} o, equivalentemente, assegnare a j l'unico intero k che soddisfa k−1 X i=1 ai(x(t)) < a0(x(t)) · r ≤ k X i=1 ai(x(t))

Per la dimostrazione di correttezza di queste proprietà si veda [16]. Segue il codice dell'algoritmo:

Codice: 1 SSA() 2 { 3 x = x0; 4 t = t0; 5 while(t < T ) 6 { 7 calcola aj(x); 8 calcola a0(x) =P m j=1aj(x); 9 if(a0= 0) return; 10 genera r1, r2 in [0, 1]; 11 calcola τ = 1 a0ln( 1 r1)

12 calcola j =min{n| r2· a0(t) ≤P n j=1aj(x)}; 13 x = x + vj; 14 t = t + τ; 15 } 16 }

Notare che questo algoritmo è esatto nel senso che produce una traiettoria nello spazio degli stati del sistema. È importante dire che esistono diverse varianti del-l'algoritmo di Gillespie che dieriscono, tra le altre cose, nel modo in cui generano l'istante della reazione successiva o nel modo in cui scelgono quale reazione eseguire. La variante qui presentata è chiamata metodo diretto, un'altra presentata in letter-atura è il First Reaction Method [2]. Altri algoritmi per la simulazione stocastica di sistemi biologici possono essere trovati in [3] [5]. Tutti questi algoritmi sono simili e basati sull'idea denita da Gillespie.

3.3 Modelli stocastici con ritardi

In questa sezione discutiamo i modelli stocastici con ritardi. Deniremo una Delay Chemical Master Equation e diversi algoritmi di simulazione stocastica con ritardi. La motivazione per introdurre tali algoritmi è che la natura non determinis-tica di questo genere di simulazioni può mostrare, e conseguentemente giusticare, comportamenti che vengono osservati negli esperimenti ma che non sono descritti nei modelli deterministici.

3.3.1 Delay Chemical Master Equation

In questa sezione deriviamo, con gli stessi principi usati per derivare la CME, una Delay Chemical Master Equation per sistemi con ritardi costanti. Per denire la DCME identichiamo le quantità a cui siamo interessati che sono concettualmente simili a quelle usate per la denizione della CME. In particolare denotiamo con

P (x, t| x0, t0; ω)la probabilità che il sistema sia nello stato x al tempo t dati questi

due fatti: la congurazione iniziale x0, t0 e dato che abbiamo dei ritardi, il valore

dello stato in istanti precedenti a t0 che è determinato dlla funzione ω per cui vale

x(t) = ω(t)se t < t0. Si noti che la necessità di una funzione ω è dovuta al fatto che

all'istante t0il valore della propensity function di una generica reazione Rj dipende

dallo stato ad un istante t < t0 e, di conseguenza, non può essere calcolata senza

usare ω. In modo analogo a quanto fatto con la CME vogliamo denire la quantità P (x, t + dt|x0, t0; ω)assumendo che dt sia abbastanza piccolo che al massimo una

reazione avvenga nell'intervallo [t, t + dt) . Dobbiamo considerare i seguenti eventi

1. al tempo t il sistema è già nello stato x, al tempo t − σj il sistema era nello

stato xi e nell'intervallo [t, t + dt) non avviene nessuna reazione.

2. al tempo t il sistema è nello stato x − vj, al tempo t − σj il sistema era nello

stato xi e nell'intervallo [t, t + dt) avviene la reazione Rj.

Formalmente denotiamo con Q(x) l'insieme di tutti i possibili stati nei quali il sistema può trovarsi. Possiamo denire P (x, t + dt|x0, t0; ω)come segue:

P (x, t+dt|x0, t0; ω) = P (x, t|x0, t0; ω)·  1 − m X j=1 X xi∈Q(x) P (xi, t − σj|x, t, x0, t0; ω) · aj(xi)dt   + m X j=1 P (x − vj, t|x0, t0; ω)·   X xi∈Q(xi) P (xi, t − σj|x − vj, t, x0, t0; ω) · aj(xi)dt   Si noti che le quantità P (xi, t − σj|x, t, x0, t0; ω)e P (xi, t − σj|x − vj, t, x0, t0; ω)

denotano la probabilità che il sistema sia nello stato xi al tempo t − σj conoscendo

che si trova, rispettivamente, nello stato x e x−vjal tempo t. Dopo alcuni passaggi

∂P (x, t|x0, t0; ω) ∂t = m X j=1 X xi∈Q(x) P (x − vj, t; xi, t − σj|x0, t0; ω) · aj(xi) − m X j=1 X xi∈Q(x) P (x, t; xi, t − σj|x0, t0; ω) · aj(xi)

Si può provare che, in assenza di ritardi, la DCME si riduce alla CME. Inne possiamo notare che la DCME ha gli stessi svantaggi della CME: non può essere risolta analiticamente e le simulazioni numeriche possono essere dicili.

3.4 Algoritmo DSSA nelle varianti PDA e DPF

Questi algoritmi sono estensioni dell'algoritmo di Gillespie e servono a model-lare l'evoluzione di sistemi chimici o biologici in cui le reazioni possono avere dei ritardi. I ritardi vengono interpretati come una quantità costante di tempo che intercorre tra l'inizio e la ne di una reazione. Supponiamo, ad esempio, che τ sia l'intervallo di tempo, calcolato all'istante t, dopo il quale inizia la reazione Rj.

La reazione inizierà all'istante t + τ e terminerà all'istante t + τ + σj dove σj è il

ritardo della reazione Rj. Nella formulazione originale di Gillespie, che non

trat-ta i ritrat-tardi, le reazioni sono eventi istrat-tantrat-tanei e la loro applicazione avviene in un istante determinato t. In questa generalizzazione le reazioni hanno associato un ritardo, l'applicazione di una reazione ha quindi associati due istanti: l'istante di inizio della reazione t e l'istante in cui la reazione termina t+σ. A questo proposito bisogna fare due precisazioni. Nell'articolo [25] viene introdotto un algoritmo per la gestione dei ritardi in cui il vettore x viene aggiornato sia nell'istante di inizio che nell'istante di ne di una reazione. Nell'istante di inizio vengono sottratti i reagenti e nell'istante di ne vengono sommati i prodotti. Negli algoritmi di cui ci

occupiamo invece il vettore x viene aggiornato solo nell'istante in cui una reazione termina nel quale vengono sottratti i reagenti e sommati i prodotti. In questo caso, quindi, i ritardi vengono utilizzati per posticipare gli eetti della reazione lasciando la possibilità ai reagenti di essere coinvolti in altre reazioni. Nell'articolo originale di Gillespie, inoltre, l'algoritmo stocastico viene ricavato basandosi sull'assunzione che nell'intervallo innitesimo [t, t + dt) venga applicata una sola reazione e che la probabilità di applicare la reazione j sia aj(x(t)). Adesso che l'applicazione di una

reazione avviene in due momenti distinti bisogna capire come interpretare questa assunzione. L'interpretazione implicita fatta negli algoritmi per la gestione dei ri-tardi in [6], [25] è che nell'intervallo innitesimo [t, t + dt) inizi una sola reazione e che la probabilità, per la reazione j, di iniziare sia aj(x(t)). Il primo algoritmo di

cui ci occupiamo, il PDA, fa questa stessa assunzione. Il secondo algoritmo oggetto del confronto, il DPF, assume invece che nell'intervallo [t, t + dt) termini una sola reazione e che la probabilità, per la reazione j, di terminare sia aj(x(t − σj)).

3.4.1 Algoritmo DSSA PDA Introduzione:

Nel DSSA PDA gli eventi aleatori simulati sono gli inizi delle reazioni. La dierenza fondamentale tra il PDA e lo SSA è che nel PDA le reazioni possono essere schedu-late per essere eseguite in istanti futuri. Nel PDA viene utilizzata una struttura dati per memorizzare le reazioni schedulate e gli istanti in cui andranno applicate. L'algoritmo, dopo aver inizializzato x a x0e t a t0, entra in un ciclo. Nel ciclo, ad

ogni iterazione, genera un valore per le variabili τ e j. La variabile τ rappresenta il tempo da attendere prima dell'inizio della reazione successiva. La variabile j rapp-resenta quale tra le m reazioni sarà la prossima ad iniziare. Se viene generato un valore di τ tale che t + τ > tk dove tk è il primo istante in cui è schedulata una

e viene applicata la reazione schedulata con x = x + vk. Se invece non ci sono

reazioni schedulate o se t + τ ≤ tk allora il tempo viene aggiornato con t = t + τ

e viene eseguita la reazione j. Se la reazione scelta Rj ha un ritardo σj = 0viene

applicata immediatamente con x = x + vj. Se la reazione Rj ha un ritardo σj> 0

viene schedulata all'istante t + σj.

Variabili:

xvettore di interi che rappresenta lo stato tnumero reale che rappresenta il tempo

vp_j vettore di interi positivi indica i prodotti della reazione jesima j = 1, ...., m vr

j vettore di interi positivi indica i reagenti della reazione jesima j = 1, ...., m

vj v p

j − vrj viene sommato al vettore di stato per applicare la reazione jesima

j = 1, ...., m

σj ritardo della reazione jesima j = 1, ...., m

Llista che memorizza le reazioni schedulate. x0il valore a cui viene inizializzata x

t0 il valore a cui viene inizializzata t

T maxla durata massima della simulazione

Operazioni su L:

L.schedule(j, t): schedula la reazione j-esima al tempo t

L.getNextApplicable(t): restituisce la coppia [j, tk] dove tk è il primo istante

Funzioni ausiliarie:

acceptTau(t, τ, L): restituisce true se non ci sono reazioni schedulate applicabili o se dato [j, tk] =getNextApplicale(t) , t + τ ≤ tk. Restituisce false altrimenti.

Pseudocodice: 1 PDA() 2 { 3 x = x0,t = t0; 4 while(t < T max) 5 { 6 ∀j = 1, ...., mcalcola aj(x); 7 calcola a0(x) =P m j=1aj(x); 8 if(a0(x) = 0) return; 9 genera r1 in U[0, 1]; 10 calcola τ = 1 a0(t) ln  1 r1; 11 if( L = ∅ ∨acceptTau() ) 12 { 13 genera r2in U[0, 1]; 14 calcola j =min{n| r2· a0(x) ≤Pn_j=1aj(x)}; 15 t = t + τ; 16 if(σj= 0) x = x + vj; 17 else L.schedule(j, t + σj) 18 } 19 else 20 { 21 [j, tk] =getNextApplicable(); 22 x = x + vj;

23 t = t + tk; 24 } 25 } 26 } 3.4.2 Algoritmo DSSA DPF Introduzione:

Questo algoritmo è il più complesso di quelli presentati no ad ora. L'algoritmo, dopo aver inizializzato x a x0 e t a t0, entra in un ciclo. Nel ciclo, ad ogni

iterazione, calcola i valori delle propensity function ritardate aj(x(t − σj))e a0 = m

P

j=1

aj(x(t − σj)). Per eettuare questo calcolo l'algoritmo mantiene una struttuta

dati che memorizza le informazioni necessarie per determinare il valore di x(t0₎

con t0 _{in [t − max}m

j=1σj, t]. Questa struttura dati viene inizializzata con i valori

necessari a determinare x(t0_{)con t}0 _{in [t}

0− maxmj=1σj, t0] e viene aggiornata ad

ogni iterazione. Viene quindi generato un valore per τ. La variabile τ, una volta selezionata una reazione j, rappresenterà il tempo che intercorre tra l'istante t−σj e

l'istante di inizio della reazione j. Si noti che, quando viene generato τ, la reazione da eettuare non è ancora determinata e che il valore di τ dipende da a0 e quindi

da ogni aj. Una volta generato un valore di τ se esiste j tale che aj cambia valore

tra t − σj e t − σj+ τ allora τ viene scartato. Per controllare questa condizione

si procede come segue: per ogni j in {1, ., , , m} viene calcolato il valore di θj

denito come θj = t0− (t − σj)dove t0 è il primo istante successivo a t − σj in cui

cambia lo stato x. Sia θ il minimo su j di θj. Se τ≥θ τ viene scartato e il tempo

viene aggiornato con t = t + θ. Altrimenti viene selezionata una reazione Rj con

j =min{n| r2· a0 ≤P n

j=1aj}. La reazione inizia in t − σj+ τ e termina in t. Lo

t = t + τ.

Variabili:

xvettore di interi che rappresenta lo stato tnumero reale che rappresenta il tempo

vp_j vettore di interi positivi indica i prodotti della reazione jesima j = 1, ...., m vr_j vettore di interi positivi indica i reagenti della reazione jesima j = 1, ...., m vj v

p

j − v

r

j viene sommato al vettore di stato per applicare la reazione jesima

j = 1, ...., m

σj ritardo della reazione jesima j = 1, ...., m

Luna lista che memorizza le informazioni necessarie a determinare gli stati attraver-sati dal sistema nell'intervallo [t − maxm

j=1σj, t]

x0il valore a cui viene inizializzata x

t0 il valore a cui viene inizializzata t

L0 una lista che memorizza gli stati attraversati dal sistema nell'intervallo [t0−

maxm_j=1σj, t0]

T maxla durata massima della simulazione

Operazioni su L:

L.getState(t0): se t' è in [t − maxm_j=1σj, t] restituisce lo stato a cui si trova il

sistema al tempo t'

L.getNextChangeTime(t0): se t0 è in [t − maxm_j=1σj, t] restituisce l'istante del

primo cambiamento di stato avvenuto in (t0_{, t]restituisce null se il sistema non ha}

Pseudocodice: 1 DPF() 2 { 3 x = x0, t = t0, L = L0; 4 while(t < T max) 5 { 6 ∀j calcola aj(L.getState(t − σj)); 7 calcola a0=P m j=1aj;

8 if(a0= 0 ∧ ∀j = 1, ..., m L.getNextChangeTime(t − σj)=null) esci

9 genera r1 in U[0, 1]; 10 if( a0= 0) τ = +∞; 11 else τ = 1 a0(t) ln  1 r1;

12 if( ∀j = 1, ..., m L.getNextChangeTime(t − σj)=null) θ = +∞;

13 else θ =minm j=1{L.getNextChangeTime(t − σj)} 14 if( τ< θ) 15 { 16 genera r2in U[0, 1]; 17 calcola j =min{n| r2· a0≤P n j=1aj}; 18 t = t + τ; 19 x = x + vj; 20 } 21 else t = t + θ; 22 } 23 }

Capitolo 4

4 Confronto sperimentale tra DSSA DPF e DSSA

PDA

In questa sezione presentiamo i risultati del confronto sperimentale tra DPF e PDA. Lo scopo del confronto è di identicare le condizioni iniziali per cui i due algoritmi sono equivalenti. La proprietà di equivalenza che vogliamo investigare è la seguente: date le opportune condizioni iniziali, di cui discuteremo nelle conclusioni, dati i valori xi e ti, le probabilità di raggiungere lo stato x = xi al tempo t = ti sono uguali.

Nessuno degli esperimenti considerati testa, in generale, la proprietà suddetta. I pri-mi due esperimenti sono di tipo esplorativo e sono serviti a deterpri-minare le condizioni iniziali per cui gli algoritmi hanno un comportamento 'simile' e per cui crediamo che sia vericata la proprietà. Come vedremo in questi due esperimenti viene mis-urata la probabilità di raggiungere un dato valore di x al termine dell'esecuzione ma non vengono raccolte informazioni sul valore della variabile t quindi non viene testata la proprietà di interesse. Nel terzo esperimento si eettua il calcolo di al-cune grandezze statistiche sull'insieme dei valori assunti dalla variabile x al termine dell'esecuzione. Per eettuare gli esperimenti i due algoritmi sono stati implemen-tati in Java: bisogna notare che il codice degli algoritmi utilizzato calcola il valore corretto di aj(x)solo nel caso in cui per la reazione j valga ∀ i vrji<= 1. Per

gen-eralizzarlo in modo che tratti reazioni qualsiasi basta inserire un codice ecente per il calcolo della binomiale in aj(x). Negli esperimenti eettuati le reazioni utilizzate

soddisfano tutte la proprietà suddetta. Bisogna notare, inoltre, che il codice degli algoritmi è stato testato solo per eettuare gli esperimenti di cui si tratta in questo

capitolo e potrebbe, in altri casi, generare risultati non corretti.

4.1 Esperimento 1

Introduzione:

Nel primo esperimento gli algoritmi vengono inizializzati con lo stesso insieme di reazioni {R1, R2}, lo stesso stato iniziale x0, lo stesso istante iniziale t0e lo stesso

limite temporale T . Le reazioni e lo stato iniziale forniti sono tali che può essere applicata solo una reazione. Lo stato iniziale è il vettore [1, 0, 0]. Applicando la reazione R1 si raggiunge lo stato [0, 1, 0] da cui non è possibile applicare nessuna

reazione. Applicando la reazione R2 si raggiunge invece lo stato [0, 0, 1] da cui

comunque non è possibile applicare nessuna reazione. Come si vede dunque al termine della prima applicazione non ci sono più reazioni applicabili e gli algoritmi terminano. In entambi gli algoritmi gli stati raggiungibili al termine dell'esecuzione sono due: [0, 1, 0] e [0, 0, 1]. Viene eseguito un numero statisticamente signicativo di simulazioni e, per ciascun algoritmo, viene contato il numero di esecuzioni in cui raggiunge il primo stato e il numero di esecuzioni in cui raggiunge il secondo. Da questi due numeri e dal numero complessivo di esecuzioni svolte si ottengono le probabilità di raggiungere il primo e il secondo stato. I valori di queste probabilità nei due algoritmi vengono inne confrontati. Come si vede sono uguali no alle prime due cifre dopo la virgola. L'algoritmo DPF, come già detto, utilizza anche una struttura dati che contiene le informazioni per determinare il valore di x(t0₎

per t0 _{in [t − max}m

j=1σj, t]. Tale struttura dati viene inizializzata in modo che il

valore restituito per t0_{in [t}

0− maxmj=1σj, t0]sia il vettore [0, 0, 0] che rappresenta lo

stato vuoto. Se la struttura dati viene inizializzata diversamente le due probabilità diventano dierenti. Questo ci ha portato a supporre che la proprietà di equivalenza valga solo nel caso in cui la lista viene cosi inizializzata.

Dati e risultati:

Vengono quindi eseguiti gli algoritmi e viene controllato il valore di x quando ter-minano. In entrambi gli algoritmi i valori possibili di x al termine dell'esecuzione sono due: [0, 1, 0] o [0, 0, 1].

Vengono eseguite le seguenti misure: Siano x1= [0, 1, 0]e x2= [0, 0, 1]

NP DA(xi) =numero di esecuzioni del PDA in cui x al termine dell'esecuzione è xi.

NDP F(xi) =numero di esecuzioni del DPF in cui x al termine dell'esecuzione è xi.

Da cui si calcolano le seguenti quantità:

PP DA(xi) =NP DA(xi)/(NP DA(x1) + NP DA(x2))

PDP F(xi) = NDP F(xi)/(NDP F(x1) + NDP F(x2))

Si noti che, al crescere del numero di esecuzioni su cui si fanno le misure, PP DA(x)

e PDP F(x)tendono rispettivamente alla probabilità che il PDA termini nello stato

xed alla probabilità che il DPF termini nello stato x. Riportiamo i risultati rela-tivi ad un caso d'esempio. Dopo 104_{esecuzioni con i seguenti valori dei parametri}

σ1 = 2, k1 = 0.8, σ2 = 1.6, k2 = 0.1 i risultati sono PP DA(x1) = 0.853225,

4.2 Esperimento 2

Introduzione:

Nel secondo esperimento gli algoritmi vengono inizializzati con lo stesso insieme di reazioni {R1, R2}, lo stesso stato iniziale x0, lo stesso istante iniziale t0e lo stesso

limite temporale T . Le reazioni e lo stato iniziale forniti sono tali che possono essere applicate solo due reazioni. Lo stato iniziale è il vettore [2, 0, 0]. Applicando la reazione R1due volte si raggiunge lo stato [0, 2, 0] da cui non è possibile applicare

nessuna reazione. Applicando la reazione R2 due volte si raggiunge lo stato [0, 0, 2]

da cui non è possibile applicare nessuna reazione. Applicando le reazioni R2 e la

R1 in una qualsiasi sequenza si raggiunge lo stato [0, 1, 1] da cui non è possibile

applicare nessuna reazione. In entrambi gli algoritmi gli stati raggiungibili al termine dell'esecuzione sono tre: [0, 2, 0], [0, 0, 2] e [0, 1, 1]. Viene eseguito un numero statisticamente signicativo di simulazioni e, per ciascun algoritmo, viene contato il numero di esecuzioni in cui raggiunge ciascuno degli stati nali possibili. Da questi due numeri e dal numero complessivo di esecuzioni svolte si ottengono le probabilità di raggiungere ciascuno degli stati nali. I valori di queste probabilità nei due algoritmi vengono inne confrontati. Come si vede sono uguali no alle prime due cifre dopo la virgola. Anche in questo caso valgono le stesse considerazioni del caso precedente sul valore iniziale della struttura dati utilizzata dal DPF.

Dati e risultati:

Nel secondo esperimento gli algoritmi vengono inizializzati con lo stesso insieme di regole {R1, R2}, lo stesso stato iniziale x0, lo stesso istante iniziale t0 e lo stesso

limite temporale T . Le regole sono: R1: vr1= [1, 0, 0] v

p

R2: vr2= [1, 0, 0] v p

2= [0, 0, 1] σ2k2

Lo stato iniziale è: x0= [2, 0, 0]

L'istante iniziale è: t0= 0

Vengono quindi eseguiti gli algoritmi e viene controllato il valore di x quando ter-minano. In entrambi gli algoritmi i valori possibili di x al termine dell'esecuzione sono tre: [0, 2, 0], [0, 0, 2] e [0, 1, 1].

Vengono eseguite le seguenti misure:

Siano x1= [0, 2, 0]e x2= [0, 0, 2]e x3 = [0, 1, 1]

NP DA(xi) =numero di esecuzioni del PDA in cui x al termine dell'esecuzione è xi.

NDP F(xi) =numero di esecuzioni del DPF in cui x al termine dell'esecuzione è xi.

Da cui si calcolano le seguenti quantità:

PP DA(xi) =NP DA(xi)/(NP DA(x1) + NP DA(x2) + NP DA(x3))

PDP F(xi) = NDP F(xi)/(NDP F(x1) + NDP F(x2) + N (x3))

Si noti che, al crescere del numero di esecuzioni su cui si fanno le misure, PP DA(x)

ePDP F(x)tendono rispettivamente alla probabilità che il PDA termini nello stato

xed alla probabilità che il DPF termini nello stato x. Riportiamo i risultati rela-tivi ad un caso d'esempio. Dopo 104 _{esecuzioni per i seguenti valori dei parametri}

σ1 = 2, k1 = 0.8, σ2 = 1.6, k2 = 0.1 i risultati sono PP DA([0, 2, 0]) = 0.7285,

PP DA([0, 0, 2]) = 0.0249, PP DA([0, 1, 1]) = 0.2466 PDP F([0, 2, 0]) = 0.7345,

PDP F([0, 0, 2]) = 0.0228, PDP F([0, 1, 1]) = 0.2427.

4.3 Esperimento 3

Introduzione:

Nel terzo esperimento gli algoritmi vengono inizializzati con lo stesso insieme di reazioni {R1, R2}, lo stesso stato iniziale x0, lo stesso istante iniziale t0e lo stesso

gli algoritmi proseguono no a raggiugere il limite temporale T . Il vettore di stato al termine dell'esecuzione può essere considerato una variabile casuale di cui vengono misurate media e varianza. I valori misurati nei due algoritmi vengono confrontati.

Dati e risultati:

Nel terzo esperimento gli algoritmi vengono inizializzati con lo stesso insieme di regole {R1, R2}, lo stesso stato iniziale x0, lo stesso istante iniziale t0 e lo stesso

limite temporale T . Le regole sono: R1: vr1= [1] v p 1= [0] σ1k1 R2: vr2= [1] v p 2= [2] σ2k2

L'algoritmo DPF, come già detto, utilizza anche una lista che contiene le infor-mazioni per determinare il valore di x(t0_{) per t}0 _{in [t − max}m

j=1σj, t]. Tale lista

viene inizializzata in modo che il valore restituito per t0_{in [t}

0− maxmj=1σj, t0] sia

il vettore [0] che rappresenta lo stato vuoto. Vengono quindi eseguiti gli algoritmi e viene controllato il valore di x quando terminano. Vengono calcolate le seguenti quantità:

EP DA(x) =valore medio di x nel PDA.

V ARP DA(x) =varianza x nel PDA.

EDP F(x) =valore medio di x nel DPF.

V ARDP F(x) =varianza x nel DPF.

Riportiamo i risultati relativi ad un caso d'esempio. Dopo 102_{esecuzioni per i}

seguen-ti valori dei parametri σ1 = 2, k1= 0.1, σ2= 1.6, k2 = 0.9, x0= [24], T = 10, i

risultati sonoEP DA(x) = 949.45, V ARP DA(x) = 113.6021, EDP F(x) = 947.81,

Conclusioni:

Nessuno degli esperimenti considerati testa la proprietà di equivalenza che riteniamo essere soddisfatta dai due algoritmi DPF e PDA. I risultati sperimentali mostrano però che i due algoritmi hanno un comportamento 'simile' in certe condizioni e questo ci ha portato a concludere che, nelle stesse condizioni, valga tale proprietà. Le condizioni per cui crediamo che valga la proprietà di equivalenza sono: valore iniziale di t, t0, uguale nei due algoritmi, valore iniziale di x, x0, uguale nei due

algoritmi e lista utilizzata dall'algorimo DPF inizializzata in modo che il valore restituito per t in [t0− maxmj=1σj, t0] sia il vettore con tutte le componenti nulle.

Capitolo 5

5 Confronto formale tra DSSA DPF e DSSA PDA

Visti i risultati sperimentali è stato eettuato un confronto teorico tra i due algorit-mi a cui è dedicata questa sezione. Piuttosto che lavorare sugli algoritalgorit-mi originali si è preferito scrivere lo pseudocodice di tre nuovi algoritmi: il DPF discreto (DPFD), il PDA discreto (PDAD) e il PDA discreto rilassato (PDAR). Questi algoritmi intro-ducono notevoli semplicazioni rispetto agli originali ma consentono di provare delle proprietà che possono aiutare a comprenderne il comportamento. In particolare è possibile provare che, per gli algoritmi DPFD e PDAR, vale una proprietà analoga a quella che riteniamo valga per Il DPF e Il PDA. Nel seguito del capitolo proveremo che, per il DPFD e il PDAR, dati i valori xi e ti, le probabilità di raggiungere lo

stato x = xi al tempo t = ti sono uguali a meno di una quantità trascurabile.

Discutiamo ora le caratteristiche di questi algoritmi.

1. Tempo discreto: L'assunzione di base fatta da Gillespie è che, se i reagenti si trovano in equilibrio termico all'interno di un volume ssato, la probabilità che una reazione Rj occorra nell'intervallo di tempo innitesimo [t, t + dt) si

può esprimere come aj(x(t)) · dt. In questi algoritmi assumiamo che esista un

numero δt in R molto minore di uno tale che la probabilità che una reazione Rj

occorra nell'intervallo di tempo [t, t + δt) si può esprimere come aj(x(t)) · δt.

Negli algoritmi la variabile t viene inizializzata a t0 e viene incrementata, ad

ogni iterazione, della quantità δt. I ritardi delle reazioni sono maggiori di zero e multipli interi di δt. Gli eetti delle reazioni che terminano in [t, t + δt) vengono applicati prima di generare le reazioni che iniziano in [t, t + δt).

2. Generazione di eventi reazione: L'introduzione dei ritardi ha portato a reazioni che hanno associato un istante d'inizio e un istante di ne separati da un intervallo di tempo: il ritardo della reazione. Nel PDA con tempo continuo ad ogni istante può iniziare al più una reazione mentre può terminare un numero di reazioni distinte compreso tra 0 ed m. Nel DPF a tempo continuo nello stesso istante può terminare al più una reazione mentre può iniziare un numero di reazioni distinte compreso tra 0 ed m. Lo stesso accade nelle versioni a tempo discreto PDAD e DPFD. Il PDAR il vincolo sulle reazioni iniziali viene rilassato quindi ad ogni istante può iniziare un numero di reazioni distinte compreso tra 0 ed m e terminare un numero di reazioni distinte compreso tra 0ed m.

Il confronto si propone di associare al DPFD e al PDAR due sistemi di transizioni etichettate attraverso cui associare a ciascun assegnamento eettuabile una proba-bilità. Assumendo che i due algoritmi abbiano attraversato gli stessi stati vengono quindi fatti i seguenti due confronti:

1. Assegnamenti eettuabili: il numero di assegnamenti diversi eettuabili nel PDAR è maggiore del numero di assegnamenti diversi eettuabili nel DPFD ma gli assegnamenti che si possono fare nel PDAR e non nel DPFD hanno associata un probabilità trascurabile.

2. Probabilità di eettuare lo stesso assegnamento: risultano uguali a meno di un termine trascurabile.

Basandosi su queste proprietà viene inne provato che, dati i valori xi e ti, le

algoritmi a meno di una quantità trascurabile. Questo conclude il confronto tra il DPFD e il PDAR. Vengono inne confrontati il PDAR e il PDAD e, in particolare, vengono fatti i seguenti due confronti:

1. Eventi di inizio reazione generati in uno stesso istante: il PDAR genera più eventi rispetto al PDAD ma gli eventi generati nel PDAR e non nel PDAD hanno associata una probabilità trascurabile.

2. Probabilità di generare lo stesso evento di inizio reazione: risultano uguali a meno di un termine trascurabile.

Nel seguito del capitolo vedremo i seguenti argomenti:

1. Pseudocodice dei tre algoritmi.

2. Denizione dei sistemi di transizione per il DPFD e il PDAR. 3. Confronto tra i sistemi di transizione.

4. Confronto tra il PDAR e il PDAD.

5.1 Algoritmi DPFD, PDAD e PDAR

per ogni algoritmo vengono riportate, oltre allo pseudocodice, le variabili utilizzate ed eventuali funzioni ausiliarie.

5.1.1 Algoritmo DPFD

Variabili:

xvettore di interi che rappresenta lo stato tnumero reale che rappresenta il tempo

vp_j vettore di interi positivi che indica i prodotti della reazione jesima j = 1, ...., m vr

j vettore di interi positivi che indica i reagenti della reazione jesima j = 1, ...., m

vj v p j − v

r

j viene sommato a x per applicare la reazione jesima j = 1, ...., m

σj ritardo della reazione jesima j = 1, ...., m

L lista di coppie [t, x] con t reale x vettore di interi ordinata sul primo elemento [t1, x1] : [t2, x2]....[tn, xn]con tn> .... > t2> t1

T indica la durata della simulazione x0il valore a cui viene inizializzata x

t0 il valore a cui viene inizializzata t

L0 il valore a cui viene inizializzata L

Operazioni sulla lista degli stati:

L.get(t): restituisce lo stato corrispondente a t L.add(x, t): inserisce [t, x] in coda alla lista

Pseudocodice:

1 DPFD() 2 {

4 while (t ≤ T ) do 5 { 6 ∀j = 1, .., mcalcola pj= aj(L.get(t − σj))·δt; 7 genera r in U[0, 1]; 8 calcola k =min{n| r ≤ Pn j=1pj}; 9 if(k ≤ m) x =apply(x, k); 10 L.add(x, t); 11 t = t + δt; 12 } 13 } Funzioni ausiliarie: 1 apply(x, j) 2 { 3 if(vr j ≤ x) x = x + vj; 4 } 5.1.2 Algoritmo PDAR Variabili:

xvettore di interi che rappresenta lo stato tnumero reale che rappresenta il tempo

vp_j vettore di interi positivi che indica i prodotti della reazione jesima j = 1, ...., m vr

j vettore di interi positivi che indica i reagenti della reazione jesimaj = 1, ...., m

σj ritardo della reazione jesima j = 1, ...., m

L lista di coppie [t, I] con t reale, I ⊆ {R1, R2, ...., Rn} ordinata sul primo

ele-mento. I rappresenta l'insieme di reazioni da applicare al tempo t T indica la durata della simulazione

x0il valore a cui viene inizializzata x

t0 il valore a cui viene inizializzata t

Operazioni su L:

L.schedule(j, t): se t appartiene a L inserisce Rj nell'insieme di reazioni associato

a t. Altrimenti aggiunge a L un nuovo elemento [t, {Rj}] rispettando l'ordine. L.get(t): se t appartiene a L restituisce l'insieme di reazioni associato a t. Resituisce l'insieme vuoto se t non appartiene a L.

Pseudocodice: 1 PDAR() 2 { 3 x = x0; t = t0; 4 while (t ≤ T ) 5 { 6 I = L.get(t);

7 if(I6= ∅) x =apply(x, I);

8 ∀j = 1, ..., mcalcola pj = aj(x) · δt;

9 genera r1, ...., rmin U[0, 1];

10 ∀j = 1, ..., m if( rj≤ pj ) L.schedule(j, t + σj);

12 } 13 } Funzioni ausiliarie: 1 apply(x, I) 2 { 3 for(j = 1; j ≤ m; j + +) 4 if(Rj ∈ I ∧ vrj ≤ x) 5 x = x + vj; 6 } 5.1.3 Algoritmo PDAD Variabili: come PDAR Operazioni su L: come PDAR Pseudocodice: 1 PDAR() 2 {

3 x = x0; t = t0

4 while (t ≤ T ) 5 {

6 I = L.get(t);

7 if(I 6= ∅) x = apply(x, I);

8 ∀j = 1, ...., mcalcola pj = aj(x) · δt; 9 genera r in U[0, 1]; 10 calcola k=min{n|r ≤ Pn j=1pj}; 11 if(k ≤ m) L.schedule(k, t + σk); 12 t = t + δt; 13 } 14 } Funzioni ausiliarie: 1 apply(x, I) 2 { 3 for(j = 1; j ≤ m; j + +) 4 if(Rj ∈ I ∧ vrj ≤ x) 5 x = x + vj; 6 }

5.2 Sistemi di transizione

Richiamiamo prima la denizione di sistema di transizione e di sistema di transizioni etichettate.

5.2.1 Denizione (Sistema di transizione)

Un sistema di transizione è una coppia (S, →) dove S è l'insieme degli stati S = {s0, s1, ..., sn}e →⊆ S ×S è la relazione di transizione. Scriviamo si→ sjquando

(si, sj) ∈→.

5.2.2 Denizione (Sistema di transizioni etichettate)

Un sistema di trasizioni etichettate è una tripla (S, L, →) dove S è l'insieme degli stati S = {s0, s1, ...} Lè l'insieme delle etichette L = {l, l1; ..., ln}e →⊆ S×L×S

è la relazione di transizione. Scriviamo si l

→ sj quando (si, l , sj) ∈→.

5.2.3 Sistema di transizione per DPFD

Introduzione

Vogliamo denire un sistema di transizioni etichettate che tenga traccia dei valori as-segnati alle variabili x e t e delle probabilità di eettuare ogni singolo assegnamento. Per calcolare le probabilità deniamo prima i seguenti eventi rilevanti.

Denizione (Eventi X, E ed I)

Eventi riguardanti una esecuzione del DPFD:

X(i, j) =durante l'iterazione i-esima viene eseguito l'assegnamento x =apply(x, j) E(i, xi) =il valore assunto da x al termine dell'iterazione i-esima è xi

Probabilità di un generico assegnamento

osserviamo quindi che la seguente probabilità:

pj = P (X(n + 1, j)|I(L0, x0)E(1, x1)E(2, x2)....E(n, xn))

dati i valori L0, x0, x1,..., xnè univocamente determinata e rappresenta la

probabil-ità che durante l'iterazione n+1 esima venga eseguito l'assegnamento x =apply(x, j). Calcoliamo questa probabilità nel caso particolare in cui L0= ε dove con ε

desig-niamo la lista che contiene solo lo stato vuoto identicato dal vettore con tutte le componenti nulle che indichiamo con 0. Se t è il valore del tempo all'iterazione n + 1: pj= aj(x(t−σj))·δt = aj(x_n+1−σj δt )·δt se t−σj ≥ 0 cioè n+1− σj δt ≥ 0 (1) pj= 0 se t − σj< 0 cioè n + 1 − σj δt < 0

si noti che le reazioni hanno tutte ritardo maggiore di zero e multiplo intero di δt quindi n + 1 −σj

δt è un intero e il suo valore massimo è n. Nell'ultima espressione

abbiamo usato il fatto che se t − σj< 0allora lo stato corrispondente si trova in ε

che contiene solo lo stato vuoto 0 e aj(0) = 0per ogni j.

Denizione (insiemi degli stati e delle etichette)

Stato iniziale: lo stato iniziale s0 viene rappresentato con una tripla < ε, x0, t0>

Altri stati: un generico stato diverso da s0 viene rappresentato da una quadrupla

< i, x, t, j >dove: iè l'indice dell'iterazione

tè il valore della variabile t al termine dell'iterazione i-esima

j è un intero compreso tra zero ed m. Se è zero allora all'iterazione i-esima non è stata eseguita la apply se è diverso da zero allora all'iterazione i-esima è stata eseguita x =apply(x, j).

Etichette: numeri reali in [0, 1]

Denizione (regole di transizione) Prima regola: t0≤ T pj = P (X(1, j)|I(ε, x0)) x1=apply(x0, j) j = 1, ...., m < ε, x0, t0> pj −→< 1, x1, t0+ δt, j > Seconda regola: t0≤ T pj = P (X(1, j)|I(ε, x0)) p = 1 − m X j=1 pj < ε, x0, t0> p −→< 1, x0, t0+ δt, 0 > Terza regola: tn≤ T < , x0, t0> p(1) −→< 1, x1, t1, j1>, ...., < n−1, xn−1, tn−1, jn−1> p(n) −→< n, xn, tn, jn>

pj = P (X(n + 1, j)|I(ε, x0)E(1, x1)E(2, x2)....E(n, xn)) xn+1=apply(xn, j) j =1, ...., m

< n, xn, tn, jn > pj

−→< n + 1, xn+1, tn+ δt, j >

tn≤ T < , x0, t0> p(1)

−→< 1, x1, t1, j1>, ...., < n−1, xn−1, tn−1, jn−1> p(n)

−→< n, xn, tn, jn>

pj= P (X(n + 1, j)|I(ε, x0)E(1, x1)E(2, x2)....E(n, xn)) p = 1 − m X j=1 pj < n, xn, tn, jn> p −→< n + 1, xn, tn+ δt, 0 >

Denite le ragole di transizione vogliamo adesso dare alcune denizioni. Vogliamo denire l'insieme degli stati che possono essere raggiunti partendo dallo stato iniziale s0 e applicando le regole del sistema di transizione. Ad ogni stato raggiungibile s

vogliamo associare la lista di operazioni che sono state eseguite durante le iterazioni che hanno portato da s0 a s e la probabilità di eseguire tale lista di operazioni.

Denizione (insieme degli stati raggiungibili)

Dato lo stato iniziale < ε, x0, t0>l'insieme degli stati raggiungibili R(< ε, x0, t0>)

è un sottoinsieme di S denito come segue: < ε, x0, t0>∈ R(< ε, x0, t0>).

se esistono s0 _{∈ R(< ε, x}

0, t0 >) ed l in L tali che (s0, l, s00)∈→ allora s00 è in

R(< ε, x0, t0>).

Denizione(lista di operazioni di uno stato raggiungibile)

Dato s in R(< ε, x0, t0 >) la lista di operazioni di s L(s) è una lista ordinata di

L:= empty|L.add(I)

dove I ⊆ {R1, ..., Rm}denita come segue:

L(< ε, x0, t0>)=empty.

se esistono s0_{in R(< ε, x}

0, t0>)ed l In L tali che (s0, l, s00)∈→ed s00=< i, x, t, j >

con j 6= 0 allora L(s00_)=L(s0_).add({R j}).

se esistono s0_{in R(< ε, x}

0, t0>)ed l In L tali che (s0, l, s00)∈→ed s00=< i, x, t, j >

con j = 0 allora L(s00_)=L(s0_).add(∅).

Denizione (probabilità di uno stato raggiungibile)

Dato s in R(< ε, x0, t0>)la probabilità di s p(s) è denita come segue:

p(< ε, x0, t0>) = 1.

se esistono s0 _{in R(< ε, x}

0, t0 >) ed l in L tali che (s0, l, s00) ∈→ allora p(s00) =

p(s0) · l.

Considerazioni nali:

osserviamo che dato uno stato s raggiungibile se ts≤ T esistono m + 1 transizioni

che hanno s come stato di partenza: una transizione per ognuno degli m possibili parametri della apply più una transizione per l'eventualità in cui la apply non viene eseguita. Ricordiamo che la probabilità di eettuare un transizione in un dato stato dipende dagli stati attraversati in precedenza durante l'esecuzione e dal valore di inizializzazione della lista e, nel caso particolare della lista ε, è data dalla formula 1.

5.2.4 Sistema di transizione per PDAR

Introduzione

Vogliamo denire un sistema di transizioni etichettate che tenga traccia dei valori assegnati alle variabili x e t e delle probabilità di eettuare ogni singolo asseg-namento. Si osservi che, a dierenza del caso precedente, in una iterazione può essere eseguita più di una reazione. In particolare possono essere eseguite no ad m reazioni distinte. La funzione apply prende in input l'insieme delle reazioni da applicare cioè uno dei possibili sottoinsiemi di {R1, ...., Rm} diverso dall'insieme

vuoto. Per calcolare le probabilità deniamo prima gli eventi rilevanti.

Denizione (Eventi X', E' ed I')

Eventi riguardanti una esecuzione del PDAR:

X0(i, L) =durante l'iterazione i-esima viene eseguito l'assegnamento x =apply(x, L) con L ⊆ {R1, ..., Rm}L 6= ∅

E0(i, xi) =il valore assunto dalla variabile x al termine dell'iterazione i-esima è xi

I0(x0) =il valore a cui viene inizializzata x è x0

Probabilità di un generico assegnamento

Osserviamo quindi che la seguente probabilità:

pL= P (X0(n + 1, L)|I0(x0)E0(1, x1)E0(2, x2)....E0(n, xn))

dati i valori x0, x1, ..., xn è univocamente determinata e rappresenta la probabilità

Calcoliamo questa probabilità per ogni valore di L. Se t è il valore del tempo all'iterazione n + 1 sia pj la probabilità che la reazione j inizi in t − σj. Come nel

caso precedente si ha:

pj= aj(x(t−σj))·δt = aj(x_n+1−σj δt )·δt se t−σj ≥ 0 cioè n+1− σj δt ≥ 0 (2) pj= 0 se t − σj< 0 cioè n + 1 − σj δt < 0

si noti che le reazioni hanno tutte ritardo maggiore di zero e multiplo intero di δt quindi n + 1 −σj

δt è un intero e il suo valore massimo è n. La probabilità pL che in

ttermini l'insime L di reazioni è:

L = {R1} pL= p1(1 − p2)(1 − p3)....(1 − pn)

L = {R2} pL= p2(1 − p1)(1 − p3)....(1 − pn)

L = {R1, R2} pL = p1p2(1 − p3)...(1 − pn)

L = {R1, R2, ...., Rm} pL= p1p2p3....pm

La probabilità p∅ che in t non termini alcuna reazione:

L = ∅ p∅= (1 − p1)(1 − p2)....(1 − pm)

si può provare facilmente che la somma di queste probabilità è uno. Come si vede in generale vale la formula:

pL=   Y Rj∈L pj  ·   Y Rj∈L/ (1 − pj)   (3)

Denizione (insiemi degli stati e delle etichette)

Stato iniziale: lo stato iniziale s0 viene rappresentato con una coppia < x0, t0>

Altri stati: un generico stato diverso da s0 viene rappresentato da una quadrupla

< i, x, t, L >dove: iè l'indice dell'iterazione

tè il valore della variabile t al termine dell'iterazione i-esima

Lè un sottoinsieme di {R1, R2, ...., Rm}. Se è l'insieme vuoto allora all'iterazione

i-esima non è stata eseguita la apply. Se è diverso dall'insieme vuoto allora all'iter-azione i-esima è stata eseguita x =apply(x, L).

Etichette: numeri reali in [0, 1]

Denizione (regole di transizione) Prima regola: t0≤ T pL= P (X0(1, L)|I0(x0)) x1=apply(x0, L) L ⊆ {R1, ...., Rm} L 6= ∅ < x0, t0> pL −→< 1, x1, t0+ δt, L > Seconda regola: t0≤ T pL= P (X0(1, L)|I0(x0)) p = 1 − X L pL L ⊆ {R1, ...., Rm} L 6= ∅ < x0, t0> p −→< 1, x0, t0+ δt, ∅ > Terza regola: tn≤ T < x0, t0> p(1) −→< 1, x1, t1, L1>, ...., < n−1, xn−1, tn−1, Ln−1> p(n) −→< n, xn, tn, Ln>

pL= P (X0(n + 1, L)|I0(x0)E0(1, x1)E0(2, x2)....E0(n, xn)) xn+1=apply(xn, L) L ⊆ {R1, ...., Rm} L 6= ∅

< n, xn, tn, Ln> pL

−→< n + 1, xn+1, tn+ δt, L >