Dec 2 – 3, 2020
Le Bois-Marie
Europe/Paris timezone

Tracelet Algebras

Dec 2, 2020, 10:30 AM


Nicolas Behr (Université de Paris, IRIF)


Stochastic rewriting systems evolving over graph-like structures are a versatile modeling paradigm that covers in particular biochemical reaction systems. In fact, to date rewriting-based frameworks such as the Kappa platform [1] are amongst the very few known approaches to faithfully encode the enormous complexity in both molecular structures and reactions exhibited by biochemical reaction systems in living organisms. Since in practice experimental constraints permit to track only very limited information about a given reaction system (typically the concentrations of only a handful of molecules), a fundamental mathematical challenge arises: which types of information are meaningful to derive and computable from a stochastic rewriting system in view of the limited empirical data? Traditionally, the main focus of the mathematical theory of stochastic rewriting theory has been upon the derivation of ODE systems describing the evolution of averages and higher moments of pattern counts (i.e. the concentrations of molecular species). In this talk, we present an alternative approach based upon so-called tracelets [2]. The latter are the precise mathematical encoding of the heuristic notion of pathways in biochemistry. We demonstrate a novel mathematical concept of tracelet algebras and highlight a computational strategy that permits to derive structural, high level insights into the dynamics of pattern counts. In view of the focus of CAP on combinatorial aspects, we will illustrate this mathematical approach with an analysis of planar rooted binary trees in a rewriting-based formulation utilizing the Rémy generator.

[1] Pierre Boutillier et al., ”The Kappa platform for rule-based modeling.”, Bioinformatics 34.13 (2018): pp. 583-592.

[2] Nicolas Behr, ”Tracelets and Tracelet Analysis Of Compositional Rewriting Systems”, Electronic Proceedings in Theoretical Computer Science 323 (2020), pp. 44-71.

Presentation materials