TY - THES A1 - Rohr, Christian T1 - Simulative analysis of coloured extended stochastic Petri nets T1 - Simulative Analyse von gefärbten erweiterten stochastischen Petri Netzen N2 - Stochastic modelling of biochemical reaction networks is getting more and more popular. Throughout the past decades typical biological models increased in their size and complexity, because of advances in systems and molecular biology, in particular through the high-throughput omic technologies. Here biochemical networks of different levels of detail are modelled, starting with simple chemical reactions and signal transduction networks, up to individual cells and entire organisms. This increases the demand for efficient analysis methods. A Petri net is a mathematical modelling language for the description of concurrent behaviour of distributed systems. Its advantage is the ease of scalability of the models, which relates to the network’s state space, as well as the structure of the network itself. In this work, we recall several stochastic simulation algorithms, e.g., exact as well as approximate methods. Furthermore, we introduce an approach to improve the efficiency of stochastic simulation for large and dense networks by a new approximate stochastic simulation algorithm called discrete-time leap method. We depict the wide range of simulative analyses of complex stochastic systems ranging from trace generation to the computation of transient solutions and steady state distributions. We set forth advanced analysis of stochastic models by means of simulative model checking. For the use of simulative model checking, we integrate the continuous stochastic (reward) logic (CS(R)L) and the probabilistic linear-time temporal logic with constraints (PLTLc). Simulative model checking has some limitations compared to the numerical methods, e.g., in principle it is possible to consider nested probabilistic formulas in CS(R)L, but not practical, since the calculation is not feasible in a reasonable period of time. In addition to the transient analysis, the steady state analysis is often of interest; therefore we have implemented two on-the-fly steady state detection methods. The first one is based on a “sample batch means” algorithm and is used in the linear-time temporal logic. The second approximates the steady state distribution and checks for convergence. We apply the aforementioned techniques to several case studies from systems biology and technical systems. The main contributions of this thesis to scientific knowledge are the development of the discrete-time leap method for the simulation of stochastic models, the approximations of transient solutions and steady state distributions by use of stochastic simulation for stochastic models and Markov reward models, the development of an infinite time horizon model checking algorithm exploiting the steady state property for PLTLc and CSL, and the first simulative model checking algorithm for CSRL incorporating state and impulse rewards. All presented algorithms and methods are implemented in the advanced analysis tool MARCIE. N2 - Stochastische Modellierung von biochemischen Reaktionsnetzwerken wird immer populärer. Im Laufe der letzten Jahrzehnte hat sich sowohl die Größe als auch die Komplexität typischer biologischer Modelle immer weiter erhöht. Hier werden biochemische Netzwerke unterschiedlicher Detailebenen modelliert, beginnend mit einfachen chemischen Reaktionen und Signaltransduktionsnetzwerken, bis zu einzelnen Zellen und ganzen Organismen. Dadurch erhöht sich die Nachfrage nach leistungsfähigen Analyseverfahren. Ein Petri-Netz ist eine mathematische Modellierungssprache für die Beschreibung des nebenläufigen Verhaltens von verteilten Systemen. Ein Vorteil ist die einfache Skalierbarkeit der Modelle sowohl in Bezug auf die Struktur des Netzes als auch auf ihren Zustandsraum. In dieser Arbeit stellen wir verschiedene stochastische Simulationsalgorithmen vor, sowohl exakte wie auch approximative Verfahren. Darüber hinaus stellen wir einen Ansatz vor, um die Effizienz der stochastischen Simulation für große und dichte Netzwerke durch einen neuen approximativen stochastischen Simulation Algorithmus, genannt discrete-time leap method, zu verbessern. Wir zeigen das breite Spektrum der simulativen Analysen komplexer stochastischer Systeme von der Pfaderzeugung bis zur Berechnung von transienten Lösungen und stationärer Verteilungen. Wir legen erweiterte Analysen von stochastischen Modellen mit Hilfe von simulativer Modellprüfung dar. Wir integrieren die Continuous Stochastic (Reward) Logic (CS(R)L) und die Probabilistic Linear-time Temporal Logic with contraints (PLTLc) für die simulative Modellprüfung. Neben der Transientenanalyse ist oftmals die Analyse der stationären Verteilung von Interesse, deshalb haben wir zwei Methoden zur Erkennung des stationären Zustandes implementiert. Die erste basiert auf einem “sample batch means” Algorithmus und wird in der linearen temporalen Logik verwendet. Die zweite approximiert die stationäre Verteilung und prüft auf Konvergenz. Wir wenden die oben genannten Techniken auf mehrere Fallstudien aus Systembiologie und technischen Systemen an. Der größte Beitrag dieser Arbeit zum aktuellen Stand von Wissenschaft und Technik liegt in der Entwicklung der discrete-time leap method zur Simulation stochastischer Modelle, der Approximationen transienter Lösungen und stationärer Verteilungen mittels stochastischer Simulation für stochastische Modelle und Markov-Rewardmodelle, der Entwicklung eines nicht zeitbeschränkten Algorithmus zur simulativen Modellprüfung, der die stationäre Eigenschaft für PLTLc und CSL ausnutzt, und des ersten Algorithmus zur simulativen Modellprüfung für CSRL, der Zustands- und Impulsrewards enthält. Alle vorgestellten Algorithmen und Methoden sind in dem Analyse-Tool MARCIE implementiert. KW - Coloured extended Stochastic Petri Nets KW - Stochastic simulation KW - Delta-leaping KW - Simulative model checking KW - Gefärbte erweiterte stochastische Petri Netze KW - Stochastische Simulation KW - Delta-leaping KW - Simulatives Modelchecking KW - Stochastisches Modell KW - Gefärbtes Petri-Netz KW - Model Checking Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-41476 ER -