Stochastic graph rewriting and (executable) knowledge representation for molecular biology
Jean Krivine (CNRS and Université Paris Diderot)
In the late 90s Molecular Biology (the science of collating data about molecular interactions) was believed to be shortly giving way to Systems Biology (the science of integrating biological observations into comprehensive models of the cell). Nearing 2020, the race between data collation and data integration is still largely lead by Molecular Biologists . In this context, computer scientitsts, from the Programming Language community, have proposed various flavors of rewriting formalisms to equip Molecular Biology with an executable representation .
If multiset rewriting  is appealing to the biolgists because of its proximity to chemical reaction networks, and the ease of compilation into Ordinary Differential Equations, its use is limited by the combinatorial explosion that is characteristic of protein-protein interaction networks.
Recently, graph rewriting formalisms also known as Rule-Based modeling, has emerged as a pertinent framework to represent molecular dynamics of the cell. In this setting, a cell state is represented as a labelled graph whose vertices denote proteins and edges typically denote non-covalent bonds [4,5].
This lecture will focus on graph rewriting as a modeling framework for Systems Biology. We will focus on one particular tool suite called Kappa , which offers a stochastic simulator and static analysis tools based on abstract interpretation.
The course has a large interactive component as we learn how to write a rule-based model in Kappa.
Outline of the lecture
- Stochastic graph rewriting: Basics of Gillespie’s algorirhtm. Pattern matching and rule activity: fully dynamic algorithm.
- A simple ABC model: Building a pseudo biological model. Simulation, perturbation and observables.
- Static analysis: Reachability issue. Abstract interpretation.
- Advanced modeling: DNA repair. A real biological problem. Choice of encoding. Results.
- Systems biology. Krivine J, SIGLOG News 4(3): 43-61 (2017)
- Executable Cell Biology. Fisher J and Henzinger TA. Nature Bio. 25(11): 1239-49 (2007)
- BIOCHAM: an environment for modeling biological systems and formalizing experimental knowledge. Calzone L et al. Bioinformatics 22(14): 1805-07 (2006)
- The Kappa platform for rule-based modeling. Boutillier et al. Bioinformatics 34(13): 583-592 (2018)
- Efficient modeling, simulation and coarse-graining of biological complexity with NFsim. Sneddon et al. Nature Methods 8(2):177-83. (2011)