Quantifying Flows in Time-Irreversible Markov Chains

Abstract

Stochastic networks a.k.a. Markov chains allow us to model phenomena in systems arising in many applications. The appeal of stochastic networks is that they offer a mathematically tractable and robust model focused on the most important features of the system. Nevertheless, stochastic networks approximating complex systems can be huge and unstructured, and an effective description of their dynamics is a challenging mathematical problem. This dissertation is motivated by our study of two models of a gene regulatory network (GRN), one deterministic [1] and one stochastic [2], which describes the budding yeast cell cycle. A GRN with N nodes can be straightforwardly converted into a Markov chain with 2^N states. Our scientific goal is to understand how the stochasticity affects the stability of the cell cycle in the GRN. This gives rise to our mathematical goal: to develop efficient tools for quantifying dynamics of large time-irreversible Markov chains. Our methodological developments are built upon the transition path theory (TPT) [16] which is a general framework for describing transitions in Markov chains between two subsets of states. In TPT, the transition process is described by the so- called effective current. We have realized that the effective current gives a lopsided description of the transition process in the case of time-irreversible networks where elementary cycles of length greater than two are present. Thus, we have introduced the so-called acyclic current that gives a quantitative description of a transition process and proposed an algorithm to compute it. Moreover, we have developed a general recipe to modify the generator matrix of a given Markov chain in order to make the stationary probability current and the invariant distribution in the modified chain coincide with a desired current and a desired invariant distribution in the original chain. Finally, we have applied these tools to the budding yeast cell cycle GRN. Our results show which edges are essential and which ones are redundant. Our computations eloquently demonstrate that stochasticity makes the GRN much more stable with respect to edge removals. This conclusion is consistent with Q. Nie’s statement [26] that stochasticity plays a fundamental role in biological processes.