*Category-driven Algorithm for the Generation of Emulations*

# Summary

An *emulation* is a function from the species of a *source* chemical reaction network (CRN) to those of a *target* CRN such that the concentrations of the corresponding species coincide at all time points if initialized equally.

CAGE is a Matlab script which interacts with the tool ERODE to compute all emulations between two CRNs.

The tool implements a novel algorithm based on a geometric characterization of emulation. It currently supports the continuous-state semantics of chemical reaction networks (CRNs) based on the law of mass action, which generates a system of nonlinear ordinary differential equations (ODEs). However, the theory underlying CAGE is more general, and can be in principle applied to any ODE system with a differentiable drift.

In particular, the tool currently supports:

- CRNs encoded in the simple explicit .crn format described at the bottom of this page;
- CRNs or polynomial ODEs encode in the ERODE format (.ode). In this case, the Matlab script is automatically generated within ERODE.

Publications:

- Luca Cardelli, Mirco Tribastone, Max Tschaikowski, and Andrea Vandin, Comparing Chemical Reaction Networks: A Categorical and Algorithmic Perspective, submitted to the Special Issue on Formal Verification and Static Analysis of Molecular Devices and Biological Systems of TCS.
- Luca Cardelli, Mirco Tribastone, Max Tschaikowski, and Andrea Vandin, Comparing Chemical Reaction Networks: A Categorical and Algorithmic Perspective, 35th Annual ACM/IEEE Symposium on Logic In Computer Science (LICS’16).

- Luca Cardelli, Mirco Tribastone, Max Tschaikowski, Andrea Vandin, ERODE: A Tool for the Evaluation and Reduction of Ordinary Differential Equations, 23rd Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS’17).
- Luca Cardelli, Mirco Tribastone, Max Tschaikowski, and Andrea Vandin, Efficient Syntax-driven Lumping of Differential Equations, 22nd International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS’16).
- Luca Cardelli, Mirco Tribastone, Max Tschaikowski, and Andrea Vandin,, Symbolic Computation of Differential Equivalences, 43rd Annual Symposium on Principles of Programming Languages (POPL’16).
- Luca Cardelli, Mirco Tribastone, Max Tschaikowski, and Andrea Vandin, Forward and Backward Bisimulations for Chemical Reaction Networks, 26th International Conference on Concurrency Theory (CONCUR’15).

# Download and Installation

A first prototype of our tool is available here.

CAGE does not require any installation process for machines running MATLAB_R2015 or superior. It is sufficient to add the absolute path of the jar file provided in the archive to MATLAB’s static java classpath as described here. In short:

- Type ‘prefdir’ in MATLAB’s console
- Navigate to the obtained path, and open (or create) the file ‘javaclasspath.txt’
- Add to the file a new line with the absolute path of the provided jar file

Optionally, ERODE can be installed as explained here.

# Usage

The tool accompanies:

- The paper recently published at LICS’16: Comparing Chemical Reaction Networks: A Categorical and Algorithmic Perspective;
- Its extension, Comparing Chemical Reaction Networks: A Categorical and Algorithmic Perspective, submitted to the Special Issue on Formal Verification and Static Analysis of Molecular Devices and Biological Systems of TCS.

For the sake of reproducibility, CAGE comes with the models discussed in the two papers:

- Those discussed in the LICS paper and in Section 5.2 of its extension are stored in the folder “TCS_SASB\InfluenceNetworks\AMZoo\CRNNetworks”;
- Those discussed in Section 5.1 of the extended paper are stored in the folder “TCS_SASB\InfluenceNetworks\RandomInfluenceNetworks”;
- Those discussed in Section 5.3 of the extended paper are stored in the folder “TCS_SASB\InfluenceNetworks\BNG”.

Emulations between two CRNs of **point 1** can be computed by just opening the MATLAB file “get_all_bdes.m”, and decommenting the corresponding commands, as documented in the file. All CRNs stored in files with prefix “simp” have been encoded in a simplified but equivalent CRN, as discussed here.

Emulations between CRNs of **points 2 and 3** can be computed by just running the ad-hoc MATLAB files provided in the corresponding folders, automatically generated within ERODE. In particular, they have been generated using the ERODE command:

exportCAGEScript(fileOut="script.m",compBound=0,print=true, unionModel="unionOfSourceAndTarget.ode")

where:

- fileOut specifies the Matlab file to be created;
- compBound specifies if an heuristic variant of the algorithm should be used (if assigning a positive value). It might be used to generate a subset of all emulations for models that are too large to be handled;
- print specifies if debug information should be printed;
- unionModel is an optional parameter used to store the file containing the union of the source and target CRN. If the parameter is provided, then the current ERODE file is considered as the source CRN, and all emulations from the source to the target CRN are computed. If the parameter is not specified, then CAGE will compute all backward differential equivalences within the current model.

The folder TCS_SASB provided in the archive is actually an ERODE project that can be imported in ERODE as described here.

The CRNs of point 2 have been simplified as discussed here.

## Example: computing all emulations from GW’ to AM

% GW' and union (GW',AM) % Decomment this to calculate emulations from GW' to AM n = javaMethod('loadCRN', crnreducer, 'CRNNetworks/gw-p.crn'); H = javaMethod('computeBB', crnreducer, ones(1,n))'; A = javaMethod('computeJacobian', crnreducer, H); crnunion = 'CRNNetworks/gw-p_and_am.crn';

GW’ consists of 12 species: y0, y1, y2, q0, q1, q2, r0, r1, r2, z0, z1, z2, while AM consists of 3 species: x0, x1, x2.

As depicted in the output given below, there exist two emulations from GW’ to AM. The former relates

- y0, q0, z2 and r2 to x0;
- z0, y2, q2 and r0 to x2;
- y1, q1, z1 and r1 to x1.

Instead, the second emulation relates

- y0, q0, z2 and r2 to x2;
- z0, y2, q2 and r0 to x0;
- y1, q1, z1 and r1 to x1.

====== Emulation 1 ======================= The partition has 3 blocks out of 15 species: Block 1, Size: 5 0-y0 4-q0 8-z2 11-r2 12-x0 Block 2, Size: 5 1-z0 3-y2 6-q2 9-r0 13-x2 Block 3, Size: 5 2-y1 5-q1 7-z1 10-r1 14-x1 =========================================== ====== Emulation 2 ======================= The partition has 3 blocks out of 15 species: Block 1, Size: 5 0-y0 4-q0 8-z2 11-r2 13-x2 Block 2, Size: 5 1-z0 3-y2 6-q2 9-r0 12-x0 Block 3, Size: 5 2-y1 5-q1 7-z1 10-r1 14-x1 ===========================================

As shown in the above output, CAGE prints emulations in form of a *block* per species in the target CRN. Each block contains a species of the target CRN (xi), together with all species of the source CRN mapped to it.

## Notes on supported input file formats: .crn format

CAGE currently supports an explicit .crn format for representing chemical reaction networks. The following is a commented example of a simple .crn file with 5 species and 4 reactions:

begin CRN #The optional list of parameters begin parameters a 2.0 b 3.0 end parameters #The mandatory list of reactions in form: "reagents -> products , rate" # where "rate" can be any arithmetic expression, possibly using the parameters or numbers begin reactions xA + xC -> xC + xE , a xB + xC -> xC + xE , a xC -> xA , b xD -> xB , b end reactions #The optional list of initial concentration of each species. Non listed species have assigned 0 as #initial concentration. begin initialConcentrations xA 1.0 xB 1.0 xC 1.0 xD 1.0 xE 1.0 end initialConcentrations end CRN

## About

For suggestions, remarks, bugs or requests please do not hesitate to contact any of us.

- luca@microsoft.com
- mirco.tribastone@imtlucca.it
- max.tschaikowski@imtlucca.it
- andrea.vandin@imtlucca.it