Propagation Models for Biochemical Reaction Networks

In this thesis we investigate different ways of approximating the solution of the chemical master equation (CME). The CME is a system of differential equations that models the stochastic transient behaviour of biochemical reaction networks. It does so by describing the time evolution of probability distribution over the states of a Markov chain that represents a biological network, and thus its stochasticity is only implicit. The transient solution of a CME is the vector of probabilities over the states of the corresponding Markov chain at a certain time point t, and it has traditionally been obtained by applying methods that are general to continuous-time Markov chains: uniformization, Krylov subspace methods, and general ordinary differential equation (ODE) solvers such as the fourth order Runge-Kutta method. Even though biochemical reaction networks are the main application of our work, some of our results are presented in the more general framework of propagation models (PM), a computational formalism that we introduce in the first part of this thesis. Each propagation model N has two associated propagation processes, one in discrete-time and a second one in continuous-time. These propagation processes propagate a generic mass through a discrete state space. For example, in order to model a CME, N propagates probability mass. In the discrete-time case the propagation is done step-wise, while in the continuous-time case it is done in a continuous flow defined by a differential equation. Again, in the case of the chemical master equation, this differential equation is the equivalent of the chemical master equation itself where probability mass is propagated through a discrete state space. Discrete-time propagation processes can encode methods such as the uniformization method and the fourth order Runge-Kutta integration method that we have mentioned above, and thus by optimizing propagation algorithms we optimize both of these methods simultaneously. In the second part of our thesis, we define stochastic hybrid models that approximate the stochastic behaviour of biochemical reaction networks by treating some variables of the system deterministically. This deterministic approximation is done for species with large populations, for which stochasticity does not play an important role. We propose three such hybrid models, which we introduce from the coarsest to the most refined one: (i) the first one replaces some variables of the system with their overall expectations, (ii) the second one replaces some variables of the system with their expectations conditioned on the values of the stochastic variables, (iii) and finally, the third one, splits each variable into a stochastic part (for low valuations) and a deterministic part (for high valuations), while tracking the conditional expectation of the deterministic part. For each of these algorithms we give the corresponding propagation models that propagate not only probabilities but also the respective continuous approximations for the deterministic variables.

Dynamical low rank approximation for uncertainty quantification of time-dependent problems

Eva Vidlicková

The quantification of uncertainties can be particularly challenging for problems requiring long-time integration as the structure of the random solution might considerably change over time. In this respect, dynamical low-rank approximation (DLRA) is very appealing. It can be seen as a reduced basis method, thus solvable at a relatively low computational cost, in which the solution is expanded as a linear combination of a few deterministic functions with random coefficients. The distinctive feature of the DLRA is that both the deterministic functions and random coefficients are computed on the fly and are free to evolve in time, thus adjusting at each time to the current structure of the random solution. This is achieved by suitably projecting the dynamics onto the tangent space of a manifold consisting of all random functions with a fixed rank. In this thesis, we aim at further analysing and applying the DLR methods to time-dependent problems.Our first work considers the DLRA of random parabolic equations and proposes a class of fully discrete numerical schemes.Similarly to the continuous DLRA, our schemes are shown to satisfy a discrete variational formulation.By exploiting this property, we establish the stability of our schemes: we show that our explicit and semi-implicit versions are conditionally stable under a ``parabolic'' type CFL condition which does not depend on the smallest singular value of the DLR solution; whereas our implicit scheme is unconditionally stable. Moreover, we show that, in certain cases, the semi-implicit scheme can be unconditionally stable if the randomness in the system is sufficiently small. The analysis is supported by numerical results showing the sharpness of the obtained stability conditions. The discrete variational formulation is further applied in our second work, which derives a-priori and a-posteriori error estimates for the discrete DLRA of a random parabolic equation obtained by the three newly-proposed schemes. Under the assumption that the right-hand side of the dynamical system lies in the tangent space up to a small remainder, we show that the solution converges with standard convergence rates w.r.t. the time, spatial, and stochastic discretization parameters, with constants independent of singular values.We follow by presenting a residual-based a-posteriori error estimation for a heat equation with a random forcing term and a random diffusion coefficient which is assumed to depend affinely on a finite number of independent random variables. The a-posteriori error estimate consists of four parts: the finite element method error, the time discretization error, the stochastic collocation error, and the rank truncation error. These estimators are then used to drive an adaptive choice of FE mesh, collocation points, time steps, and time-varying rank.The last part of the thesis examines the idea of applying the DLR method in data assimilation problems, in particular the filtering problem. We propose two new filtering algorithms. They both rely on complementing the DLRA with a Gaussian component. More precisely, the DLR portion captures the non-Gaussian features in an evolving low-dimensional subspace through interacting particles, whereas each particle carries a Gaussian distribution on the whole ambient space. We study the effectiveness of these algorithms on a filtering problem for the Lorenz-96 system.

EPFL2022

Hybrid Numerical Solution of the Chemical Master Equation

Maria-Emanuela-Canini Mateescu, Verena Wolf

We present a numerical approximation technique for the analysis of continuous-time Markov chains that describe networks of biochemical reactions and play an important role in the stochastic modeling of biological systems. Our approach is based on the construction of a stochastic hybrid model in which certain discrete random variables of the original Markov chain are approximated by continuous deterministic variables. We compute the solution of the stochastic hybrid model using a numerical algorithm that discretizes time and in each step performs a mutual update of the transient probability distribution of the discrete stochastic variables and the values of the continuous deterministic variables. We implemented the algorithm and we demonstrate its usefulness and efficiency on several case studies from systems biology.

2010

Stochastic Control and Free Boundary Problems for Sailboat Trajectory Optimization

Laura Vinckenbosch

The topic of this thesis is the study of several stochastic control problems motivated by sailing races. The goal is to minimize the travel time between two locations, by selecting the fastest route in face of randomly changing weather conditions, such as wind direction. When a sailboat is travelling upwind, the key is to decide when to tack. Since this maneuver slows down the yacht, it is natural to model this time lost by a "tacking penalty" which places the problem in the context of optimal stochastic control problems with switching costs. An objective of this work is to propose and to study mathematical models that capture some of the features of a sailing race, but which remain amenable to an explicit rigorous solution that can be proved to be optimal. We consider three different models in which the wind direction is described by a stochastic process. In the first model, we consider a wind that changes randomly only once. In the second model, the wind oscillates between two possible directions according to a continuous-time Markov chain. We exhibit a free boundary problem for the value function involving hyperbolic partial differential equations of Klein-Gordon type. The last model considers the wind direction as a Brownian motion. We prove the existence of a finite value function and exhibit a free boundary problem involving parabolic partial differential equations with non-constant coefficients. In these three models, the optimal solution consists of a partition of the state space into a region where it is optimal to tack immediately and a region where it is optimal to continue on the current tack. The boundaries between these regions are given by one or more "switching curves" and in the cases where we have been able to exhibit them, the optimality of the solution is established by a verification theorem based on the martingale method. We also solve two other control problems in which a player tries to minimize or maximize the exit time from an interval of a Brownian particle by controlling its drift and subject to a switching penalty. In each problem, the value function is written as the solution of a second order ordinary differential equations problem whose unknown boundaries are found by applying the principle of smooth fit. For both problems, we exhibit a candidate strategy as a function of the switching cost and we prove its optimality as well as its generic uniqueness.