Generalised Gillespie Algorithm Generalised Gillespie Algorithms for Simulations in a Rule-Based

2025-05-06 0 0 4.6MB 29 页 10玖币

侵权投诉

Generalised Gillespie Algorithm

Generalised Gillespie Algorithms for

Simulations in a Rule-Based

Epidemiological Model Framework

David Alonso1†, Steﬀen Bauer2†, Markus Kirkilionis3*†,

Lisa Maria Kreusser4†and Luca Sbano5†

1Theoretical and Computational Ecology, Center for Advanced

Studies of Blanes (CEAB-CSIC), Spanish Council for Scientiﬁc

Research, Acces Cala St. Francesc 14, Blanes, E-17300, Spain.

2Mathematisches Institut, Mathematikon,

Ruprecht-Karls-Universität Heidelberg, Im Neuenheimer Feld

205, 69120 Heidelberg, Germany.

3*Warwick Mathematics Institute, University of Warwick,

Zeeman Building, Coventry, CV4 7AL, United Kingdom.

4Department of Mathematical Sciences, University of Bath, Bath,

BA2 7AY, United Kingdom.

5Liceo “Vittoria Colonna”, Via dell’Arco del Monte 99, Rome,

00186, Italy.

*Corresponding author(s). E-mail(s): mak@maths.warwick.ac.uk;

Contributing authors: dalonso@ceab.csic.es;

steﬀen.bauer@stud.uni-heidelberg.de;lmk54@bath.ac.uk;

luca.sbano@posta.istrizione.it;

†These authors contributed equally to this work.

Abstract

Rule-based models have been successfully used to represent diﬀerent

aspects of the COVID-19 pandemic, including age, testing, hospitali-

sation, lockdowns, immunity, infectivity, behaviour, mobility and vac-

cination of individuals. These rule-based approaches are motivated by

chemical reaction rules which are traditionally solved numerically with

the standard Gillespie algorithm proposed in the context of molecular

arXiv:2210.09511v2 [q-bio.PE] 24 Oct 2022

Generalised Gillespie Algorithms

2Generalised Gillespie Algorithms

dynamics. When applying reaction system type of approaches to epi-

demiology, generalisations of the Gillespie algorithm are required due

to the time-dependency of the problems. In this article, we present dif-

ferent generalisations of the standard Gillespie algorithm which address

discrete subtypes (e.g., incorporating the age structure of the popula-

tion), time-discrete updates (e.g., incorporating daily imposed change

of rates for lockdowns) and deterministic delays (e.g., given waiting

time until a speciﬁc change in types such as release from isolation

occurs). These algorithms are complemented by relevant examples

in the context of the COVID-19 pandemic and numerical results.

Keywords: Gillespie algorithm, rule-based models, COVID-19.

1 Introduction

This paper discusses generalisations of the Gillespie algorithm, an algorithm

which was originally designed for chemical reaction systems. The generalisa-

tions are triggered by the wish to apply a reaction system type of approach

to epidemiology, a choice that is often done, even unconsciously, due to the

simple analogy of the infection process with a chemical reaction. However,

the important reason why generalisations of the Gillespie algorithm are neces-

sary is already deeply rooted in the history of mathematical modelling, where

time-dependent problems are, in a majority of cases, modelled by ordinary dif-

ferential equations (ODE), and in that class of models, by so-called mass-action

systems. Roughly speaking, a mass-action system can be characterised by the

rate of change of concentrations of an entity being proportional to the con-

centration of entities needed to assemble or change it during collision events.

Using mass-action systems in modelling is very helpful, as the whole arsenal

of methods developed for dynamical systems can be applied. In addition, the

right-hand side of a mass-action based ODE is polynomial, allowing the addi-

tional use of speciﬁc mathematical theories, like algebraic geometry. However,

there are a few assumptions needed for mass-action systems to work:

(i) The system is deterministic, which is usually the case when the collid-

ing entities are present in very large numbers. In addition, in the dynamical

systems sense, the system is autonomous.

(ii) The collision events between entities are such that every entity can col-

lide with any other entity in the system, and has moreover exactly the same

probability to collide with another entity in the system.

(iii) The system is conﬁned to a well-deﬁned (thermodynamically) closed

space, in reaction systems called the reaction chamber. This also constitutes a

well-deﬁned system boundary, where ’inside’ the system and ’outside’ the sys-

tem are well-deﬁned concepts. Often such systems are also labeled as ’closed’

and ’open’ if either no disturbances from outside the system boundaries are

considered in a closed system, or a allowed in an open system.

Generalised Gillespie Algorithm

Generalised Gillespie Algorithms 3

(iv) By the collision assumption, system changes are driven by a sequence

of events ordered by time. Moreover, system changes are instantaneous, and

only depend on the current state of the system when the event happens. This

induces the so-called Markov property.

The original Gillespie algorithm is constructed to generalise assumption (i),

deterministic dynamics. The idea is to relax the idea of very large number of

entities in the system, and therefore to allow for so-called small-number eﬀects.

This transforms the ODE mass-action system into a stochastic process. We

will follow this argument and assume assumption (i)is not necessarily valid,

as we believe, especially for epidemiological processes, we need to study the

consequences of stochastic eﬀects. However, in this article, we keep assumptions

(ii)and (iii), as these assumptions are also fundamental in order to apply

any Gillespie-type algorithm. However, we will need to relax assumption (iv),

because epidemiology (but also other applications) provides clearly model cases

where an event triggers a system change only with a delay. Vaccination is such

an example. The vaccination event is instantaneous, however the establishment

if immunity, for example, will only happen after some time has passed. The

algorithms presented in this paper should be able to enable rule-based models

to be used in situations where simple reaction mechanisms fail. But what are

rule-based systems?

1.1 Rule-based systems

Rule-based systems are a generalisation of reaction systems, mostly in order

to carry over the theory to other ﬁelds of applications. Following the notation

in [1] for the rule-based modelling framework, we denote by T={T1, . . . , Ts},

s∈N, the set of all possible types or individual characteristics, sdiﬀerent types

in total. Let R={R1, . . . , Rr},r∈N, be the ﬁnite set of rules constituting

the epidemiological system. Each rule Rjtakes the form

i=1

αij Ti

−→

i=1

βij Ti,(1)

for j= 1, . . . , r, where kjdenotes the rate constant of reaction Rj. The coeﬃ-

cients αij ∈N0are the stoichiometric coeﬃcients of types Ti,1≤i≤s, of the

source side, and βij ∈N0are the stoichiometric coeﬃcients of types Tiof the

target side of transition or reaction Rj. Note that we use the terms reaction

and rule of interaction interchangeably for Rj.

The rule-based formulation (1) of reactions can be interpreted stochasti-

cally or deterministically. While the deterministic formulation is based on a

system of ODEs, several stochastic formulations exist [1], including continuous-

time Markov chains, Kolmogorov Diﬀerential Equations and Master Equations,

as well as on Stochastic Diﬀerential Equations. Here we focus on stochastic

dynamics based on continuous-time Markov chains in this paper. We introduce

the population size Nand consider the size ni(t)of type Tiat time t≥0for

Generalised Gillespie Algorithms

4Generalised Gillespie Algorithms

i= 1, . . . , s as discrete random variables with values in {0, . . . , N}. For ease

of notation, we also write n= (n1, . . . , ns), which accurately characterizes the

system conﬁguration (or state of the system) at any given time. Further for-

mulations include Kolmogorov Diﬀerential Equations and Master Equations,

as well as on Stochastic Diﬀerential Equations, see [1].

The time-dependency of nmotivates to regard nas a stochastic process

and under some additional assumptions, nis a continuous-time Markov chain.

To simulate the sample paths of n, one can apply the Gillespie algorithm.

The simulation of many trajectories of the system allows the computation of

the statistics of the evolution. While it is known that polynomial regression

asymptotically converges to the numerical solution as the number of considered

trajectories increases, there exist realisations so that the stochastic trajecto-

ries and the deterministic dynamics diﬀer signiﬁcantly. We believe we need

this multi-sampling approach in order to make better predictions on epidemic

scenarios when compared with deterministic models.

1.2 The pandemic as a modelling challenge

The Coronavirus disease 2019 (COVID-19) pandemic has put epidemic

modelling in the worldwide spotlight. However, public policy making and fore-

casting the spread of COVID-19 remains a challenging task [2,3]. This is

especially true because the huge impact of the pandemic had many previously

unknown or unconsidered consequences that came to the spotlight and which

need to be reﬂected in models in order to make them predictive. Moreover the

evolution and unfolding of the pandemic triggered new policies and interven-

tions which need unconventional mathematical modelling techniques, including

novel simulation techniques. This latter need essentially triggered the writing

of this paper.

In terms of mathematical models supporting policy decisions a lot of trade-

oﬀs have been registered during the Covid-19 pandemic. The most obvious one

is the link of a pandemic to economy, where of course the pandemic policy

measures have created huge impacts on economic performance, which in turn

had tremendous impact on the spread of the disease. An example of an attempt

to model such feedback for the Philippines is given in [4], but this model is

based on a pure diﬀerential equation approach, as most models in this area. Of

course the pandemic has also positive economic aspects, for example in terms

of air pollution [5]. If we like to give good estimates of such models in terms

of stochastic modelling, algorithm like the one developed in this paper will be

needed.

There was a multitude of lockdown measures implemented during the

Covid-19 pandemic, and it is still an open question which one worked best, and

which one could be further improved in their eﬀectiveness. The most severe

intervention was surely a country-wide lockdown with a simultaneous closing

of national borders. These measures prove eﬀective [6], but costly in economic

terms [7]. Then there are local lockdowns, for example automatically triggered

by infection numbers, as based on testing [8]. Isolation measures were also

Generalised Gillespie Algorithm

Generalised Gillespie Algorithms 5

implemented on an individual level, after a person had been detected to be

infected. Here the question is how eﬀective the search for infected individuals

must be (contact tracing [9], how long such an isolation should last, and how

much impact isolations have on economy and society [10]? More mild mea-

sures are to impose protective measures, like face-mask wearing, or to avoid

close contact [11]. To study such eﬀects, and eventually to optimise the eﬀec-

tiveness of measures one needs to use the stochastic algorithms developed in

this paper, which can be applied to such non-autonomous stochastic systems

describing interventions.

Many such mathematical modelling problems involve some form of delay,

constituting also a basic form of memory. This can perhaps be best explained

in terms of vaccination strategies. Many vaccination strategies involve two of

more doses of vaccine injections after some ﬁxed time delay, which improves

the eﬀect of the vaccine drastically [12], sometimes better than immunity by

infection [13]. Immunity itself also is never instantaneously achieved after an

infection or vaccination event, but build up and declines over a longer period

of time. If such eﬀects or policies need to be incorporated into a stochastic

collision-based stochastic model, then again the algorithms in this paper need

to be used.

1.3 Gillespie algorithm

In the context of molecular dynamics, Gillespie showed in a series of seminal

papers [14–16] that, if the reaction rates are proportional to the product of

the number of particles, i.e. if they follow the mass action kinetics, then the

evolution processes are Poisson processes and can be reconstructed through an

algorithm. Note that mass action is equivalent to random close contacts. The

Gillespie algorithm is characterised by observing that Poisson processes have

inter-event times (waiting time) which are exponentially distributed and satisfy

the Markov property. This is equivalent to increments being independent and

the time evolution having no memory. The spread of an infection requires to

analyse eﬀects and interactions that occur at diﬀerent scales in time, space

and size, which is a challenging problem for modellers. Such eﬀects can be

more accurately modelled through memory eﬀects, and therefore requiring

the introduction of non-Markov process with non-exponentially distributed

waiting-times. The necessity of a generalisation of the Gillespie algorithm was

considered already by Gillespie himself in [17].

The main directions to generalise the Gillespie algorithm is to ﬁnd ways to

eﬃciently simulate systems with a large number of degrees of freedom [18,19],

and simulate stochastic processes with given waiting time distributions not

necessarily exponentially distributed. These problems have recently attracted

lots of interest, including generalisations of the Gillespie algorithm for non-

Markov processes [20–22], based on considering waiting times which are not

necessarily exponentially distributed. A recent general review can be found in

[23].

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

GeneralisedGillespieAlgorithmGeneralisedGillespieAlgorithmsforSimulationsinaRule-BasedEpidemiologicalModelFrameworkDavidAlonso1y,SteenBauer2y,MarkusKirkilionis3*y,LisaMariaKreusser4yandLucaSbano5y1TheoreticalandComputationalEcology,CenterforAdvancedStudiesofBlanes(CEAB-CSIC),SpanishCouncilforScient...

展开>> 收起<<

Generalised Gillespie Algorithm Generalised Gillespie Algorithms for Simulations in a Rule-Based.pdf

共29页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Generalised Gillespie Algorithm Generalised Gillespie Algorithms for Simulations in a Rule-Based

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: