A Cellular Automata Model Of Ebola Virus Dynamics
Physica A 438 (2015) 424–435Contents lists available at ScienceDirectPhysica Ajournal homepage: www.elsevier.com/locate/physaA cellular automata model of Ebola virus dynamicsEmily Burkhead a,1 , Jane Hawkins b, aDepartment of Mathematics and Computer Science, Meredith College, United StatesbDepartment of Mathematics, University of North Carolina at Chapel Hill, CB #3250, Chapel Hill,NC 27599-3250, United Stateshighlights We construct a stochastic cellular automaton model for the Ebola virus.Basic dynamical rules governing viral spread are adapted to the Ebola setting.Rigorous results are given about the dynamics.Model output simulates the timeline of the infection and captures fatality rates.articleinfoArticle history:Received 2 June 2015Available online 15 July 2015Keywords:EbolaCellular automataVirus spreadabstractWe construct a stochastic cellular automaton (SCA) model for the spread of the Ebolavirus (EBOV). We make substantial modifications to an existing SCA model used for HIV,introduced by others and studied by the authors. We give a rigorous analysis of thesimilarities between models due to the spread of virus and the typical immune response toit, and the differences which reflect the drastically different timing of the course of EBOV.We demonstrate output from the model and compare it with clinical data. 2015 Elsevier B.V. All rights reserved.1. IntroductionEbola virus (EBOV) is a filovirus that causes severe illness in most humans who are exposed to it. A filovirus is a negative,single-stranded RNA virus whose genome is configured linearly, which differs from a retrovirus such as HIV (humanimmunodeficiency virus) in its method of replication [1,2]. On the other hand, similarities between these two types ofviruses, especially in terms of their negative effect on the immune system, have been studied for some time [3]. In Octoberof 2014 the World Health Organization (WHO) Ebola Response Team published a report estimating the fatality rate of EbolaVirus Disease (EVD) to be around 70.8% [4], but hospitalized patients during the recent outbreak in West Africa had a slightlylower fatality rate. Due to the difficulty in gathering accurate data, differences among patient care, and individual responsesto treatment, there is a wide range of fatality rates reported, from 25% to 90% [5].Because of the extreme virulence of EBOV, autopsies and handling of fluids of infected patients are limited and avoidedwhen possible [5], making mathematical and computer models of the disease a particularly valuable tool. In Ref. [6], acomputer model first introduced in 2001 by Zorzenon dos Santos and others [7] for HIV, was amended and studied rigorouslyto show precisely which viral dynamics were being modeled, how the set of infected cells spreads, and how immuneresponse and drug therapy affects the dynamics. The authors of Ref. [6] extracted some results that apply independently Corresponding author.E-mail addresses: burkhead@unc.edu (E. Burkhead), jmh@math.unc.edu (J. Hawkins).1 Current address: Department of Mathematics, University of North Carolina at Chapel Hill, CB #3250, Chapel Hill, NC 27599-3250, United 490378-4371/ 2015 Elsevier B.V. All rights reserved.
E. Burkhead, J. Hawkins / Physica A 438 (2015) 424–435425of the virus in question and showed how varying parameters changed the model. The spread of HIV, as well as the effectof administering drugs, has been modeled by SCAs (see for example, Refs. [6,8–10] and references therein). In Refs. [11,10]the later chronic stages of viral infection were isolated from the model and studied further; these studies involved Markovprocesses reflecting randomness in the development and control of a chronic viral condition. The EBOV time scale is muchshorter and there seems to be no chronic residual disease that has been observed in survivors of the acute illness up to now.Therefore the early viral dynamics control the progression and outcome. In this paper we adapt the early stages of the viraldynamics model in Ref. [6] to EBOV.A cellular automaton (CA) model is an agent-based model, a computer simulation of the process of the viral spread in anorgan based on simple rules. For example, a rule that all viral models have in common is that if a cell is contiguous to anactively infected cell, it becomes infected in the next time step. An SCA uses a small number of simple rules chosen randomlyusing data-based probabilities, to emulate differences in immune responses to viral spread. By running an SCA simulation,we achieve a variety of outcomes from a single model.In this paper, we modify the original (HIV) SCA model to use parameters and cellular automata rules specific to the spreadof EBOV within an individual organ. While much is still unknown about EBOV, we can use features of existing models for thegeneral properties of viral spread and the body’s typical immune response to it. We change some of the salient features ofthe HIV model as needed for this setting. As of this writing, it is believed that viral mutation occurs much less with EBOV thanwith HIV though the possibility that EBOV mutations might affect future diagnosis and treatment is being studied [12]. Incontrast, it has been known for some time that HIV shows extensive genetic variation even within individual hosts, makingHIV one of the fastest evolving of all organisms [13]. Therefore, one of the main modifications we make is to remove the ruleleading to viral reservoirs due to mutating viruses, a characteristic property of HIV. We eliminate that as a mathematicallypossible rule and replace it with a rule that reflects a delayed or slower immune response to the virus. The rest of the rules inthe SCA stay the same and this small change immediately speeds up the course of the viral infection to a fairly rapid recoveryor death.The paper is organized as follows. In Section 2 we give the basic definitions of CAs and SCAs, introduce the rules used inour model of EBOV dynamics, and present theoretical results. The output obtained by various computer simulations utilizingdifferent parameters is analyzed in Section 3, and we discuss some conclusions in Section 4.2. Theory of cellular automata models2.1. Cellular automataLet A denote the finite state space or alphabet, A {0, 1, 2, 3}. We use state 0 to represent a healthy cell site in an organ,and states 1 and 2 to represent infectious cells able to infect neighboring cells. State 3 represents a depleted (dead) cell site.Then, we define the integer lattice Z2 {Eı (i, j), i, j 2 Z}, viewed as a subset in the plane (or on a surface, by identifyingedges of a polygon). The length of a vector in Z2 is taken as kEık max{ i , j }. The space on which a cellular automaton acts2is X AZ , which we think of as the integer lattice Z2 in the plane with exactly one value from the state space A placedat each coordinate (i, j) in the lattice. The space X is mathematically equivalent to the set of functions from Z2 to A. So, foreach x 2 X and Eı (i, j) 2 Z2 we write x(i,j) to denote the coordinate of x at Eı, with x(i,j) 2 {0, 1, 2, 3}. Similarly for any finiteset E Z2 , we define xE to be the block of coordinates {xEı : Eı 2 E }; i.e., xE 2 A E where E is the cardinality of E.We make X into a compact space by using the classical metric on X , which is defined so that two points are close if theircoordinates agree on a large central region. First, we define a neighborhood of radius k 2 N [ {0} about (0, 0) 2 Z2 , byNk {Eı (i, j) : i , j k} {Eı : kEık k}. Then, the metric dX on X is defined as follows: for any pair of points x, v 2 X ,dX (x, v) 21k where k min m : xNm 6 vNm . We call a pattern any fixed (2k 1)2 square block of states from A (or afinite union of (2k 1)2 square blocks), k 2 N. We form a basis for the metric topology from the following collection of sets.For any pattern u, define Bu {x 2 X : xNk u} to be the u-cylinder of radius k (centered at (0, 0)). Bu is precisely the setof points from X whose central block of coordinates extending out k units in each direction from (0, 0) coincides with thefixed pattern u.The space X provides a model for an organ that is susceptible to the virus such as liver, spleen, lungs, or skin [5,14]. Eachpoint x 2 X represents a configuration of the healthy, infected, and depleted cells of the organ at any given time, and eachcoordinate x(i,j) shows the state of the organ at that location where a coordinate is either a cell or a site of cells, dependingon the organ. In order to dynamically move around within an organ and sample the state at any location, we define the shiftmaps on X as follows:8Eı (i, j) 2 Z2 ,[ Eı (x)](k,l) x(i k,j l) .With respect to the metric dX , each shift Eı is a continuous transformation on X . With all this structure in place, we are nowable to define a CA.Definition 2.1. A 2-dimensional cellular automaton (CA) is a continuous transformation F on X such that for every Eı 2 Z2 ,FEı Eı F .It is well-known that each CA is characterized by a local rule (of radius rthe metric topology on X . In the next theorem this is made precise.0), based on the definition of continuity in
E. Burkhead, J. Hawkins / Physica A 438 (2015) 424–435426Theorem 2.2 ([15]). The map F : X ! X is a CA if and only if there exists an integer rthat for every x 2 X ,20 and a map f : A(2r 1) ! A suchF (x)Eı f (xNr Eı ).(2.1)The map f that appears in (2.1) is called the local rule for the CA F as f describes the CA completely.It is useful to regard a CA as a map or rule that updates each coordinate in X at each time step by looking only at finitelymany nearby coordinates. If F is a CA, we iterate F using the notation F k (x) F · · · F (x) to denote composition withitself k times.An analogous space X could be defined to be the set of functions from Zd to A for any integer dimension d1. We find,however, that using two dimensions captures most of the EBOV dynamics that are understood so far. The SCA model of thespread of the virus we define below does not depend on the dimension of the organ, but rather on the relative positionsof cells to each other. Moreover, the actual viral spread could take place in one-dimensional channels (narrow capillaries),along two-dimensional sheets (such as the skin), and in 3-dimensional organs (for example, the liver) [5]. All of the mathanalysis that follows can be done for arbitrary dimension d as well. However using d 2 makes the concepts and notationeasier to explain in this paper.2.2. CAs model the immune response to EbolaWe use three different 2-dimensional CAs to model the immune response to viruses such as Ebola, combining them intoa stochastic cellular automaton (SCA) in Section 2.3. Here, we introduce them independently.In a healthy individual with a functioning immune system, infected cells die quickly and are replenished by healthy ones,while at the same time the infected cells are also infectious, able to infect nearby healthy cells. The CA Q models this quickresponse: all infectious cells are depleted in a single time step, as we see in local rule q which has radius 1. On the state spaceA {0, 1, 2, 3}, define the local rule q : A3 3 ! A as follows: q q q 0 a 3 d ! 1 if at least one * is 1 or 2 0 otherwise, ! 3 for 1 a 2, ! 0. The dynamics of Q are illustrated in Fig. 1. White represents 0, healthy cells, and black represents 3, depleted (dead)cells; pink represents state 1, the initial infection, as shown in the first frame. State 2 does not appear under iteration of Qwhen we begin with an initial point consisting of 0s and 1s. Above each frame is the time step, where one time incrementcorresponds to one day. As shown, initial infection spreads and then clears out, with a return to the all healthy configurationin a very short time frame. The timing to clear out the infection depends on the number and proximity of initial 1s; fewerand farther spaced out 1s will require a longer time to return to the all 0 configuration.We use two small variations on this CA to model what happens if the immune system is compromised or simply delayedin its response. We call these CAs L for longer response and D for depleted response; we define them by their radius r 1local rules, and d, respectively. For the longer response, an additional timestep will be needed for the immune systemto wipe out an initially infected site (1 passes to 2 and then to 3). The depleted response is so named because a dead sitewill stay dead (3 stays 3). All other portions of the rules are the same as in the quick response. So, we define the local rules , d : A3 3 ! A by: a 0 ! q ! q a 0 ! for any a 6 3, while d ! ; for any a 6 0, a 3! 3; ! a 1 (mod 3). The dynamics of L are virtually identical to those of Q and are shown in Fig. 2. We see the appearance of state 2,represented by teal; initial infection once again spreads and then clears out. The dynamics of D are shown in Fig. 3. Insteadof recovery, we see that the infection eventually depletes all cells.These three rules are variations on those used in the study HIV [6]. Our L and D parallel two of the three rules in the HIVmodel, however we use fewer total states (four here as compared to seven for the HIV model) since EBOV progresses muchmore quickly than does HIV. The third rule used in the HIV model took into account the very fast mutation rate of the virus.
E. Burkhead, J. Hawkins / Physica A 438 (2015) 424–435Fig. 1. Iteration of Q : infection spreads, then clears out.Fig. 2. Iteration of L: infection spreads, then clears out.Fig. 3. Iteration of D: infection spreads, resulting in cell death.427
428E. Burkhead, J. Hawkins / Physica A 438 (2015) 424–435Despite the likelihood that EBOV might mutate due to transcription errors based on its RNA replication [12], it seems thatthe genetic sequence of EBOV is relatively stable [2]. Our motivation for using both Q and L comes from observations thatantibody responses are very different for patients who survive the disease when compared to those who have lethal cases;‘‘deceased patients show a lower or even absent antibody response [1]’’.Formal statements regarding the dynamics of each of Q , L, and D are treated next. Many of the results correspond to onesstated and proven for the CAs considered in the HIV model in Ref. [6]. Rather than provide a complete proof of our resultshere, then, we simply indicate the differences needed to modify the proofs from Ref. [6].Proposition 2.3. Let 0 2 X be such that 0(i1 ,i2 ) 0 for all (i1 , i2 ) 2 Z2 . Then 0 is a fixed point under each of the CAs Q , L, and D.Physically, this would correspond to a completely healthy organ: with no infection in any site, the organ simply stayscompletely healthy for all time. The proof is obvious: since none of the 0 states are adjacent to any 1s or 2s, they will allupdate to 0 under iteration of each of the three CAs.There are points in X arbitrarily close to this fixed point which have drastically different trajectories; 0 is not what iscalled a point of equicontinuity. A point x 2 X is a point of equicontinuity for a transformation F if for any " 0, there exists 0 so that any y 2 X having dX (x, y) has dX (F n x, F n y) " for all n 0.Proposition 2.4. 0 is not a point of equicontinuity for Q , L, or D.Proof. The proof of Proposition 4.1 in Ref. [6] can be applied here due to the similar mechanism by which 0 7! 1 in the localrules of the CAs. In our model, we are primarily considering initial points which consist strictly of states 0 and 1. All of these initial pointsconverge under iteration of both Q and L to the fixed point 0, which is to say that these two CAs model a successful immuneresponse to an ordinary virus. Under iteration of D, our initial points all converge to 3 and they are points of equicontinuity.Proposition 2.5. Let x 2 X have x(i1 ,i2 ) 2 {0, 1} for all (i1 , i2 ) 2 Z2 . Then {Q n x} ! 0, {Ln x} ! 0, and {Dn x} ! 3 as n ! 1.Proposition 2.6. Let x 2 X have x(i1 ,i2 ) 2 {0, 1} for all (i1 , i2 ) 2 Z2 but x 6 0. Then, x is a point of equicontinuity for D.Proof. The proof of each of these statements is obtained in a virtually identical manner to that of the CAs considered inRefs. [6, Propositions 4.3, 4.4, and 4.5]. The only difference is that the number of iterates needed for convergence is slightlyless here since we have fewer states in the alphabet A. Although the orbits of our initial points are certain under all three CAs, there are other points arbitrarily close to a giveninitial point of 0s and 1s which have drastically different orbits under both Q and L, giving rise to some unpredictability. It isunfortunate, then, that these are the two CAs which bring our initial points to a good outcome, with all healthy sites; D takesour initial points to a very bad outcome, where all sites are dead. Once again, we can turn to the proof of a similar resultthat appears in Ref. [6, Proposition 4.7], which relies on the presence of a fully blocking pattern. A fully blocking pattern is afinite arrangement of states from the alphabet whose appearance in a point determines the states at those coordinates forall subsequent iterations of a CA, regardless of what states occur nearby.Proposition 2.7. Let x 2 X have x(i1 ,i2 ) 2 {0, 1} for all (i1 , i2 ) 2 Z2 . Then x is not a point of equicontinuity for Q or for L.Proof. Since the fully blocking pattern given in Ref. [6], consisting of concentric rings of 0s, 2s, and 0s, also happens to be afully blocking pattern for our L, as shown in Fig. 4, the proof of Ref. [6] extends with only minor modifications to L.Although the concentric rings of 0s and 2s turn out not to be fully blocking for Q , we are still able to utilize theaforementioned proof for Q by utilizing a different fully blocking pattern, the one in Fig. 5, in much the same way. By a result of Ref. [16], we can also use these fully blocking patterns to create many initial points in X which do havepredictable orbits under each of the three CAs. We define a CA to be almost equicontinuous if its set of equicontinuity pointscontains a countable intersection of dense open sets.Proposition 2.8. The CAs Q , L, and D are each almost equicontinuous.3Proof. The pattern of Fig. 5 is fully blocking for Q . The pattern of Fig. 4 is fully blocking for L. The pattern 33333333is fixedunder D and therefore fully blocking for D. Thus, we can apply Theorem 6.3 of Ref. [16] to each of Q , L, and D to concludethat these three CAs are each almost equicontinuous. 2.3. Stochastic cellular automataNow, we combine the three CAs above to form a stochastic cellular automaton (SCA). The idea is that in each iteration, wewill independently choose which of these CAs to apply at each site in the lattice. The choices need not be equally weighted,
E. Burkhead, J. Hawkins / Physica A 438 (2015) 424–435429Fig. 4. A fully blocking pattern for L; the pattern reappears after four iterations.Fig. 5. A fully blocking pattern for Q : the pattern reappears after three iterations.but the probability of making each choice is consistent across all coordinates. Since we have three CAs, we let C {1, 2, 3}be an index set. The local rule for the SCA will then need to take as arguments both a single element of C as well as a 3 3block of symbols from A. To iterate the SCA, we will need to select one rule for each time step. Thus, we let C N[{0}model the random selection at a single site. The shift space is equipped with the standard metric d (!, ) 21k , wherek min{m 2 N [ {0} : !m 6 m } as well as the standard shift map s given by[s(!)]n !n 1 .(2.2)g (!, u) f!0 (u) A s(!), f!0 (u) ,(2.3)For convenience of notation, we will rename F1 Q , F2 L, and F3 D, with corresponding local rules f1 q, f2 ,and f3 d. Constructing an SCA begins with a local rule. On the space A3 3 , defi
Ebola Cellular automata Virus spread abstract We construct a stochastic cellular automaton (SCA) model for the spread of the Ebola virus (EBOV). We make substantial modifications to an existing SCA model used for HIV, introduced by others and studied b
ture of new generations of computers, is found in Cellular automata in the fourth class identified many natural systems. by Wolfram are conjectured to be capable of" uni-2. Outline This special issue is a collection of papers on various aspects of cellular automata and their ap plications. Cellular automata have arisen in several
Advanced Automata Theory is a lecture which will rst review the basics of formal languages and automata theory and then give insight into speci c topics from wider area of automata theory. In computer science, automata are an important tool for many theoretical results and various types of automata
Automata and Formal Languages II Tree Automata Peter Lammich SS 2015 1/161. Overview by Lecture Apr 14: Slide 3 Apr 21: Slide 2 Apr 28: Slide 4 May 5: Slide 50 . Finite tree automata: Basic theory (TATA Ch. 1) Pumping Lemma, Clo
Deterministic Finite Automata plays a vital role in lexical analysis phase of compiler design, Control Flow graph in software testing, Machine learning [16], etc. Finite state machine or finite automata is classified into two. These are Deterministic Finite Automata (DFA) and non-deterministic Finite Automata(NFA).
Complexity, the Central Concepts of Automata Theory - Alphabets, Strings, Languages, Problems. Deterministic Finite Automata, Nondeterministic Finite Automata, an application: Text Search, Finite Automata with Epsilon-Transitions, Finite automata with output - Mealy and Moore machines, Equivalence of Mealy and Moore machines.
properties of bipolar general fuzzy switchboard automata are discussed in term of switching and commutative by proving the theorems that are related into these concepts. . 2.3 Automata theory 18 2.4 Optimisation problems 23 2.4.1 Critical path problem 23 . Deterministic finite automata FSM - Finite state machine FSA - Finite state automata .
Abstract—Quantum-dot cellular automata (QCA) is an emerging nanotechnology, with the potential for faster speed, smaller size, and lower power consumption than transistor-based technology. Quantum-dot cellular automata has a simple cell as the basic element. The cell is used as a building block to construct gates and wires.
BAB 2 LANDASAN TEORI 2.1 Program Pensiun 2.1.1 Definisi Program Pensiun Berdasarkan Undang-Undang Republik Indonesia Nomor 11 tahun 1992 tentang Dana Pensiun didefinisikan bahwa program pensiun adalah setiap program yang mengupayakan manfaat pensiun bagi peserta. Manfaat pensiun itu berupa pembayaran berkala yang diberikan setelah peserta mencapai usia pensiun. Definisi tentang Dana Pensiun .
