27-09-2012, 01:12 PM
Reconfigurable Hardware Acceleration of Exact Stochastic Simulation
[attachment=34600]
ABSTRACT
This thesis explores the use of reconfigurable hardware in modeling chemical
species reacting in a spatially homogeneous environment. The time evolution of
biochemical models is often evaluated using a deterministic approach that uses
differential equations to describe the chemical interactions of the model. However, such
an approach treats species as continuous valued concentrations, is inaccurate for small
species populations, and neglects the stochastic nature of biochemical systems. The
Stochastic Simulation Algorithm (SSA) developed by Gillespie is able to properly
account for these inherent noise fluctuations. This allows the SSA to accurately project
the time evolution of a biochemical model. Unfortunately, the SSA can be
computationally intensive and require a substantial amount of time to complete.
Therefore, it has been proposed that the SSA be implemented on a Field Programmable
Gate Array (FPGA) to improve performance. Employing an FPGA allows parallelism to
be exploited within the SSA providing a speedup over software implementations
executing instructions sequentially. Recent work in this area has focused on
implementing the SSA on an FPGA to simulate specific biochemical models. However,
this requires re-constructing and re-synthesizing the design in order to simulate a new
biochemical system. This work examines the use of a reconfigurable computing platform
to allow an implementation of the SSA on an FPGA to simulate a variety of models.
Introduction
The future of biochemical systems analysis is as promising as it is challenging.
Accurately modeling complex biochemical systems is currently a daunting and time
consuming task. Efforts are underway to develop more efficient tools for modeling these
systems while producing reliable data. Some biochemical systems of interest include the
transcription and translation of DNA during protein synthesis or the growth of a bacterial
infection, as well as many others. By understanding how cells operate and communicate,
we can begin to predict the behavior of the underlying biochemical system. Then
methods can be developed to interrupt and control cellular processes, allowing advances
in the field of gene therapy and medicine.
Biochemical systems, consisting of species reacting in a spatially homogeneous
environment, are often formulated using a deterministic approach. Such an approach
represents species as continuous-valued concentrations and interactions between
chemicals are modeled using ordinary differential equations. A deterministic approach is
effective for modeling many biological systems, although inaccuracies become apparent
for systems with small populations of chemical species and systems affected by noise.
Recent research has shown that noise may play a critical role in many biochemical
systems [1,2]. Therefore a stochastic approach must be used to model noise-affected
systems. Within a stochastic approach, chemical species are represented as discretevalued
populations and interactions between chemicals are represented as random
processes.
Ordinary Differential Equations to the Model
Traditionally, models of chemical species reacting within a spatially
homogeneous environment are devised using a deterministic approach involving ordinary
differential equations. Such an approach treats species populations as continuous valued
concentrations that are a function of time [3]. Through the use of software packages that
include differential equation solvers (i.e. Matlab), a complex biological system can be
modeled using ordinary differential equations (ODEs) and solved in less than a day.
However, the results may not necessarily be accurate. Ordinary differential equation
models ignore the inherent stochastic nature of chemically reacting systems. This hinders
the application of ODEs to systems with small numbers of molecules. In addition, it is
possible for the results of an ODE model to suggest that species concentrations are real
valued or below zero. In actual chemical systems, it makes no sense to have any less
than a whole molecule and it is impossible to have a negative amount of molecules. The
effects of these limitations can be devastating to modeling chemical systems since a
species with a small population can have a significant impact on the trajectory of the
system.
Explanation of Terms
The following terms are crucial to formulating an exact stochastic simulation
algorithm and may require an explanation.
Propensity, a, is associated with the probability that a reaction will occur. It is
based upon the stochastic reaction rate constant and the number of distinct molecular
combinations of the reaction. The stochastic reaction rate constant, c, is defined as the
average probability that a molecular combination from a given reaction will collide and
react in the next infinitesimal time interval. The stochastic reaction rate constant is
directly related to the deterministic reaction rate constant, k. This relationship is altered
for the case when identical reactant molecules collide and react. The equation below
depicts the correlation between the stochastic and deterministic reaction rate constants
where n is the number of identical reactant molecules reacting together [7].
Gillespie’s First Reaction Method
The First Reaction Method was Daniel Gillespie’s first take on the SSA [3]. The
Initialization step of this algorithm creates and loads variables to hold the species
populations, reaction equations, and the current time. Upon the initialization of the
system, the Propensity Calculation step begins and the propensity of each reaction is
calculated. For each reaction during the Putative Time Estimation step, a potential time
is calculated to determine when that reaction will occur in the future. Each potential time
is found by generating an exponential random number and dividing it by the propensity
of the reaction. The Reaction Selection step searches the list of putative times from each
reaction; the reaction with the earliest time is labeled as the next reaction. The Reaction
Execution step adds the putative time of the selected reaction to the current time and
updates the species populations by decrementing the values of the reactant populations
and incrementing the values of the product populations. This process is repeated until the
desired end time is reached. See figure 2.1 to find pseudo code for Gillespie’s First
Reaction Method. Gillespie’s First Reaction Method is an effective way to accurately
model biochemical systems. However generating an exponential random number for
each reaction during each iteration severely limits the method’s performance.
[attachment=34600]
ABSTRACT
This thesis explores the use of reconfigurable hardware in modeling chemical
species reacting in a spatially homogeneous environment. The time evolution of
biochemical models is often evaluated using a deterministic approach that uses
differential equations to describe the chemical interactions of the model. However, such
an approach treats species as continuous valued concentrations, is inaccurate for small
species populations, and neglects the stochastic nature of biochemical systems. The
Stochastic Simulation Algorithm (SSA) developed by Gillespie is able to properly
account for these inherent noise fluctuations. This allows the SSA to accurately project
the time evolution of a biochemical model. Unfortunately, the SSA can be
computationally intensive and require a substantial amount of time to complete.
Therefore, it has been proposed that the SSA be implemented on a Field Programmable
Gate Array (FPGA) to improve performance. Employing an FPGA allows parallelism to
be exploited within the SSA providing a speedup over software implementations
executing instructions sequentially. Recent work in this area has focused on
implementing the SSA on an FPGA to simulate specific biochemical models. However,
this requires re-constructing and re-synthesizing the design in order to simulate a new
biochemical system. This work examines the use of a reconfigurable computing platform
to allow an implementation of the SSA on an FPGA to simulate a variety of models.
Introduction
The future of biochemical systems analysis is as promising as it is challenging.
Accurately modeling complex biochemical systems is currently a daunting and time
consuming task. Efforts are underway to develop more efficient tools for modeling these
systems while producing reliable data. Some biochemical systems of interest include the
transcription and translation of DNA during protein synthesis or the growth of a bacterial
infection, as well as many others. By understanding how cells operate and communicate,
we can begin to predict the behavior of the underlying biochemical system. Then
methods can be developed to interrupt and control cellular processes, allowing advances
in the field of gene therapy and medicine.
Biochemical systems, consisting of species reacting in a spatially homogeneous
environment, are often formulated using a deterministic approach. Such an approach
represents species as continuous-valued concentrations and interactions between
chemicals are modeled using ordinary differential equations. A deterministic approach is
effective for modeling many biological systems, although inaccuracies become apparent
for systems with small populations of chemical species and systems affected by noise.
Recent research has shown that noise may play a critical role in many biochemical
systems [1,2]. Therefore a stochastic approach must be used to model noise-affected
systems. Within a stochastic approach, chemical species are represented as discretevalued
populations and interactions between chemicals are represented as random
processes.
Ordinary Differential Equations to the Model
Traditionally, models of chemical species reacting within a spatially
homogeneous environment are devised using a deterministic approach involving ordinary
differential equations. Such an approach treats species populations as continuous valued
concentrations that are a function of time [3]. Through the use of software packages that
include differential equation solvers (i.e. Matlab), a complex biological system can be
modeled using ordinary differential equations (ODEs) and solved in less than a day.
However, the results may not necessarily be accurate. Ordinary differential equation
models ignore the inherent stochastic nature of chemically reacting systems. This hinders
the application of ODEs to systems with small numbers of molecules. In addition, it is
possible for the results of an ODE model to suggest that species concentrations are real
valued or below zero. In actual chemical systems, it makes no sense to have any less
than a whole molecule and it is impossible to have a negative amount of molecules. The
effects of these limitations can be devastating to modeling chemical systems since a
species with a small population can have a significant impact on the trajectory of the
system.
Explanation of Terms
The following terms are crucial to formulating an exact stochastic simulation
algorithm and may require an explanation.
Propensity, a, is associated with the probability that a reaction will occur. It is
based upon the stochastic reaction rate constant and the number of distinct molecular
combinations of the reaction. The stochastic reaction rate constant, c, is defined as the
average probability that a molecular combination from a given reaction will collide and
react in the next infinitesimal time interval. The stochastic reaction rate constant is
directly related to the deterministic reaction rate constant, k. This relationship is altered
for the case when identical reactant molecules collide and react. The equation below
depicts the correlation between the stochastic and deterministic reaction rate constants
where n is the number of identical reactant molecules reacting together [7].
Gillespie’s First Reaction Method
The First Reaction Method was Daniel Gillespie’s first take on the SSA [3]. The
Initialization step of this algorithm creates and loads variables to hold the species
populations, reaction equations, and the current time. Upon the initialization of the
system, the Propensity Calculation step begins and the propensity of each reaction is
calculated. For each reaction during the Putative Time Estimation step, a potential time
is calculated to determine when that reaction will occur in the future. Each potential time
is found by generating an exponential random number and dividing it by the propensity
of the reaction. The Reaction Selection step searches the list of putative times from each
reaction; the reaction with the earliest time is labeled as the next reaction. The Reaction
Execution step adds the putative time of the selected reaction to the current time and
updates the species populations by decrementing the values of the reactant populations
and incrementing the values of the product populations. This process is repeated until the
desired end time is reached. See figure 2.1 to find pseudo code for Gillespie’s First
Reaction Method. Gillespie’s First Reaction Method is an effective way to accurately
model biochemical systems. However generating an exponential random number for
each reaction during each iteration severely limits the method’s performance.