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.

This work describes and formalises 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.

This is joint work with Vincent Danos, Jérôme Feret, Walter Fontana, Russ Harmer, Jean Krivine, Chris Thompson-Walsh and Glynn Winskel.