`FIREFRONT/AVATAR` are two methods to quantify attractors reachable from a given initial condition, i.e. to determine their reachability probability, over asynchronous discrete dynamics.
`FIREFRONT` is a quasi-exact method, simultaneously following all (concurrent) trajectories while propagating state probabilities.
`AVATAR` is a modified Monte Carlo algorithm in order to handle strongly connected components. It avoids revisiting the same states, due to transient and terminal cycles, by rewiring the state transition graph.

Input files can be automatically generated through the export functionality of the beta version of the GINsim modelling and simulation tool.

### Supplementary Material

You can find additional details on the corresponding Supplementary Material here.

### Models

To evaluate the performance of `FIREFRONT` and `AVATAR` we considered a set of randomly generated, synthetic and published biological models.

In the file table-models.tar.gz, you can find the original model files and the corresponding .avatar specification files, exported using GINsim.

**Model Specification**

Models are specified in `AVATAR` format, which is an export format produced by the current beta version of GINsim, and inspired by the NuSMV specification format. This format is human-readable and can be easily edited to specify initial conditions or known complex attractors.

Briefly, the format includes a description of model components, distinguishing between input and proper components and indicating the values each can take. It also describes the logical rules governing proper component value updates. These sections of the model specification file are not intended for editing.

Initial conditions are specified using lines of the form `INIT COMP=v`, where `COMP` is the name of a component and `v` the corresponding initial value. Unspecified components are initialized to zero by default, unless the `--sampling` option is used (available in `AVATAR` only) in which case the component will get a random value for each simulation run. If initial oracles are specified (see below), the initial state for each simulation run is also required to be accepted by all these oracles. If it is not possible, for any initial state, to cumulatively satisfy these condition, the program exits with an error.

The model specification file can contain an `ATTRACTORS` section specifying known complex attractors whose component states will be immediately recognized by the script. The section is begun by a single line containing only the string `"ATTRACTORS"`. The specification of each complex attractor is done by a line of the form `ATTRACTOR_NAME := COND_1 | ... | COND_n ;`, where each `COND_i` represents a conjunction of component valuations of the form `COMP_1=v_1 & ... & COMP_m = v_m`. Attractor names should contain letters only, except for initial oracles (see below).

Initial oracles, which constrain the sampling pool for initial states when the `--sampling` option is used (available in `AVATAR` only) are specified in the same way as other oracles, except that the attractor name is preceded by a `'@'`.

### Download

You can download the source code of the `FIREFRONT/AVATAR` software suite here: FirefrontAvatar.tar.gz.

You can find additional information on the usage of `FIREFRONT/AVATAR`, the existing parameters, the model specification and the produced output, in the `README` file.

### Prerequisites

`FIREFRONT/AVATAR` programs are coded in `Perl` and prior to using them you need to make sure you have the following software installed in your system:

- Perl (version >= 5.10)
- R framework (version >= 2.5.10) [required by Avatar only]
- Gnuplot (version >= 4.6)

- Statistics::R [required by Avatar only]
- Chart::Graph::Gnuplot

### Command-line options

A brief description of all the command-line options of Firefront/Avatar can be accessed via the `--help` option. Below we describe the command-line options in detail. In both programs, the `--quiet` option suppresses all output except for the attractor identification and quantification results.

`FIREFRONT`

`--alpha=NUMBER`

Specifies the probability threshold (0 < NUMBER < 1) below which a state is no longer be explored and is, consequently, placed on the neglected state set. Default value is 1e-5.

`--beta=NUMBER`

Specifies the minimum total probability (0 < NUMBER < 1) contained in the firefront state set for the algorihtm to proceed to the subsequent iteration. If the probability falls below this threshold the program exists without attempting to distribute any further probability. Default value is 1e-5.

`--max-steps=NUMBER`

Specifies the maximum number (> 0) of iterations performed by the algorithm. The state exploration halts after reaching this limit. If left unspecified, the algorithm will perform, at most, as many iterations as the square of the number of states in the state space.

`--output-dir=PATH`

Specifies the output directory where the optional plots will be written to. By default, the current directory is used.

`--plots`

If this option is provided, the program produces two EPS files showing the evolution of set sizes (resp. probabilities) of the states contained in the firefront, neglected and attractors state sets.

`AVATAR`

`--runs=NUMBER`

Specifies the number of simulation runs to perform. By default, the program performs 100 simulations.

`--max-steps=NUMBER`

Specifies the maximum number of exploration steps the program performs per simulation. If more than NUMBER of exploration steps are made without reaching an attractor, the current simulation is truncated and is not counted for the attractor probability estimation. By default, each simulation performs an unbounded number of steps.

`--tau=NUMBER`

Specifies the initial value of the tau parameter to be used for cycle extension prior to any cycle re-write operation. The tau parameter automatically doubles for every new incarnation within the same simulation or in successive steps of cycle extension when the program enter an aggressive expansion mode (inflationary mode). In this latter case, each identified cycle is iteratively extended (with growing values of tau) until a maximal strongly-connected component is identified. By default, the initial value of tau is 2.

`--no-extension`

Supresses all cycle extension by setting the tau parameter to zero. Cycles identified on the course of an exploration will therefore not be extended prior to any re-write operation. However, this does not affect the inflationary mode which will still iteratively extend the current cycle to its maximal strongly-connected component, in this case starting with the default value of tau.

`--min-cycle-size=NUMBER`

Specifies the minimum numbers of states in a cycle to allow for a re-write operation. Any cycle identified (and possibly extended) which yields a strongly-connecte component with less than NUMBER elements is not re-written and the program proceeds normally. By default, only cycles with more than 4 states are re-written.

`--max-psize=NUMBER`

Specifies the maximum number of explicit transitions kept by the program before the inflationary mode is triggered. At the start of each simulation, transitions between states are implicitly defined by the logical rules of the model (except for any transient cycles which may be kept from previous simulations). On the course of a simulation, each re-write operation replaces the implicit representations within the cycle by explicit transitions towards the cycle exits and their associated probability. When the number of explicit representations exceeds NUMBER, the inflationary mode is enabled and the subsequent incarnation will iteratively extend any cycle found to the corresponding maximal strongly-connected component. The default value of this parameter is 2^15.

`--min-transient-size=NUMBER`

Specifies one of the parameters that determines whether a re-written cycle is saved for subsequent simulations (i.e. the corresponding explicit transitions). More specifically, it specifies the minimum number of states in the transient. Thus, if a transient (non-terminal strongly-connected component) has more states than NUMBER and an exit ratio below 1 (number of transient exits / number of states in the cycle) it is saved, otherwise it is not. By default, the minimum transient size is 32.

`--expand-all-transients`

This option indicates that cycles found on the course of the simulations are to be extended to the corresponding maximal strongly-connected components. This amounts to triggering the inflationary mode unconditionally. This option is automatically set for state spaces with 1024 states or less.

`--sampling`

This option indicates that the initial state of each simulation is randomly sampled from the state space considering the following restrictions: 1) only components with unspecified initial values in the model file are sampled, specified values are kept fixed; 2) if an initial oracle is specified in the model file (see below) any sampled initial state is additionnaly required to be recognized by the initial oracle(s). The program automatically detects whether it is impossible to honour both restrictions in which case it terminates with an error.

`--output-dir=PATH`

Specifies the output directory where the optional plots will be written to. By default, the current directory is used.

`--plots`

If this option is provided, the program produces two EPS files showing the evolution of the probability of reaching each found attractor on the course of the simulations and a boxplot showing the distribution of the length of the simulated trajectories towards each identified attractor.

### Output

This section describes the output produced by `FIREFRONT` and `AVATAR`.

`FIREFRONT`

The output produced by `FIREFRONT` consists of a summary header and an enumeration of the attractors found. The header reports the model name, the initial state, the program parameters (number of iterations performed versus maximum number of iterations, alpha and beta thresholds), the sizes and total probability of the firefront, neglected and attractors state sets, and the total time it took to run the program.

Each attractor found is enumerated referring whether it is a point or an oracular attractor (only found if an oracle is specified), the estimated probability of that attractor and a complete description of the state (i.e. component values), except for oracular attractors which only mention the name of the attractor.

`AVATAR`

`AVATAR`consists of a summary header and an enumeration of the attractors found. The header reports the model name, the initial state (or whether sampling was performed), the program parameter (maximum depth, the tau parameter, the minimum cycle size require to enable a re-write operation, the inflationary mode threshold, and the transient cycle size threshold for saving it for subsequent simulations). It further specifies the number of simulations asked, performed and truncated. Truncated simulations refer to simulations which reached the maximum depth without finding an attractor. Finally, the header also reports the total time it tool to run the program.

Each attractor found is enumerated referring whether it is a point, complex or an oracular attractor (only found if an oracle is specified), the estimated probability of that attractor, the minimum, maximum and average discovery depths, a complete description of the state (i.e. component values), except for oracular attractors which only mention the name of the attractor. If sampling is enabled, the estimated probability of each attractor is further broken down in terms of sampled inputs (if any), listing the contribution of each sampled input combination leading to that attractor and the corresponding partial probability.