Abstract

Abstract: The so-called ‘exact’ Gillespie stochastic simulation algorithms have spawned a number of successors which aim to speed up the computationally intense process of stochastic simulation of chemically reacting systems. While some of these successors achieve a speed-up by compromising exactness, usually via judicious approximation, others are both faster and remain exact. In this latter vein, the Gibson-Bruck algorithm has apparent market-leading asymptotic performance and is the benchmark by which contenders are measured. In fact, it has been found that it’s theoretical performance may not be realised in practical systems which do not approach asymptotic dimensions and that its overhead may allow it to be beaten by simpler algorithms. More surprisingly, in the stochastic simulation of some complex hierarchical systems whose interactions are combinatorial in nature, the Gibson-Bruck algorithm also loses its theoretical edge due to one of its assumptions about chemical systems not holding.

We thus present an algorithm which gives an improvement of performance over the Gibson-Bruck algorithm equivalent to O(n) vs. O(n log n) when used to simulate the complex interactions of populations of cells containing chemistry. We further show that the idea behind the algorithm can be usefully exploited for the simulation of practical, non-hierarchical chemical systems. Finally, we present a promising new technique for the analysis of stochastic simulations which allows the creation of a space of phenotype, thus allowing the comparison of models and algorithms.

Biography: Sean Sedwards studied electronics at University College London and later set up a company to design and manufacture hi-fi amplifiers. Recently, seeking a change of career, he returned to academia. At Oxford Brookes University he attained first class honours in computer science and won the John Birch award for the most outstanding graduate. Beyond his current research in systems biology he has a broad range of scientific interests and recently worked on chaotic artificial neurons.