The explosion of data available in life sciences is fueling an increasing demand for expressive models and computational methods. Graph transformation is a model for dynamic systems with a large variety of applications. We introduce a novel method of the graph transformation model construction, combining generative and dynamical viewpoints to give a fully automated data-driven model inference method. The method takes the input dynamical properties, given as a "snapshot" of the dynamics encoded by explicit transitions, and constructs a compatible model. The obtained model is guaranteed to be minimal, thus framing the approach as model compression (from a set of transitions into a set of rules). The compression is permissive to a lossy case, where the constructed model is allowed to exhibit behavior outside of the input transitions, thus suggesting a completion of the input dynamics. The task of graph transformation model inference is naturally highly challenging due to the combinatorics involved. We tackle the exponential explosion by proposing a heuristically minimal translation of the task into a well-established problem, set cover, for which highly optimized solutions exist. We further showcase how our results relate to Kolmogorov complexity expressed in terms of graph transformation.

MOTIVATION: The design of enzymes is as challenging as it is consequential for making chemical synthesis in medical and industrial applications more efficient, cost-effective and environmentally friendly. While several aspects of this complex problem are computationally assisted, the drafting of catalytic mechanisms, i.e. the specification of the chemical steps-and hence intermediate states-that the enzyme is meant to implement, is largely left to human expertise. The ability to capture specific chemistries of multistep catalysis in a fashion that enables its computational construction and design is therefore highly desirable and would equally impact the elucidation of existing enzymatic reactions whose mechanisms are unknown. RESULTS: We use the mathematical framework of graph transformation to express the distinction between rules and reactions in chemistry. We derive about 1000 rules for amino acid side chain chemistry from the M-CSA database, a curated repository of enzymatic mechanisms. Using graph transformation, we are able to propose hundreds of hypothetical catalytic mechanisms for a large number of unrelated reactions in the Rhea database. We analyze these mechanisms to find that they combine in chemically sound fashion individual steps from a variety of known multistep mechanisms, showing that plausible novel mechanisms for catalysis can be constructed computationally. AVAILABILITY AND IMPLEMENTATION: The source code of the initial prototype of our approach is available at https://github.com/Nojgaard/mechsearch. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Models based on rules that express local and heterogeneous mechanisms of stochastic interactions between structured agents are an important tool for investigating the dynamical behavior of complex systems, especially in molecular biology. Given a simulated trace of events, the challenge is to construct a causal diagram that explains how a phenomenon of interest occurred. Counterfactual analysis can provide distinctive insights, but its standard definition is not applicable in rule-based models because they are not readily expressible in terms of structural equations. We provide a semantics of counterfactual statements that addresses this challenge by sampling counterfactual trajectories that are probabilistically as close to the factual trace as a given intervention permits them to be. We then show how counterfactual dependencies give rise to explanations in terms of relations of enablement and prevention between events.

Motivation: We present an overview of the Kappa platform, an integrated suite of analysis and visualization techniques for building and interactively exploring rule-based models. The main components of the platform are the Kappa Simulator, the Kappa Static Analyzer and the Kappa Story Extractor. In addition to these components, we describe the Kappa User Interface, which includes a range of interactive visualization tools for rule-based models needed to make sense of the complexity of biological systems. We argue that, in this approach, modeling is akin to programming and can likewise benefit from an integrated development environment. Our platform is a step in this direction. Results: We discuss details about the computation and rendering of static, dynamic, and causal views of a model, which include the contact map (CM), snaphots at different resolutions, the dynamic influence network (DIN) and causal compression. We provide use cases illustrating how these concepts generate insight. Specifically, we show how the CM and snapshots provide information about systems capable of polymerization, such as Wnt signaling. A well-understood model of the KaiABC oscillator, translated into Kappa from the literature, is deployed to demonstrate the DIN and its use in understanding systems dynamics. Finally, we discuss how pathways might be discovered or recovered from a rule-based model by means of causal compression, as exemplified for early events in EGF signaling. Availability and implementation: The Kappa platform is available via the project website at kappalanguage.org. All components of the platform are open source and freely available through the authors' code repositories.

We introduce the Dynamic Influence Network (DIN), a novel visual analytics technique for representing and analyzing rule-based models of protein-protein interaction networks. Rule-based modeling has proved instrumental in developing biological models that are concise, comprehensible, easily extensible, and that mitigate the combinatorial complexity of multi-state and multi-component biological molecules. Our technique visualizes the dynamics of these rules as they evolve over time. Using the data produced by KaSim, an open source stochastic simulator of rule-based models written in the Kappa language, DINs provide a node-link diagram that represents the influence that each rule has on the other rules. That is, rather than representing individual biological components or types, we instead represent the rules about them (as nodes) and the current influence of these rules (as links). Using our interactive DIN-Viz software tool, researchers are able to query this dynamic network to find meaningful patterns about biological processes, and to identify salient aspects of complex rule-based models. To evaluate the effectiveness of our approach, we investigate a simulation of a circadian clock model that illustrates the oscillatory behavior of the KaiC protein phosphorylation cycle.

In this paper, we introduce a novel way of constructing concise causal histories (pathways) to represent how specified structures are formed during simulation of systems represented by rule-based models. This is founded on a new, clean, graph-based semantics introduced in the first part of this paper for Kappa, a rule-based modelling language that has emerged as a natural description of protein-protein interactions in molecular biology [Bachman 2011]. The semantics is capable of capturing the whole of Kappa, including subtle side-effects on deletion of structure, and its structured presentation provides the basis for the translation of techniques to other models. In particular, we give a notion of trajectory compression, which restricts a trace culminating in the production of a given structure to the actions necessary for the structure to occur. This is central to the reconstruction of biochemical pathways due to the failure of traditional techniques to provide adequately concise causal histories, and we expect it to be applicable in a range of other modelling situations.

Rule-based approaches (as in our own Kappa, or the BNG language, or many other propositions allowing the consideration of "reaction classes'') offer new and more powerful ways to capture the combinatorial interactions that are typical of molecular biological systems. They afford relatively compact and faithful descriptions of cellular interaction networks despite the combination of two broad types of interaction: the formation of complexes (a biological term for the ubiquitous non-covalent binding of bio-molecules), and the chemical modifications of macromolecules (aka post-translational modifications). However, all is not perfect. This same combinatorial explosion that pervades biological systems also seems to prevent the simulation of molecular networks using systems of differential equations. In all but the simplest cases the generation (and even more the integration) of the explicit system of differential equations which is canonically associated to a rule set is unfeasible. So there seems to be a price to pay for this increase in clarity and precision of the description, namely that one can only execute such rule-based systems using their stochastic semantics as continuous time Markov chains, which means a slower if more accurate simulation. In this paper, we take a fresh look at this question, and, using techniques from the abstract interpretation framework, we construct a reduction method which generates (typically) far smaller systems of differential equations than the concrete/canonical one. We show that the abstract/reduced differential system has solutions which are linear combinations of the canonical ones. Importantly, our method: 1) does not require the concrete system to be explicitly computed, so it is intensional, 2) nor does it rely on the choice of a specific set of rate constants for the system to be reduced, so it is symbolic, and 3) achieves good compression when tested on rule-based models of significant size, so it is also realistic.

Models will play a central role in the representation, storage, manipulation, and communication of knowledge in systems biology. Models capable of fulfilling such a role will likely differ from the all familiar styles deployed with great success in the physical sciences. Molecular systems at the basis of cellular decision processes are concurrent and combinatorial. Their behavior is as much constrained by relationships of causality between molecular interactions as it is by chemical kinetics. Understanding how such systems give rise to coherent behavior and designing effective interventions to fight disease will require a notion of model that is akin to the concept of program in computer science. I will discuss recent progress in implementing a platform and tools for formal analysis that bring us closer to this vision. Protein interactions are represented by means of rules expressed in a formal language that captures a very simple, yet effective and biologically meaningful level of abstraction. Models, then, are collections of rules operating on an initial set of agents, in complete analogy to rules of organic chemical reactions. I will describe tools for analyzing and navigating rule collections as well as exploring their dynamics. We draw on concepts familiar to computer science, especially event structures, and adapt them to biological needs with the goal of formalizing the notion of "pathway". The challenges are many, but a road map for the future is discernible. Computer science will play a central role in providing an additional foundational layer, both theoretical and practical, that neither physics nor chemistry can offer on their own in the future definition of the biological sciences.

Metabolic rate, heart rate, lifespan, and many other physiological properties vary with body mass in systematic and interrelated ways. Present empirical data suggest that these scaling relationships take the form of power laws with exponents that are simple multiples of one quarter. A compelling explanation of this observation was put forward a decade ago by West, Brown, and Enquist (WBE). Their framework elucidates the link between metabolic rate and body mass by focusing on the dynamics and structure of resource distribution networks-the cardiovascular system in the case of mammals. Within this framework the WBE model is based on eight assumptions from which it derives the well-known observed scaling exponent of 3/4. In this paper we clarify that this result only holds in the limit of infinite network size (body mass) and that the actual exponent predicted by the model depends on the sizes of the organisms being studied. Failure to clarify and to explore the nature of this approximation has led to debates about the WBE model that were at cross purposes. We compute analytical expressions for the finite-size corrections to the 3/4 exponent, resulting in a spectrum of scaling exponents as a function of absolute network size. When accounting for these corrections over a size range spanning the eight orders of magnitude observed in mammals, the WBE model predicts a scaling exponent of 0.81, seemingly at odds with data. We then proceed to study the sensitivity of the scaling exponent with respect to variations in several assumptions that underlie the WBE model, always in the context of finite-size corrections. Here too, the trends we derive from the model seem at odds with trends detectable in empirical data. Our work illustrates the utility of the WBE framework in reasoning about allometric scaling, while at the same time suggesting that the current canonical model may need amendments to bring its predictions fully in line with available datasets.

The success of Artificial Life (ALife) depends on whether it will help solve the conceptual problems of biology. Biology may be viewed as the science of the transformation of organizations. Yet biology lacks a theory of organization. We use this as an example of the challenge that ALife must meet.