Biological software developped in Serrano's laboratory

SmartCell Simulation Algorithm

SmartCell offers 3 kinds of algorithms to simulate your network, the exact stockastic algorithm, the deterministic algorithm and the approximative algorithm.

The exact stockastic algorithm

The next reaction method

The next reaction method is based on the Gillespie algorithm. It is based on a queue of events with an approximate length of Number of Event * Number of voxels.

The main steps of the algorithm are:

  1. Calculate the probability ai for each event i
  2. For each i, sample a putative reaction time Ti from an exponential distribution with parameter ai, and add it to the queue of events
  3. Pick the event with the lowest T from the queue
  4. Execute the event, recalculate ai, generate a new Ti and add it to the queue of events
  5. Check dependencies and update “dirty” Ts
  6. If the queue is not empty, go to step 3.

The advantage of this method is that the detection of the next event is really fast as it is the first element of the queue, but the time to sort the queue can be really high on a complicated network.

The next subvolume method

The next subvolume method is based on the Elf algorithm. It is based on a queue of voxels with a length of 1 * Number of voxels.

The main steps of the algorithm are:

  1. Calculate the probability ai for each event i
  2. Calculate the probability av for each voxel v, with av = sum of ai of voxel v events
  3. For each voxel v, sample a putative reaction time Tv from an exponential distribution with parameter av, and add it to the queue of voxels
  4. Pick the voxel with the lowest T from the queue
  5. Select one event of voxel v, with a distribution proportional to the ai
  6. Execute the event, recalculate ai, av and Tv and add it to the queue of voxels
  7. Check dependencies and update “dirty” Ts
  8. If the queue is not empty, go to step 4.

The advantage of this method is that the size of the queue will be independant of the complexity of the network and as a consequence the time needed to sort the queue won't depend of the network but only the geometry. Unfortunately, an additional step will be needed in order to detect the next event as the queue will only provide the next voxel the next event will take place.

The hybrid method

The hybrid method is used in order to combine the advantage of the stochastic Next Reaction/Next Subvolume methods and the deterministic ODE method. The reaction related to species with high copy number will be simulated with ODE when the reaction related to species with low copy number will be simulated with stochastic algorithm. This will allow a speed close to the ODE but will give some stochastic results, closer to the biological reality.

The deterministic algorithm

SmartCell is offering an ODE solver in order to have a first idea of the network behavior based on ODE. This method will have the advantage of being really fast in most of the network, but won't present the stochastic behavior of the cell and can even present some wrong result in case of instable steady state of the network.

The approximative algorithm

The tau-leap method

The tau-leap method is an approximative algorithm based on the next reaction method and published by Gillespie in 2001.
The principle is based on:

  • At time t, τ is calculated considering:
    • τ is a small time interval
    • The events that will occur during τ have a small impact on the other events
  • Jump to time t + τ
  • Execution of events that occur during τ
  • Calculation of new probabilities and new τ