• search hit 10 of 91
Back to Result List

Simulative analysis of coloured extended stochastic Petri nets

Simulative Analyse von gefärbten erweiterten stochastischen Petri Netzen

  • 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 newStochastic 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.show moreshow less
  • 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 neuenStochastische 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.show moreshow less

Download full text files

Export metadata

Additional Services

Search Google Scholar Stastistics
Metadaten
Author: Christian Rohr
URN:urn:nbn:de:kobv:co1-opus4-41476
Referee / Advisor:Prof. Dr.-Ing. Monika Heiner, Prof. Dr. rer. nat. Wolfgang Marwan, Prof. Dr. David Gilbert
Document Type:Doctoral thesis
Language:English
Year of Completion:2016
Date of final exam:2017/01/10
Release Date:2017/03/09
Tag:Delta-leaping; Gefärbte erweiterte stochastische Petri Netze; Simulatives Modelchecking; Stochastische Simulation
Coloured extended Stochastic Petri Nets; Delta-leaping; Simulative model checking; Stochastic simulation
GND Keyword:Stochastisches Modell; Gefärbtes Petri-Netz; Model Checking
Institutes:Fakultät 1 MINT - Mathematik, Informatik, Physik, Elektro- und Informationstechnik / FG Datenstrukturen und Softwarezuverlässigkeit
Licence (German):Keine Lizenz vergeben. Es gilt das deutsche Urheberrecht.
Einverstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.