Search

Molecular noise, which arises from the randomness of the discrete events in the cell, significantly influences fundamental biological processes. Discrete -state continuous-time stochastic models (CTMC) can be used to describe such effects, but the calculation of the probabilities of certain events is computationally expensive. We present a comparison of two analysis approaches for CTMC. On one hand, we estimate the probabilities of interest using repeated Gillespie simulation and determine the statistical accuracy that we obtain. On the other hand, we apply a numerical reachability analysis that approximates the probability distributions of the system at several time instances. We use examples of cellular processes to demonstrate the superiority of the reachability analysis if accurate results are required. [ABSTRACT FROM AUTHOR]

We present an on-the-fly abstraction technique for infinite-state continuous -time Markov chains. We consider Markov chains that are specified by a finite set of transition classes. Such models naturally represent biochemical reactions and therefore play an important role in the stochastic modeling of biological systems. We approximate the transient probability distributions at various time instances by solving a sequence of dynamically constructed abstract models, each depending on the previous one. Each abstract model is a finite Markov chain that represents the behavior of the original, infinite chain during a specific time interval. Our approach provides complete information about probability distributions, not just about individual parameters like the mean. The error of each abstraction can be computed, and the precision of the abstraction refined when desired. We implemented the algorithm and demonstrate its usefulness and efficiency on several case studies from systems biology. [ABSTRACT FROM AUTHOR]

We compare several languages for specifying Markovian population models such as queuing networks and chemical reaction networks. These languages –matrix descriptions, stochastic Petri nets, stoichiometric equations, stochastic process algebras, and guarded command models– all describe continuous-time Markov chains, but they differ according to important properties, such as compositionality, expressiveness and succinctness, executability, ease of use, and the support they provide for checking the well-formedness of a model and for analyzing a model. [ABSTRACT FROM AUTHOR]

This paper proposes a novel abstraction technique based on Erlang΄s method of stages for continuous-time Markov chains (CTMCs). As abstract models Erlang-k interval processes are proposed where state residence times are governed by Poisson processes and transition probabilities are specified by intervals. We provide a three-valued semantics of CSL (Continuous Stochastic Logic) for Erlang-k interval processes, and show that both affirmative and negative verification results are preserved by our abstraction. The feasibility of our technique is demonstrated by a quantitative analysis of an enzyme-catalyzed substrate conversion, a well-known case study from biochemistry. [ABSTRACT FROM AUTHOR]

Stochastic models of biological networks properly take the randomness of molecular dynamics in living cells into account. Numerical solution approaches inspired by computational methods from applied probability can efficiently yield accurate results and have significant advantages compared to stochastic simulation. Examples for the success of non-simulative numerical analysis techniques in systems biology confirm the enormous potential. [ABSTRACT FROM AUTHOR]

Constraint automata have been used as an operational model for component connectors that coordinate the cooperation and communication of the components by means of a network of channels. In this paper, we introduce a variant of constraint automata (called continuous-time constraint automata) that allows us to specify time-dependent stochastic assumptions about the channel connections or the component interfaces, such as the arrival rates of communication requests, the average delay of enabled I/O-operations at the channel ends or the stochastic duration of internal computations. This yields the basis for a performance analysis of channel-based coordination mechanisms. We focus on compositional reasoning and discuss several bisimulation relations on continuous-time constraint automata. For this, we adapt notions of strong and weak bisimulation that have been introduced for similar stochastic models and introduce a new notion of weak bisimulation which abstracts away from invisible non-stochastic computations as well as the internal stochastic evolution. [ABSTRACT FROM AUTHOR]

In this paper the abstraction-refinement paradigm based on 3-valued logics is extended to the setting of probabilistic systems. We define a notion of abstraction for Markov chains. To be able to relate the behavior of abstract and concrete systems, we equip the notion of abstraction with the concept of simulation. Furthermore, we present model checking for abstract probabilistic systems (abstract Markov chains) with respect to specifications in probabilistic temporal logics, interpreted over a 3-valued domain. More specifically, we introduce a 3-valued version of probabilistic computation-tree logic (PCTL) and give a model checking algorithm w.r.t. abstract Markov chains. [ABSTRACT FROM AUTHOR]

Computational models of biochemical systems are usually very large, and moreover, if reaction frequencies of different reaction types differ in orders of magnitude, models possess the mathematical property of stiffness, which renders system analysis difficult and often even impossible with traditional methods. Recently, an accelerated stochastic simulation technique based on a system partitioning, the slow-scale stochastic simulation algorithm, has been applied to the enzyme-catalyzed substrate conversion to circumvent the inefficiency of standard stochastic simulation in the presence of stiffness. We propose a numerical algorithm based on a similar partitioning but without resorting to simulation. The algorithm exploits the connection to continuous-time Markov chains and decomposes the overall problem to significantly smaller subproblems that become tractable. Numerical results show enormous efficiency improvements relative to accelerated stochastic simulation. Keywords: Biochemical Reactions, Stochastic Model, Markov Chain, Aggregation. [ABSTRACT FROM AUTHOR]

The aim of this chapter is to give a survey of testing relations for probabilistic systems. We summarize the relevant material on probabilistic extensions of the work of De Nicola and Hennessy [dNH84] who defined implementation relations for nondeterministic processes based on a notion of testing (see also Chapter 5). We mainly concentrate on the relative expressive power of the different preordersWe use the term "preorder" as synonym for "testing relation" although it might be the case that the respective relation is not transitive or transitivity has not been shown.. All presented relations are primarily of theoretical interest and to the best of our knowledge their usefulness in practical applications has not been shown yet. [ABSTRACT FROM AUTHOR]