Markov models are omnipresent in the applied sciences. Although their analysis has a long research history, the development of new methods is more important than ever. Modern technologies provide novel data, and therefore realworld phenomena are captured more accurately based on enhanced models.
In the ALMA group, we focus on Markov modeling and develop algorithms for the analysis and simulation of Markov processes. In some projects, we consider particular applications and work closely together with experimentalists. Other projects are aimed at algorithms for general classes of models, or solutions for problems that appear in different application areas.
The Analysis of Markovian Models (ALMA) Group is part of the Cluster of Excellence since March 2009. The group concentrates mainly on stochastic modeling and analysis techniques and has a particular focus on applications in the area of quantitative biology. The group consists of four PhD students, Alexander Lück, Thilo Krüger, Charalampos Kyriakopoulos and Michael Backenköhler, as well as the group leader, Prof. Verena Wolf.
Numerical algorithms for stochastic models of chemical reaction networks
We proposed a numerical approximation technique for mesoscopic Markov models of chemical reaction networks and later extended it to a hybrid method. Both algorithms solve models that take into account the inherent discreteness of molecules and the randomness of the encounters between molecules that lead to reactions. This is particularly important if chemical species are present in low copy numbers. In that case, the relative variation in copy numbers may become large, and it is necessary to account for the stochasticity of the internal state of the system. Such models have been shown to appropriately represent processes such as gene expression, biochemical oscillations, and signaling pathways. The hybrid approach has the advantage that it can be applied to systems where certain variables change deterministically and continuously in time, but other variables show discrete and stochastic behavior.
Parameter Inference
In this project, we focus on the inference of parameters of Markov models of chemical reaction networks based on noisy timeseries data. We estimate the kinetic rate constants by maximizing the likelihood of the data. The computation of the likelihood relies on a dynamic abstraction of the discrete state space of the Markov model, which successfully mitigates the problem of large state space size. Our method can be used for arbitrarilyspaced observation intervals and for fully as well as partially observed systems.
Multistable decision switches
Cellular systems use switchlike behavior to decide between different strategies, e.g., as a response to an external signal. Often the underlying mechanism is the multistability of the corresponding chemical reaction network. If a Markov process representation is chosen, multistability is reflected by the shape of the probability distribution. The stability analysis of the model turns out to be challenging because computable stability criteria for such models have rarely been studied. We propose the use of drift functions to analyze the stability of the underlying Markov process and compute the stable regions and their probabilities. With our current approach, we are able to derive geometric bounds for the steadystate distribution and detect multistable behavior. In ongoing work, we consider necessary and sufficient criteria for multistability, which are of particular interest in the area of synthetic biology.
Computation of rare event probabilities in large structured Markov models
Rare events, such as gene mutations and overcoming of gene repression, play an important role for the development of certain diseases. Stochastic models of such rare event systems are difficult to simulate. The reason is that, even if a large number of trajectories of the model is generated, the rare event may not occur during the simulation, since its probability is extremely small. Importance sampling techniques are helpful in such situations because they change the underlying probability measure in such a way that the rare event becomes more likely.
Currently, we are working on methods that combine importance sampling with previous numerical solution techniques in order to approximate the probabilities of rare events. The main idea is to determine sequences of events that lead to the rare event of interest and direct the numerical solution accordingly. Our approach has many adavantages compared to traditional importance sampling techniques. During the numerical solution, an approximation of the probability distribtion is calculated. It can be used to decide on the fly which change of measure is appropriate. Moreover, we can avoid using the correction factor for the importance sampling estimates by solving the original system and the system with the change of measure simultaneously. Our preliminary results indicate that our approach works suprisingly quickly and accurately compared to classical rare event simulation techniques.
The ALMA group has joint projects with two research group at Saarland University, as well as groups at the Institute of Science and Technology Austria, the University of Oldenburg, the University of Freiburg, and the TU Clausthal.
Recent collaborations

Together with the group headed by Jörn Walter, Professor of Epigenetics at Saarland University, we use Markov models to represent the dynamics of CpG DNA methylation patterns. Based on experimental results, we estimate methylation probabilities for different methyltransferases.

Within SFB/TR 14 AVACS (Automatic Verification and Analysis of Complex Systems), we collaborate with the groups headed by Martin Fränzle and Oliver Theel (University of Oldenburg), the groups led by Bernd Becker and Andreas Podelski (University of Freiburg), and Holger Hermanns' group (Saarland University).

With Thomas A. Henzinger's group (Institute of Science and Technology in Austria) we are developing a software tool, called SABRE, for the analysis of Markov processes that describe networks of chemical reactions.

Finally, we work on the approximation of rare event probabilities together with Werner Sandmann's group (TU Clausthal).
Former collaborations

Together with Matthias Seeger's group (EPFL, Switzerland), we have been working on parameter estimation techniques for large Markov chains. We focus mainly on biological applications.

Together with the group headed by Ludger Santen, Professor of Theoretical Physics at Saarland University, we analyzed Markov models of microtubule dynamics in cells. Since this model incorporates spatial information, we used abstraction techniques to cope with the large size of the underlying state space and approximate the quantities of interest.