Sep 30, 2014: Tobias Heindel: Beyond the Rate Equation -- Average motif counts in Markov chains of graph transformation systems

September 30, 2014Beyond the Rate Equation -- Average motif counts in Markov chains of graph transformation systems
Room: Carre 3ATobias Heindel
12:30-13:30

The dynamics of the average molecule count of a chemical species in a test tube over time is the paradigm example for motif counts in continuous time systems with discrete state space. More generally, we can consider average counts of "observable" graph motifs in Markov processes that are specified by graph transformation systems (GTS). Such average counts can be used to measure network flows, protein production in cells, and the speed of DNA-walkers.

Computing average motif counts is typically extremely complicated if not impossible as it often amounts to solving the master equation of the underlying Markov chain with countable state space. The rate equation for molecule counts (per volume) is an established ODE approximation for chemical reaction networks (aka stochastic Petri nets).  Existing approximation schemes for very simple examples of GTSs, such as voter models, are already much more intricate, seemingly ad-hoc, and typically problem specific. Thus, the talk will focus on the underlying exact infinite linear ODE that describes average motif counts. Interestingly, the example of the speed of a DNA-walker can be solved exactly. The talk concludes with a glimpse at latest results and the research agenda of the approximation of stochastic graph transformation systems.