Working group: "Computational Biology"

2012, the 28th of February

Jonathan Hayman

Title: Graphs, rewriting and causality in rule-based models.


The Kappa calculus defines how a graph, representing a system of linked agents, can be modified by rules that specify which changes may occur at places that match specific local patterns. Though the calculus has a wide degree of applicability, it has emerged as a natural description of protein-protein interaction systems and pathways in molecular biology.

In my talk, I'll describe an intuitive graph-based semantics for Kappa that correctly handles subtle side-effects upon deletion of elements of the graph. Central to the work is the use of spans of morphisms to characterize rewriting in the style of single-pushout based rewriting.

The sequential application of rules gives rise to trajectories, some of which may lead to the production of particular patterns of interest. It is then natural to seek to account for their production with a causal history (a pathway). We introduce several notions of trajectory compression, providing a foundation for techniques to reconstruct causal histories at increasing levels of conciseness.

Throughout the talk, I'll try to highlight and justify some of the more subtle definitions, and I hope that it will lead on to discussion of future work and potential applications. Time (and interest!) permitting, I may also mention how a new general framework for describing single-pushout rewriting with side effects, developed with the intention of clarifying some of the proofs, might be applied.