Bioinformatics Second Edition Stochastic Modelling Praise for the First Edition “…well suited as an in-depth introduction into stochastic chemical simulation, S both for self-study or as a course text…” t o for Systems Biology —Biomedical Engineering Online, December 2006 c h Since the first edition of Stochastic Modelling for Systems Biology, there have a been many interesting developments in the use of “likelihood-free” methods s t of Bayesian inference for complex stochastic models. Re-written to reflect this i SECOND EDITION c modern perspective, this second edition covers everything necessary for a good M appreciation of stochastic kinetic modelling of biological networks in the systems biology context. o d Keeping with the spirit of the first edition, all of the new theory is presented in a e very informal and intuitive manner, keeping the text as accessible as possible to l l the widest possible readership. i n g New in the Second Edition f • All examples have been updated to Systems Biology Markup Language o Level 3 r • All code relating to simulation, analysis, and inference for stochastic kinetic S y models has been rewritten and restructured in a more modular way s • An ancillary website provides links, resources, errata, and up-to-date t e information on installation and use of the associated R package m • More background material on the theory of Markov processes and s stochastic differential equations, providing more substance for B mathematically inclined readers i • Discussion of some of the more advanced concepts relating to stochastic o kinetic models, such as random time change representations, Kolmogorov l o equations, Fokker–Planck equations and the linear noise approximation g • Simple modelling of “extrinsic” and “intrinsic” noise y An effective introduction to the area of stochastic modelling in computational systems biology, this new edition adds additional mathematical detail and computational methods which will provide a stronger foundation for the W development of more advanced courses in stochastic biological modelling. i l k i n s o n Darren J. Wilkinson K11715 K11715_Cover.indd 1 10/7/11 8:55 AM Stochastic Modelling for Systems Biology SECOND EDITION K11715_FM.indd 1 10/3/11 10:33 AM CHAPMAN & HALL/CRC Mathematical and Computational Biology Series Aims and scope: This series aims to capture new developments and summarize what is known over the entire spectrum of mathematical and computational biology and medicine. It seeks to encourage the integration of mathematical, statistical, and computational methods into biology by publishing a broad range of textbooks, reference works, and handbooks. The titles included in the series are meant to appeal to students, researchers, and professionals in the mathematical, statistical and computational sciences, fundamental biology and bioengineering, as well as interdisciplinary researchers involved in the field. The inclusion of concrete examples and applications, and programming techniques and examples, is highly encouraged. Series Editors N. F. Britton Department of Mathematical Sciences University of Bath Xihong Lin Department of Biostatistics Harvard University Hershel M. Safer School of Computer Science Tel Aviv University Maria Victoria Schneider European Bioinformatics Institute Mona Singh Department of Computer Science Princeton University Anna Tramontano Department of Biochemical Sciences University of Rome La Sapienza Proposals for the series should be submitted to one of the series editors above or directly to: CRC Press, Taylor & Francis Group 4th, Floor, Albert House 1-4 Singer Street London EC2A 4BQ UK K11715_FM.indd 2 10/3/11 10:33 AM Published Titles Algorithms in Bioinformatics: A Practical Exactly Solvable Models of Biological Introduction Invasion Wing-Kin Sung Sergei V. Petrovskii and Bai-Lian Li Bioinformatics: A Practical Approach Gene Expression Studies Using Shui Qing Ye Affymetrix Microarrays Hinrich Göhlmann and Willem Talloen Biological Computation Ehud Lamm and Ron Unger Glycome Informatics: Methods and Applications Biological Sequence Analysis Using Kiyoko F. Aoki-Kinoshita the SeqAn C++ Library Andreas Gogol-Döring and Knut Reinert Handbook of Hidden Markov Models in Bioinformatics Cancer Modelling and Simulation Martin Gollery Luigi Preziosi Introduction to Bioinformatics Cancer Systems Biology Anna Tramontano Edwin Wang Introduction to Bio-Ontologies Cell Mechanics: From Single Scale- Peter N. Robinson and Sebastian Bauer Based Models to Multiscale Modeling Arnaud Chauvière, Luigi Preziosi, Introduction to Computational and Claude Verdier Proteomics Golan Yona Clustering in Bioinformatics and Drug Discovery Introduction to Proteins: Structure, John D. MacCuish and Norah E. MacCuish Function, and Motion Amit Kessel and Nir Ben-Tal Combinatorial Pattern Matching Algorithms in Computational Biology An Introduction to Systems Biology: Using Perl and R Design Principles of Biological Circuits Gabriel Valiente Uri Alon Computational Biology: A Statistical Kinetic Modelling in Systems Biology Mechanics Perspective Oleg Demin and Igor Goryanin Ralf Blossey Knowledge Discovery in Proteomics Computational Hydrodynamics of Igor Jurisica and Dennis Wigle Capsules and Biological Cells Meta-analysis and Combining C. Pozrikidis Information in Genetics and Genomics Computational Neuroscience: Rudy Guerra and Darlene R. Goldstein A Comprehensive Approach Methods in Medical Informatics: Jianfeng Feng Fundamentals of Healthcare Data Analysis Tools for DNA Microarrays Programming in Perl, Python, and Ruby Sorin Draghici Jules J. Berman Differential Equations and Mathematical Modeling and Simulation of Capsules Biology, Second Edition and Biological Cells D.S. Jones, M.J. Plank, and B.D. Sleeman C. Pozrikidis Dynamics of Biological Systems Niche Modeling: Predictions from Michael Small Statistical Distributions David Stockwell Engineering Genetic Circuits Chris J. Myers K11715_FM.indd 3 10/3/11 10:33 AM Published Titles (continued) Normal Mode Analysis: Theory and Statistics and Data Analysis for Applications to Biological and Chemical Microarrays Using R and Bioconductor, Systems Second Edition Qiang Cui and Ivet Bahar Sorin Dra˘ghici Optimal Control Applied to Biological Stochastic Modelling for Systems Models Biology, Second Edition Suzanne Lenhart and John T. Workman Darren J. Wilkinson Pattern Discovery in Bioinformatics: Structural Bioinformatics: An Algorithmic Theory & Algorithms Approach Laxmi Parida Forbes J. Burkowski Python for Bioinformatics The Ten Most Wanted Solutions in Sebastian Bassi Protein Bioinformatics Anna Tramontano Spatial Ecology Stephen Cantrell, Chris Cosner, and Shigui Ruan Spatiotemporal Patterns in Ecology and Epidemiology: Theory, Models, and Simulation Horst Malchow, Sergei V. Petrovskii, and Ezio Venturino K11715_FM.indd 4 10/3/11 10:33 AM Stochastic Modelling for Systems Biology SECOND EDITION Darren J. Wilkinson K11715_FM.indd 5 10/3/11 10:33 AM CRC Press Taylor & Francis Group 6000 Broken Sound Parkway NW, Suite 300 Boca Raton, FL 33487-2742 © 2012 by Taylor & Francis Group, LLC CRC Press is an imprint of Taylor & Francis Group, an Informa business No claim to original U.S. Government works Version Date: 2011926 International Standard Book Number-13: 978-1-4398-3776-4 (eBook - PDF) This book contains information obtained from authentic and highly regarded sources. Reasonable efforts have been made to publish reliable data and information, but the author and publisher cannot assume responsibility for the validity of all materials or the consequences of their use. The authors and publishers have attempted to trace the copyright holders of all material reproduced in this publication and apologize to copyright holders if permission to publish in this form has not been obtained. If any copyright material has not been acknowledged please write and let us know so we may rectify in any future reprint. Except as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproduced, transmit- ted, or utilized in any form by any electronic, mechanical, or other means, now known or hereafter invented, including photocopying, microfilming, and recording, or in any information storage or retrieval system, without written permission from the publishers. For permission to photocopy or use material electronically from this work, please access www.copyright. com (http://www.copyright.com/) or contact the Copyright Clearance Center, Inc. (CCC), 222 Rosewood Drive, Danvers, MA 01923, 978-750-8400. CCC is a not-for-profit organization that provides licenses and registration for a variety of users. For organizations that have been granted a photocopy license by the CCC, a separate system of payment has been arranged. Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used only for identification and explanation without intent to infringe. Visit the Taylor & Francis Web site at http://www.taylorandfrancis.com and the CRC Press Web site at http://www.crcpress.com Contents Listoftables xi Listoffigures xiii Authorbiography xix Acknowledgements xxi Prefacetothesecondedition xxiii Prefacetothefirstedition xxv I Modellingandnetworks 1 1 Introductiontobiologicalmodelling 3 1.1 Whatismodelling? 3 1.2 Aimsofmodelling 4 1.3 Whyisstochasticmodellingnecessary? 4 1.4 Chemicalreactions 9 1.5 Modellinggeneticandbiochemicalnetworks 10 1.6 Modellinghigher-levelsystems 18 1.7 Exercises 20 1.8 Furtherreading 20 2 Representationofbiochemicalnetworks 21 2.1 Coupledchemicalreactions 21 2.2 Graphicalrepresentations 21 2.3 Petrinets 24 2.4 Stochasticprocessalgebras 34 2.5 SystemsBiologyMarkupLanguage(SBML) 36 2.6 SBML-shorthand 41 2.7 Exercises 47 2.8 Furtherreading 48 vii viii CONTENTS II Stochasticprocessesandsimulation 49 3 Probabilitymodels 51 3.1 Probability 51 3.2 Discreteprobabilitymodels 62 3.3 Thediscreteuniformdistribution 70 3.4 Thebinomialdistribution 71 3.5 Thegeometricdistribution 72 3.6 ThePoissondistribution 74 3.7 Continuousprobabilitymodels 77 3.8 Theuniformdistribution 82 3.9 Theexponentialdistribution 85 3.10 Thenormal/Gaussiandistribution 89 3.11 Thegammadistribution 93 3.12 Quantifying“noise” 96 3.13 Exercises 97 3.14 Furtherreading 98 4 Stochasticsimulation 99 4.1 Introduction 99 4.2 MonteCarlointegration 99 4.3 Uniformrandomnumbergeneration 100 4.4 Transformationmethods 101 4.5 Lookupmethods 106 4.6 Rejectionsamplers 107 4.7 Importanceresampling 110 4.8 ThePoissonprocess 111 4.9 Usingthestatisticalprogramminglanguage,R 112 4.10 Analysisofsimulationoutput 118 4.11 Exercises 120 4.12 Furtherreading 122 5 Markovprocesses 123 5.1 Introduction 123 5.2 FinitediscretetimeMarkovchains 123 5.3 Markovchainswithcontinuousstate-space 130 5.4 Markovchainsincontinuoustime 137 5.5 Diffusionprocesses 152 5.6 Exercises 166 5.7 Furtherreading 168 III Stochasticchemicalkinetics 169 6 Chemicalandbiochemicalkinetics 171 6.1 Classicalcontinuousdeterministicchemicalkinetics 171 CONTENTS ix 6.2 Molecularapproachtokinetics 178 6.3 Mass-actionstochastickinetics 180 6.4 TheGillespiealgorithm 182 6.5 StochasticPetrinets(SPNs) 183 6.6 Structuringstochasticsimulationcodes 186 6.7 Rateconstantconversion 189 6.8 Kolmogorov’sequationsandotheranalyticrepresentations 194 6.9 Softwareforsimulatingstochastickineticnetworks 199 6.10 Exercises 200 6.11 Furtherreading 200 7 Casestudies 203 7.1 Introduction 203 7.2 Dimerisationkinetics 203 7.3 Michaelis–Mentenenzymekinetics 208 7.4 Anauto-regulatorygeneticnetwork 212 7.5 Thelacoperon 217 7.6 Exercises 219 7.7 Furtherreading 220 8 BeyondtheGillespiealgorithm 221 8.1 Introduction 221 8.2 Exactsimulationmethods 221 8.3 Approximatesimulationstrategies 226 8.4 Hybridsimulationstrategies 239 8.5 Exercises 245 8.6 Furtherreading 245 IV Bayesianinference 247 9 BayesianinferenceandMCMC 249 9.1 LikelihoodandBayesianinference 249 9.2 TheGibbssampler 254 9.3 TheMetropolis–Hastingsalgorithm 264 9.4 HybridMCMCschemes 268 9.5 Metropolis–HastingsalgorithmsforBayesianinference 269 9.6 Bayesianinferenceforlatentvariablemodels 270 9.7 AlternativestoMCMC 274 9.8 Exercises 275 9.9 Furtherreading 275 10 Inferenceforstochastickineticmodels 277 10.1 Introduction 277 10.2 Inferencegivencompletedata 278 10.3 Discrete-timeobservationsofthesystemstate 281