Numerical analysis of long-run properties for Markov population models

Abstract

One of the most versatile modeling formalism is the one given by Markov chains as used for the performance analysis of queuing systems or for cost benenefit ratio optimizations in the financial sector. In systems biology, chemical reaction networks have originally been studied using deterministic models. However, when it recently became apparent that only stochastic effects can explain certain phenomenons, Markov chains again turned out to be a suitable modeling formalism in the form of Markov population models. Those Markov chains possess a structured but potentially infinite state space where each state encodes the current counts of a fixed number of population types. Due to the infinite state space, classical steady state analysis methods can not be used directly. Hence, this doctoral thesis presents a highly efficient method to compute a finite state space truncation entailing most of the steady state probability mass. Further, stochastic complementation is lifted to the infinite state space setting and is combined with truncation based reachability analysis and aggregation to derive state wise steady state bounds. This method achieves high performance even for stiff systems. Particular attention is paid on a system's ability to maintain stable oscillations and thus optimized analysis methods are developed alongside. In order to prove their applicability, all techniques are evaluated on a large variety of biological models.

Ursprünglich wurden chemische Reaktionsnetzwerke in der Systembiologie mit Hilfe von deterministischen Modellen analysiert. Als jedoch klar wurde, dass bestimmte Phänomene nur durch stochastische Effekte erklärt werden können, erwiesen sich Markovsche Populationsmodelle als geeigneter Formalismus. Diese Markovketten besitzen einen strukturierten Zustandsraum, wobei ein Zustand die aktuelle Anzahl einer oder mehrerer Populationstypen kodiert. Oft ist dieser Zustandsraums jedoch unendlich groß und klassische Methoden für die Analyse des Equilibriums können nicht benutzt werden. Diese Doktorarbeit präsentiert daher eine effiziente Methode, ein endlich großes Fenster im Zustandsraum zu berechnen, welches den Großteil der Equilibriumswahrscheinlichkeitsmasse umschließt. Zudem wird das Verfahren der stochastischen Komplementierung für das vorliegende Szenario erweitert und mit Aggregationsmethoden und der Erreichbarkeitsanalyse basierend auf dem Abschneiden von nicht signifikanten Zuständen kombiniert. Diese Methode erlaubt die Berechnung von Schranken für die Equilibriumswahrscheinlichkeit aller Zustände innerhalb des Fensters und ist performant - sogar für steife Systeme. Der Fähigkeit eines Systems, stabile Oszillationen aufrecht zu erhalten, wird spezielle Aufmerksamkeit geschenkt und die entsprechende Analyse optimiert. Um ihre Einsetzbarkeit zu zeigen werden alle Methoden anhand einer Vielzahl biologischer Modelle evaluiert.