PCA

June 10-11-12, 2013

Workshop on

Probabilistic Cellular Automata:

Theory, Applications and Future Perspectives

The workshop aims at exploring Probabilistic Cellular Automata (PCA) from the point of view of Statistical Mechanics, Probability Theory, Computational Biology, Computer Science and Discrete Dynamical Systems.

PCA revealed to be a fruitful tool in those fields nevertheless many challenges remain open. There is a recent growing interest from these different fields and agreement on the emergency of a turning point: interactions has to be strengthened. This workshop will give an opportunity for the different communities to interact. We welcome contributed talks and posters. Doctoral and post-doctoral researchers are invited to participate. Interested advanced Master students will benefit from the creative interdisciplinary atmosphere we want to promote.

The aim of the workshop is to explore the Probabilistic Cellular Automata field from different point of view.

Cellular Automata (CA) are discrete dynamical systems consisting of simple elementary elements interacting according to some local rules. Simple update rules may produce extremely complex behaviour. They have been used to model a wide range of physical phenomena including traffic flow, disease epidemics, invasion of populations, and dynamics of stock markets.

PCA build a bridge among different scientific disciplines such as Probability Theory, Statistical Mechanics, Theoretical Computer Science, Complex Systems and Computational Life Sciences, and more. Indeed, in recent years there have been active research efforts on the following briefly outlined three directions:

● Computer Science and Discrete Dynamical Systems e.g. robustness of PCA when going from synchronous to asynchronous updating scheme, deterministic CA with random initial condition, density classification, synchronous / asynchronous updating.

● Probability and Statistical Mechanics, e.g. PCA as discrete-time interacting particle system, non-equilibrium statistical mechanics, metastability, cut-off phenomena and abrupt convergence, phase transitions, Gibbs/Non--Gibbs transitions, PCA and stochastic algorithms

● Applications mainly in computational (cell) biology e.g. Cellular Potts Model and stability of emerging patterns, time to stationarity in simulation algorithms, transient regimes

The wide interest of the recent results beside the among related scientific communities confirm the urgency to break the walls and put in touch scientists with different backgrounds but all sharing a common interest for PCA. We expect that the interaction between these different fields and approaches will produce cross fertilization both at theoretical and applicative levels, exchange of point of views and challenges, joint collaborations.

ORGANISERS

LIST OF SPEAKERS

Each day, an opening talk will give an introductory lecture (40 minutes) intended to present to a broad audience the chosen days perspectives. There will be long talk of 40 minutes and short ones of 20 minutes. Relatively long breaks will give to the participants the opportunity for discussions.

Poster sessions create the opportunity to explore each others work. These sessions prove to be a great success

WEDNESDAY JUNE 12

n.b. All abstracts are included in the BOOKLET, which has been printed for all participants.

ABSTRACTS

We introduce a simple formalism for dealing with deterministic, non- deterministic and stochastic cellular automata in an unified and composable manner. This formalism allows for local probabilistic correlations, a feature which is not present in usual definitions. We show that this feature allows for strictly more behaviors (for instance, number conserving stochastic cellular automata require these local probabilistic correlations). We also show that several problems which are deceptively simple in the usual definitions, become undecidable when we allow for local probabilistic correlations, even in dimension one. Armed with this formalism, we extend the notion of intrinsic simulation between deterministic cellular automata, to the non-deterministic and stochas- tic settings. Although the intrinsic simulation relation is shown to become undecidable in dimension two and higher, we provide explicit tools to prove or disprove the existence of such a simulation between any two given stochastic cellular automata. Those tools rely upon a characterization of equality of stochastic global maps, shown to be equivalent to the existence of a stochastic coupling between the random sources. We apply them to prove that there is no universal stochastic cellular automaton. Yet we provide stochastic cellular automata achieving optimal partial universality, as well as a universal non-deterministic cellular automaton.
(joint work with Nicolas Schabanel (LIAFA), Guillaume Theyssier (LAMA)

Cellular automata are successful modeling tools, but in many cases the classical regular lattice is not adequate to the problem under investigation. By changing the topology of the lattice, several interesting phenomena occurs. We illustrate an example of a phase transition that can be induced by a change in parameters or in the topology of the lattice. We show also how one can map the change in the topology onto the change in the parameters.

I will review some of the techniques used to prove the existence of phase transitions in equilibrium models and the problems that one encounters if one tries to extend those techniques to PCA.

Metastability is a relevant phenomenon in many different applied sciences. Its full mathematical description is quite recent and still incomplete. In this framework Probabilistic Celluar Automata pose changelling problems and show unexpected behaviors. In this talk some results will be reviewd.

We propose a stochastic dynamics in which N agents update their state simultaneously but not independently. At each time step agents aim at maximizing their individual payoff, depending on their action, on the global trend of the system and on a random noise. In the limit of infinitely many agents, a law of large numbers is obtained; the limit dynamics consist in an implicit dynamical system, possibly multiple valued. For a special model, we determine the phase diagram for the long time behavior of these limit dynamics and we show the existence of a phase, where a locally stable fixed point coexists with a locally stable periodic orbit.

While molecular biology methods are required for a better characterization and identification of individual cancer cells, mathematical modelling and computer simulation is needed for investigating collective effects of cancer invasion. Here, we demonstrate how lattice-gas cellular automaton (LGCA) models allow for an adequate description of individual cancer cell behaviour [1]. We will then show how analysis of the LGCA models allows for prediction of emerging properties (in particular of the invasion speed) [2]. Furthermore, we propose that the transition to invasive phenotypes can be explained on the basis of the microscopic ‘Go or Grow’ mechanism (migration/proliferation dichotomy) and oxygen shortage, i.e. hypoxia, in the environment of a growing tumour. We test this hypothesis again with the help of a lattice-gas cellular automaton. Finally, we use our LGCA models for the interpretation of data from in vitro glioma cancer cell invasion assays [3].

Bootstrap percolation models are Cellular Automata with probabilistic initial conditions. We discuss some results and open problems on the influence of anisotropy on properties of bootstrap percolation models in two and three dimensions. In particular we discuss finite-size scaling behaviour and sharp thresholds.
(Joint work with Tim Hulshof, Anne Fey, Hugo Duminil-Copin)

Modeling natural phenomena or computing, do we need to choose ? On the landscape of randomness in cellular automata

The aim of this talk is to describe a connection between the geometry of the 2d percolation infinite cluster, an important object in statistical mechanics, and the discrete-time and synchronous TASEP, a 1d interacting particle system modeling non-equilibrium phenomena (and which is quite known in the PCA community).
We will point out some consequences and possible extensions.
(joint work with A.L.Basdevant, N.Enriquez, J.B.Gouere)

Angiogenesis, or blood vessel growth from existing ones, is an important physiological process that occur during development, wound healing, as well as diseases such as cancer and diabetes. I will report our recent progress in modeling angiogenesis in the eye in two scenarios. The good refers to healthy blood vessel growth in the retina in mouse embryos, which is a perfect experimental model for understanding the molecular mechanism of angiogenesis. The bad is the
pathological blood vessel growth in age related macular degeneration, which is the leading cause of vision loss in the elderly and a looming epidemic in our aging society. We develop cell-based, multiscale models that include intracellular, cellular, and extracellular scale dynamics, and show that biomechanics of cell-cell and cell-matrix interactions play crucial roll in determining the dynamics of blood vessel growth initiation as well as vascular network formation. Such
models show great potential as in silico Petri-dishes for predictive studies of mechanisms as well as therapies.

The enteric nervous system (ENS) in our gastrointestinal tract, nicknamed the ``second brain'', is responsible for normal gut function and peristaltic contraction. Embryonic development of the ENS involves the colonization of the gut wall from one end to the other by a population of proliferating neural crest cells. Failure of these cells to invade the whole gut results in the relatively common, potentially fatal condition known as Hirschsprung disease (HSCR). Probabilistic cellular automata models provide insight into the colonization process at both the individual cell-level and population-level. Our models generate experimentally testable predictions, which have subsequently been confirmed. These results have important implications for HSCR and highlight the significance of stochastic effects.

Being interested in describing and understanding physical phenomena one is often confronted with the question what effective models to choose as sufficiently realistic. That is true in general
when taking serious models of interacting particle systems such as probabilistic cellular automata (PCA). What specifies the dynamical ensemble when moving outside thermodynamic equilibrium?
We propose to consider the condition of local detailed balance and to introduce the frenetic contribution as a freedom in waiting time distributions. We then show that the minimum entropy production principle (MINEP) in general fails for PCA.

Around Probabilistic Cellular Automata

In this introductory talk, I will first survey how PCA appear in various contexts ranging from combinatorics, to statistical physics and theoretical computer science. I will focus on two problems : the ergodicity of positive rates PCA, and the density classification.

The sinoatrial node is the primary pacemaker of the heart. Nodal dysfunction can lead to a variety of pathological clinical syndromes. Although the basic mechanisms underlying the self-excitation of each
individual nodal cell are accepted, there is still a lot of controversy on how the cells organize themselves to produce the periodic signal, which is strong enough to drive the contraction of the heart tissue.

Approach based on Greenberg-Hastings cellular automata is redrafted to take account of the essential characteristics of both the physiology of a nodal cell and the known facts about the organization between cells. So, the model is based on cells that cycle through firing, refractory and activity stages. If sufficiently many neighbors of a cell are firing then a cell jumps directly from the activity stage to firing stage, or prolong
its refractory stage. These interactions cause the cell synchronize their stages, as in the real pacemaker tissue. The neighborhood connections are created by a stochastic wrinkling algorithm to make the network of
interactions three dimensional and heterogeneous. The synchronization in the system is studied by Kuramoto order parameters. We show that these parameters lead to the consistent description of the system stationary states, that is quantify frequencies emerging in the system. Finally, we will use the model to explain some changes that occur due to aging in the human pacemaker.

Random walk on naturals with negative drift and absorption at $0$, when conditioned on survival, has uncountably many invariant measures (quasi--stationary distributions, \textit{qsd}) $\nu_c$. We study a Fleming--Viot (FV) particle system driven by this process. In this particle system there are $N$ particles where each particle evolves as the random walk described above. As soon as one particle is absorbed, it reappears, choosing a new position
according to the empirical measure at that time. Between the absorptions, the particles move independently of each other. Our focus is in the relation of empirical measure of the FV process with \textit{qsd}'s of the random walk.
Firstly, mean normalized densities of the FV unique stationary measure converge to the minimal \textit{qsd}, $\nu_0$, as $N$ goes to infinity. Moreover, every other \textit{qsd} of the random walk ($\nu_c, c > 0$) corresponds to a metastable state of the FV particle system.

We propose a perfect sampling algorithm for the invariant measure of an ergodic PCA. A PCA is a finite state space Markov chain. Therefore, coupling from the past from all possible initial configurations provides a basic perfect sampling procedure. But it is a very inefficient one since the number of configurations is exponential. Here, the contribution consists in simplifying the procedure. We define a new PCA on an extended alphabet, called the envelope PCA (EPCA). We obtain a perfect sampling procedure for the original PCA by running the EPCA on a single initial configuration. Our algorithm does not assume any monotonicity property of the local rule.
(joint work with A. Busic and J. Mairesse)

Individual cell dynamics in cellular automaton models of interacting cell systems

Lattice-gas cellular automaton (LGCA) models have proven successful in the analysis of collective behavior arising from populations of moving and interacting cells. Examples of collective cell behavior at a macroscopic level include the formation of cell density patterns and the dynamics of moving cell fronts. However, important microscopic observables which emerge as a consequence of collective cell behavior, especially individual cell trajectories, can not be simulated and analyzed with LGCA models so far since these models cannot distinguish individual cells. Here, we introduce an extension of the classical LGCA model, which allows labeling and tracking of individual cells. We name these extended LGCA models "individual-based lattice-gas cellular automata"(IB-LGCA). Furthermore, we derive stochastic differential equations (SDE) corresponding to specific IB-LGCA models, which permit the investigation of individual cell trajectories and the approximate description of IB-LGCA models by systems of SDEs. This
approach allows computationally efficient simulations and analytical treatment of individual cell trajectories in populations of interacting cells. Finally, we present IB-LGCA examples demonstrating the analysis of individual cell trajectories in populations of interacting cells: random cell motion and the motion of cells exposed to an external gradient.

Stochastic self-organization of branched organs: on the growth of blood vessels, glands, and kidneys

Morphogenesis, the formation of biological shape and pattern during embryonic development, is a topic of intensive experimental investigation, so the participating cell types and molecular signals continue to be characterized in great detail. Yet this data only partly tells biologists how molecules and cells interact dynamically to construct a biological tissue. Probabilistic cellular automata are a great help in analyzing the mechanisms of biological morphogenesis.
I will discuss some recent developments on a lattice-based, stochastic model for the formation of blood vessel networks (Merks et al. PLoS Comput Biol 2008), which is based on the cellular Potts model. In this model, we have identified a stochastic mechanism for branching growth that, in a modified form, may play a key role in the formation of branched organs of epithelial origin, e.g., mammary glands and kidneys. I will discuss this model in detail and conclude by suggesting some interesting continuum and stochastic mathematical problems that our simulations suggest.

We consider a system of urns of Polya--type, with balls of two colours; the reinforcement of each urn depends both on the content of the same urn and on the average content of all urns. We show that the urns synchronize almost surely, in the sense that the fraction of balls of a given colour converges almost surely, as the time goes to infinity, to the same limit for all urns. A normal approximation for a large number of urns is also obtained.

Explaining many biological phenomena require a multiscale approach in which the cell is often the natural level of separation between the intracellular regulatory mechanisms and the emerging tissue level. For many tissue level phenomena, the internal mechanism that generates a certain cell behaviour may not be that important, as long as morphodynamically the cells behave realistic enough to serve the purpose of the model trying to explain those phenomena. Cell migration is a vital process in morphogenesis, tissue repair, disease fighting but also disease progression. We propose a phenomenological model for cell migration based on the CPM framwork, that bypasses the complex internal mechanism that drives the cell to move. We show that this simple and computational light method can be calibrated to fit many migration-shape deformation patterns (morphodynamics) including the amoeboid and keratocyte-like migration. The method is suited for random as well as directional migration and is easily applied in the context of crowded multicellular and heterogeneous tissue where cells need to interact.

Hybrid multiscale and partial differential equation models for cancer immunotherapy

Cancer is a heterogeneous disease governed by interconnected processes at multiple spatial and temporal scales. For example, variations in vascular density and blood flow within tumours can have significant effects on nutrient distributions. In addition, such heterogeneities can have significant implications for the delivery and efficacy of drugs and other therapies. We have developed multiscale mathematical models for vascular tumour growth, based upon an extended cellular automata model for cell populations overlaid with networks of blood vessels and the distributions of nutrients, cytokines and therapies [1]. We have used these models to predict the efficacy of novel hypoxia-targeted macrophage-based therapies, conventional therapies, and combination therapies. We find that combination therapies can be highly synergistic, depending on their relative timing, but that host tissue and tumour variability can have important implications for therapeutic efficacy [2]. We have also begun to explore the relationships between our hybrid cellular automaton models and more traditional partial differential equation models.
[1] M R Owen, T Alarcón, P K Maini and H M Byrne: Angiogenesis and vascular remodelling in normal and cancerous tissues, J. Math. Biol. 58:689-721 (2009)
[2] M R Owen, I J Stamper, M Muthana, G W Richardson, J Dobson, C E Lewis and H M Byrne:
Mathematical modeling predicts synergistic antitumor effects of combining a macrophage-based, hypoxia-targeted gene therapy with chemotherapy, Cancer Res. 71(8) 2826-37 (2011)

We study the effect of spatial heterogeneity on the collective motion of self-propelled particles (SPPs). The heterogeneity is modelled as a random distribution of either static or diffusive obstacles, which the SPPs avoid while trying to align their movements. We find that such obstacles have a dramatic effect on the collective dynamics of usual SPP models. In particular, we report about the existence of an optimal (angular) noise amplitude that maximizes collective motion. We also show that while at low obstacle densities the system exhibits long--range order, in strongly heterogeneous media collective motion is quasi--long--range and exists only for noise values in between two critical noise values, with
the system being disordered at both, large and low noise amplitudes. Since most real system have spatial heterogeneities, the finding of an optimal noise intensity has immediate practical and fundamental implications
for the design and evolution of collective motion strategies.

We consider a class of probabilistic cellular automata (PCA) of interest both in statistical physics and in computer science. They are perturbations of cellular automata (CA) that have the property of eroding blocks of impurities in an almost homogeneous configuration. A stochastic perturbation turns the CA into PCA by admitting errors in the states of the cells with some probability distribution. If the erosion is sufficient to correct the effects of errors, the PCA process can have several stationary states, providing an example of non-equilibrium phase transition. We study some properties of these stationary states when the probability of errors is small.

From the point of view of a computer scientist, deterministic cellular automata are known as a parallel computation model. Different studies have introduced randomness in this model by considering probabilistic transitions. In this talk, I will present the different motivations of these studies as well as the current results and open questions.

The aim of this talk is to introduce a class of PCA with some interesting features:
1) the equilibrium measure of the PCA tends to the Gibbs measure of Ising model in the thermodynamical limit.
2) in certain cases it is possible to introduce a unified description of reversible (equilibrium statistical mechanics) and irreversible dynamics (non equilibrium statistical mechanics).
3) Some cases are solved by exact computations.
(joint work with Elisabetta Scoppola and Paolo Dai Pra)

The general question of the influence of the environment on dynamical systems has already been widely studied in the past decades. One of the best known example comes from mathematical physics and is that of the characterisation of phase transitions in the “classical” Ising Model, shown by Dobrushin and Ruelle independently. However, this question remains of particular interest in other contexts, closer to theoretical computer science and biology. For instance, now that cellular automata, and more generally automata networks, are more and more studied as dynamical systems to model and analyse the dynamics of biological regulation networks, such as genetic networks, going further in the understanding of the substantial influence of their environment actually is important.
In this presentation, to make a step in this direction, I propose to tackle from a theoretical point of view the question of the structural instability (in the sense of Thom) of a particular class of two-dimensional finite threshold Boolean cellular automata when the latter are subjected to distinct fixed boundary instances. More precisely, focusing on a nonlinear probabilistic version of the classical threshold function governing the evolution of formal neural networks, I will show the existence of a necessary condition under which attractive cellular automata of this form become boundary sensitive, i.e., a condition without which a cellular automaton hits the same asymptotic dynamical behaviour whatever its boundary conditions are.
Then will be given an explicit formula for this necessary condition, whose sufficiency will be highlighted by simulations.

I will use space-time phases to describe some properties of probabilistic cellular automata (PCA). Space-time phases are probability distributions over state as a function of space and time that arise from initial probabilities in the past. In particular, I will focus on PCA with non-unique phase and show how space-time phases can be used to analyse emergence in such systems. To illustrate the most interesting phenomena I will use numerical demonstration. Furthermore, I will present examples of emergence in PCA used in ecology and economy.
(this research is supported by the Alfred P. Sloan Foundation (New York). (joint work with R.S.MacKay)

Some deterministic cellular automata have long been observed to demonstrate thermodynamic behavior: starting from a random configuration, they undergo a transient dynamics until they reach a state of macroscopic equilibrium. An example is the Ising cellular automaton which can be seen as a deterministic and microscopically reversible variant of a Gibbs sampler (or a micro-canonical sampler). I will discuss some results and open problems regarding (approach to)
macroscopic equilibrium in reversible (and more generally surjective) cellular automata.
(joint work with Jarkko Kari)

Understanding the mechanisms that control tissue organization during development belongs to the most fundamental goals in developmental biology. Quantitative approaches and mathematical models are essential to deduce the consequences of existing morphogenetic hypotheses, thus providing the basis for experimental testing and theoretical understanding. One approach to questions concerning patterning in developing organisms is to consider tissues as huge populations of cells which behave according to certain rules that depend on their genetic programs and inner structure as well as the states and actions of directly neighboring cells. Then, tissue organization can be understood as emergent behavior that results from local intercellular interaction.
PCA provide a spatiotemporal modeling framework to describe and analyze interacting cell populations. They have been successfully applied to study characteristic collective cell behaviors that result from specific cellular interaction rules. However, there are considerable differences in the construction of these models. While cell differentiation, cell death and proliferation can be covered by classical PCA rules, a proper implementation of cell motility is challenging. In the talk, we will compare exemplarily PCA models where one cell occupies one lattice node to spatially more resolved models, such as the CPM. We will expose the mechanistic structures of these models and discuss their implications for analysis and knowledge gain.

PRACTICAL INFORMATION

● Venue

Eurandom is located on the campus of Eindhoven University of Technology, in the brand new TU/e Metaforum building (4th floor) (about the building). The university is located at 10 minutes walking distance from Eindhoven main railway station (take the exit north side and walk towards the tall building on the right with the sign TU/e).
Accessibility TU/e campus and map.

The conference will be held at the Eindhoven Technical University. The TU/e is a relatively young university. It was founded some 50 years ago and is situated in the southern part of The Netherlands in the city of Eindhoven, well known as the hometown of the giant in Electronics, the Philips Company, and the famous football club, PSV Eindhoven. The TU/e intends to be a research driven, design oriented university of technology at an international level, with the primary objective of providing young people with an academic education within the ‘engineering science & technology’ domain.

● Registration

● Accommodation / Funding

Some limited funds are available to contribute to local and travel costs. Participants have to arrange their own hotel booking.

For hotels around the university, please see: Hotels (please note: prices listed are "best available").

Remark: Note that due to a concert at the Eindhoven Philips Stadion on June 7-8-9, it may be difficult to find accommodation before the June 9 in the city centre of Eindhoven.

● Travel

For those arriving by plane, there is a convenient direct train connection between Amsterdam Schiphol airport and Eindhoven. This trip will take about one and a half hour. For more detailed information, please consult the NS travel information pages or see Eurandom web page location.

Many low cost carriers also fly to Eindhoven Airport. There is a bus connection to the Eindhoven central railway station from the airport. (Bus route number 401) For details on departure times consult http://www.9292ov.nl

● Conference facilities : Conference room, Metaforum Building MF11&12

The meeting-room is equipped with a data projector, an overhead projector, a projection screen and a blackboard. Please note that speakers and participants making an oral presentation are kindly requested to bring their own laptop or their presentation on a memory stick.

● Conference Secretariat

Upon arrival, participants should register with the workshop officer, and collect their name badges. The workshop officer will be present for the duration of the conference, taking care of the administrative aspects and the day-to-day running of the conference: registration, issuing certificates and receipts, etc.

● Cancellation

Should you need to cancel your participation, please contact Patty Koorn, the Workshop Officer.

● Contact

Mrs. Patty Koorn, Workshop Officer, Eurandom/TU Eindhoven, koorn@eurandom.tue.nl

European Institute for Statistics, Probability, Stochastic Operations Research
and their Applications

ORGANISERS

LIST OF SPEAKERS

WEDNESDAY JUNE 12

n.b. All abstracts are included in the BOOKLET, which has been printed for all participants.

ABSTRACTS

PRACTICAL INFORMATION

● Venue

● Registration

● Accommodation / Funding

● Travel

● Conference facilities : Conference room, Metaforum Building MF11&12

● Conference Secretariat

● Cancellation

● Contact

SPONSORS

Other events of interest around this meeting

Links to meetings on related topics

Legal notice: privacy statement

Last updated 08-07-13,
by PK

European Institute for Statistics, Probability, Stochastic Operations Research and their Applications

ORGANISERS

LIST OF SPEAKERS

WEDNESDAY JUNE 12

n.b. All abstracts are included in the BOOKLET, which has been printed for all participants.

ABSTRACTS

PRACTICAL INFORMATION

● Venue

● Registration

● Accommodation / Funding

● Travel

● Conference facilities : Conference room, Metaforum Building MF11&12

● Conference Secretariat

● Cancellation

● Contact

SPONSORS

Other events of interest around this meeting

Links to meetings on related topics

Legal notice: privacy statement

Last updated 08-07-13, by PK

European Institute for Statistics, Probability, Stochastic Operations Research
and their Applications

Last updated 08-07-13,
by PK