Singh, Kapil;Prank, Klaus - Efficient Stochastic Simulation of Intracellular Signalling

ECCB 2002 Poster sorted by: Author | Number

Next | Previous poster (in order of the view you have selected)

Title: Efficient Stochastic Simulation of Intracellular Signalling	P153
Singh, Kapil; Prank, Klaus klaus.prank@uni-bielefeld.de, ksingh@uni-bielefeld.de NRW Graduate School in Bioinformatics and Genome Research, Centre of Biotechnology (CeBiTec), Bielefeld University, Bielefeld, Germany.

The broad aim of the project is to develop a simulator for intracellular signalling that can bridge the gap between mathematical models of the biological system under study to the simulators and construct a better data structure to improve the efficiency of the simulation algorithm. Many approaches exist for the simulation of biochemical cellular processes using deterministic and stochastic modelling approaches [1, 2]. Just recently the goal has been set for whole cell simulation [3]. Stochastic simulators consume more computing power and are thus generally used for smaller models. Nonetheless Gibson [4, 5] has improved the efficiency of stochastic simulation algorithms [1, 2] with his simulation system "Stochastirator"such that whole cell simulation comes within reach. Thus, the major objectives are:
1. Parsing deterministic ordinary differential equations into a stochastic master equation
2. Development of efficient models using the Gibson algorithm
3. Linking Parser to the Gibson Simulator
4. Development of data structures for minimizing space, time complexity and increasing flexibility and accessibility.

Why using stochastic approaches for the simulation of intracellular signalling?
The usual approach for modeling biochemical kinetics is to solve a set of differential equations which comprise the biochemical model by numerical integration. However, in dealing with situations where there are only a few reactants of some species present, the continuity assumption of the differential equation approach breaks down. An alternative approach is to perform a stochastic simulation of the system, whereby each reaction taking place is simulated by using Monte-Carlo methods. This approach is valid even when the reactant populations are very low.

Why using the Gibson algorithm?
Better efficiency of the Gibson approach over the algorithms proposed by Gillespie [1, 2] proves the feasibility of it in using it for simulation of complex biochemical pathways involving large number of chemical species and reactions. So, in the ongoing project the Gibson approach has been used to develop a model that can simulate complex metabolic pathways efficiently. Strong points of Gibson's approach are use of only one random number and taking time proportional to logarithm of number of reactions.

The Parser-program STODE
The program is separated logically into two main tasks [6]. The first consists of reading and processing the differential equations, while the second consists of running the simulation. For the first part, STODE takes as input a text file specifying the set of differential equations to be parsed, as well as the rate constants, reactants (with their initial concentrations) and other constants needed to determine the system. This file is lexically analysed into tokens and fed to a grammar which initiates and assigns values to the various variables representing the reactants, constants and differential equations. Following this, STODE reconstructs the reactions associated with the differential equations, and if necessary calculates the actual particle numbers from the given reactant concentrations. The second task is to perform the simulation. This is done according to Gillespie's algorithm [1, 2].

Approach
The starting point can be either (1) Elementary Chemical Reactions, or (2) Differential Equations. The two starting points are correlated to each other in the project as differential equations are parsed into the elementary chemical reactions using a parser which uses a lexical analyser and a parsing grammar. The differential equation approach is more useful as every reaction and event occurring inside the cell can be represented as differential equations. The existing parser STODE, for handling differential equations, does not incorporate the time dependent rate constants, the possibility of different input conditions (pulse input etc.) and it uses Gillespie algorithm, which uses two random variables. So, it leads to develop a flexible parser with Gibson algorithm for simulation.
Now, if elementary reactions or differential equations through a parser are used as the input, both will lead to handle huge amount of data if we envisage the whole cell modelling. The way of handling the huge amount of data e.g. chemical identity, concentrations, rate constants etc. will play an crucial role and the need of accessing the data in the future should be kept in mind. So, in the project the data is stored as mutually linked lists, resulting in the better handling and accessibility at any instant. The data, generated after parsing the differential equations or fed directly through the elementary reaction equations, is maintained in three mutually linked lists [fig. 1],
(1) Reaction list: Each node is maintained containing following fields
(1.1) Link to the list of reactants of the node reaction.
(1.2) Link to the list of products of the node reaction.
(1.3) Propensity function of the reaction.
(1.4) Rate constant of the reaction.
(1.5) Link to the next reaction node.
(2) Reactant list: Each node is maintained containing following fields,
(2.1) Reactant name
(2.2) Concentration of reactant.
(2.3) Combinations of selection of reactant for the reaction.
(2.4) Link to the next reactant list node.
(3) Product list: Each node is maintained containing following fields.
(3.1) Product name.
(3.2) Concentration of product.
(3.3) Link to the next product list node.
The time complexity of the searching and accessing any species? data would be O(mn), while in case if the reactants and products are maintained as arrays it would be O(n?3). Other data structures, which are used in the simulations, are dependency graph, priority queue (heap) and indexed array. The dependency graph approach has been modified, instead of maintaining directed graph, undirected graph has been used to facilitate the time and space complexity of the algorithm.
The outcome of the objectives to be achieved would be a better simulator with better efficiency and the flexibility for the larger signal transduction networks and metabolic networks destined to come into the complex interplay for whole cell simulation.

(For the figures see web representation of the poster abstracts)

[1] D. T. GILLESPIE. A General Method for Numerically Simulating the Stochastic Time Evolution of Coupled Chemical Reactions. J. Computational Physics 22:403-434 (1976)
[2] D.T. GILLESPIE. Exact Stochastic Simulation of Coupled Chemical Reactions. 81:2340-2361(1977)
[3] M. TOMITA, et al. E-CELL: Software Environment for Whole-Cell Simulation. Bioinformatics 15(1):72-84 (1999)
[4] M. A. GIBSON. Computational Methods for Stochastic Biological Systems. PhD Thesis. Calif. Inst. Technology (2000)
[5] M. A. Gibson and J. Bruck: Efficient Exact Stochastic Simulation of Chemical Systems with Many Species and Many Channnels. J. Phy. Chem.104,1876-1889(2000)
[6] STODE-Automatic Stochastic Simulation of Systems described by Differential Equations, Bioinfo. & Comp. Biology Group, EML, Heidelberg (Germany)