TURING Algorithms for Computation with Finite Dynamical Systems

Overview

ADAM is a web-based tool for the analysis and visualization of the dynamics of multi-state, discrete models of biological networks. Multi-state discrete models are characterized by a collection of functions. For a network of n nodes, the corresponding discrete model will have n functions, where the i-th function describes the state transitions of the i-th node in the network. The user may select one of four inputs: a GINsim file, a PDS (polynomial dynamical system), a PDSep (polynomial dynamical system with external parameters), a PBN (probabilistic Boolean network), or an SDDS (stochastic discrete dynamical system). The user may upload a file or enter functions into the text box. Based upon which input type the user selects, other input options may appear. The user is guided through additional input/output options. ADAM can calculate fixed points and limit cycles of a specified length, produce the dependency graph for all networks and the state space for networks which are simulated, the graph of trajectories starting from a given initial state, and identify functional circuits along with their signed edges. ADAM analyzes dynamics using a combination of simulation and abstract algebra techniques. The method of computation and the output will depend on options selected by the user.

How to Analyze a Logical Model (generated with GINsim)

ADAM can analyze Logical Models generated with GINsim. GINsim is a program to build a logical model for a biological system such as a gene regulatory network. Internally, ADAM converts a logical model to a polynomial dynamical system (PDS) via the method described in Veliz-Cuba et al., 20101 and then uses techniques from abstract algebra to analyze the PDS for key dynamics. ADAM will assign x1 to xn to the variables used in the logical model, and states of the dynamic model are represented as vectors, where the first entry corresponds to the variable assigned to x1, and so on. For example, the logical model of Phage Lambda (left) is converted to the following PDS. ADAM determines the number of states per variable from the logical model, in this example, there are 5 different states per variable.

The Logical Model can be analyzed (using Algorithms or Simulation). This Phage Lambda model has one fixed point or steady state, represented as (2 0 0 0). This means, that C1 is 2, a medium concentration, because the first (x1 = C1) entry is 2, and the other three variables are 0, i.e., not expressed at all.

Note: Currently ADAM is only compatible with GINsim 2.3. Please use GINsim version 2.3 to generate your models in order to analyze them with ADAM.

How to Analyze a Polynomial Dynamical System (PDS)

The user can upload a text file (.txt) or directly enter the functions of a PDS. The number of states per node must be specified. It denotes the cardinality of the state set of the user's discrete network. Note that this must be a prime number. The software accepts positive prime integers up to 99. This value gives the total number of states that a node in the network can have. For example, if number of states per node = 3, then the possible states for any node are 0, 1, and 2. If the system is Boolean, i.e., the number of states per node is 2, then ADAM accepts functions in polynomial form, or in Boolean form (see Boolean Input Format).

Each node of the user's network is represented by a variable. Variable names are x1, x2, etc. Function names are f1, f2, etc. The convention is that fk is the function which describes the state transitions of the node represented by xk. ADAM will use the functions from the input text box only when the user DOES NOT select a file to upload. The functions should follow the following formatting rules:

• The functions should begin with f followed by an integer, example f1, f2, f3,...,fn, where n is the number of variables
• Use * for multiplication, + for additions and ^ for exponents.
• The variables should begin with x followed by an integer, example x1, x2, x3,...,xn, where n is the number of states

The PDS can be analyzed (using Algorithms or Simulation). For small networks (less than 10 nodes), the complete state space can be simulated and all attractors (fixed points and limit cycles) are found. In addition to that, the size of each component, i.e., the basin of attraction, are determined. For larger networks, a simulation of the complete state space is not possible. Instead, ADAM uses tools from computational algebra, to find all fixed points or limit cycles of a given length. The algorithms that ADAM uses are fast for sparse systems, a structure maintained by most biological systems. ADAM can easily compute fixed points for systems with 50 or 100 nodes, as long as every node has only a few neighbors in the wiring diagram, i.e., only a few variables appear in each function.

How to Analyze a Polynomial Dynamical System with External Parameters (PDSep)

The user can upload a text file (.txt) or directly enter the functions of a PDS in which the external parameters can take place. The user can also specify any number of external parameters that can affect the system. The number of states must be specified. It denotes the maximum number of discrete values that all variables in the system (including external parameters) can take on. Note that this must be a prime number up to 99. For example, if number of states per node = 3, then the possible states for any node are 0, 1, and 2.

Each node of the user's network is represented by a variable. Variable names are x1, x2, etc. Function names are f1, f2, etc. The convention is that fk is the function which describes the state transitions of the node represented by xk. ADAM will use the functions from the input text box only when the user DOES NOT select a file to upload. The functions should follow the following formatting rules:

• The functions should begin with f followed by an integer, example f1, f2, f3,...,fn, where n is the number of variables
• Use * for multiplication, + for additions and ^ for exponents.
• The variables should begin with x followed by an integer, example x1, x2, x3,...,xn, where n is the number of states
• The external parameters can be anything but it is better not to begin with x followed by an integer as the variables. For example, it can be N, Mg, NO3, pH, etc. The name of the specified external parameter must be exactly the same the one taking place in the functions.

The PDSep can be analyzed using Algorithms or Simulation. For small networks (less than 10 nodes), the complete state space can be simulated and all attractors (fixed points and limit cycles) are found. In addition to that, the size of each component, i.e., the basin of attraction, are determined. For larger networks, a simulation of the complete state space is not possible. The algorithms that ADAM uses are fast for sparse systems; if every node has many neighbors in the wiring diagram, ADAM may need some time to complete the analysis.

How to Analyze a Probabilistic Network

ADAM can visualize the state space of a (small) probabilistic network. In the state space of a probabilistic network, all possible transitions from one state to the next are drawn, together with their probability, if Print Probabilities is checked. The number of states per node must be specified. It denotes the cardinality of the state set of the user's discrete network. Note that this must be a prime number. The software accepts positive prime integers up to 99. This value gives the total number of states that a node in the network can have. For example, if number of states per node = 3, then the possible states for any node are 0, 1, and 2. If the system is Boolean, i.e., the number of states per node is 2, then ADAM accepts functions in polynomial form, or in Boolean form (see Boolean Input Format).

Probabilistic Networks can be entered by using { and } around several possible functions for one variable. If not specified, the functions have uniform probability, if the user wants to impose a distribution on the functions, the probability can be specified behind the function, separated with the pound symbol, #.

In probabilistic networks, fixed points are defined as state that could remain the same when updated. The stability of a fixed point is its probability to not change in the next iteration. Fixed points with stability 1 are true fixed points, as they can never transition to another state. ADAM determines true fixed points of probabilistic networks by simulation for smaller networks, or by using algorithms from computational algebra for systems too complex for simulation. Bounded Petri Nets can be represented as probabilistic networks1. In the terminology of petri nets, fixed points with stability one are deadlocks.

How to Analyze a Stochastic Discrete Dynamical System (SDDS)

If the user would like to upload a text file (.txt) for the complete transition table corresponding to their network, then it consists of all possible states and the their future states with delimiter, an arrow (->). For example, the complete transition table of a 3-node boolean network can be:

• 0 0 0 -> 0 1 0
• 0 0 1 -> 0 1 1
• 0 1 0 -> 0 1 0
• 0 1 1 -> 0 0 0
• 1 0 0 -> 1 1 0
• 1 0 1 -> 1 0 1
• 1 1 0 -> 0 0 1
• 1 1 1 -> 0 0 0

Note that the states consist of numbers not more than 2, because this is a boolean network, i.e. the number of states for this network is 2.

If the user would like to upload a text file (.txt) for the functions instead of the complete transition table, then the functions file consists of the updating functions of all variables. For example, the functions of a 3-node boolean network can be:

• f1 = x1 + 1
• f2 = x1 * x3 + x2 ^ 2
• f3 = x2 + x3 ^ 3

Here, f1 indicates the updating function of the first variable, denoted by x1. Similarly, f2 indicates the updating function of the second variable, denoted by x2, and f2 indicates the updating function of the third variable, denoted by x3. Note that the number of functions must be equal to the number of variables.

The user enters the propensity matrix entries. If they do not know the propensity matrix paramaters or want to get random simulations, then all entries of the propensity matrix should be 0.5. In the propensity matrix, the number of rows must be the number of nodes (variables) in the network, and the number of columns must be 2 that the first column is for activation and the second column is for degredation propensity. Propensity entries must be seperated by a space and a number between 0 and 1. The sum of the activation and degradation of a node does not have to be equal to 1. For example, the propensity matrix of a 3-node boolean network must have 3 rows and 2 colums and can be:

• 0.57 0.05
• 0.40 0.70
• 0.85 0.15

Therefore, for the first node, 0.57 is the activation propensity, 0.05 is the degradation propensity; for the second node, 0.40 is the activation propensity, 0.70 is the degradation propensity; for the third node, 0.85 is the activation propensity, 0.15 is the degradation propensity. "Activation Propensity" is the probability that the variable is being activated (increased) at the next time step. Similarly, "Degradation Propensity" is the probability that the variable is being degraded(decreased) at the next time step.

Note that for random simulations, the propensity matrix of a 3-node boolean network must be:

• 0.5 0.5
• 0.5 0.5
• 0.5 0.5

The user specifies the initial state, which is the starting point for all trajectories and simulations for their system. An initial state consists of integers at least 0 and less than number of states and these numbers must be separated by a space. The number of integers in the initial state must be equal to the number of nodes (variables) in the network. For example, the initial state of a 3-node boolean network can be: 0 1 1 but cannot be: 0 1.

The user specifies the nodes of interest, which consists of integers between 1 and the number of nodes (variables) and commas as delimiter. The nodes of interest indicates of which nodes the user would like to see the behavior in the plot of cell population simulation. The user must enter at least 1 and can enter at most 5 nodes of interest. For example, in a 3-node boolean network, if the nodes of interest is 1, 3, then node1 and node3 will be shown in the plot of cell population simulation.

The user specifies the number of states determining how many values a state can have. It must be prime and not more than 20. For example, the number of states is 2 for a boolean network. If the number of states is 3, then the states for any node are 0, 1, and 2.

The user specifies the number of steps determining how many states there are after the initial state in a trajectory. It must be a number more than 1000. For example, if the number of steps are 3, then the lenght of each trajectory is 4, because the first state in the trajectory is the initial state, the second state is the next state of the first state, the third state is the next state of the second state, and the forth (and the last state) is the next state of the third state. The next states re computed using transition table or functions, and propensity matrix.

The user specifies the number of simulations determining how many simulations is needed for the system. It must be number not more than 1000000 (a million). For instance, the number of simulations can be 1 if the user would like to see only 1 cell population simulation. If the number of simulations is 50, then 50 trajectories starting with the initial state will be constructed and then the average behavior of each nodes and the frequency of some of the states will be provided.

The SDDS is analyzed (using "Plot of cell population simulation and Histogram for probability distribution). The plot of cell population simulation shows what the behavior of the nodes of interest are. It can be interpreted from the plot whether the node oscillates or approaches to a certain value. However, the histogram for probability distribution indicates how frequently the states show up in the trajectories. The state and its frequency will not be shown if the frequency is less than 1.

ADAM will provide what the steady states are for the system if the user checks "Print Steady States", and probability transition matrix if the user checks "Print Probability Transition Matrix". A steady state is the state where the system does not change in time. In the example given for the (complete) transition table, the steady states for that system are 0 1 0 and 1 0 1. However, a probability transition matrix is a huge structure provides the probability of going each state to all possible states. Only nonzero probabilities will be provided, i.e. if the probability of going from a state to another is 0, then it will not be shown in the probability transition matrix. Besides, the sum of all transition probabilities from any specific state to all states must be 1. Here is an example for the probability transition matrix of a 3-node boolean network:

• Pr (0 0 0 -> 0 0 0) = 0.1
• Pr (0 0 0 -> 1 0 0) = 0.3
• Pr (0 0 0 -> 0 1 0) = 0.6
• Pr (0 0 1 -> 0 1 1) = 0.5
• Pr (0 0 1 -> 1 1 0) = 0.5
• Pr (0 1 0 -> 0 1 0) = 1
• ... (continues...)

Pr (0 0 0 -> 0 0 0) = 0.1 indicates that the probability of transitioning from 0 0 0 to 0 0 0 itself is 0.1. In addition, 0 0 1 transitions to 0 1 1 and 1 1 0 with the probability 0.5. Since 0 1 0 is one of the steady states, the probability of transitioning from 0 1 0 to itself is of course 1. Note that the sum of all transition probabilities for 0 0 0 is 1 (= 0.1 + 0.3 + 0.6).

What is the Model Type?

ADAM can analyze a logical Model (.ginml file generated with GINsim), a polynomial dynamical system (PDS), or a probabilistic network.

What is the Model Input?

The user can upload the model as a file, or, for PBS or PN, enter it directly. Logical Models must be provided as .ginml files, PBS and PN as .txt files.

What are the different Analysis Options?

ADAM will simulate dynamics for the Simulation option (11 nodes or less), meaning it computes the transition states from all possible initializations. When simulating, ADAM will output the analysis results as well as the graph of the state space. For Algorithms ADAM uses algebra to solve for fixed points and limit cycles of a specified length. ADAM uses a separate algorithm to compute dynamics in the case of Conjunctive/Disjunctive Networks. Conjunctive Boolean networks consist of functions containing only one monomial term, i.e. the functions use only the AND operator. Conversely, Disjunctive Boolean networks consist of functions which use only the OR operator. Note that the Conjunctive/Disjunctive option only works for functions defined in a Boolean ring, i.e. there can be only two states per node. (see What is the number of states per node?) Furthermore, Conjunctive/Disjunctive networks currently works only for strongly connected graphs. When input is analyzed with either the Algorithms or Conjunctive/Disjunctive network option, ADAM displays the fixed points and limit cycles in a table.

What is the number of states per node?

The states, or varying levels of concentration a protein may have or gene expression levels. If the number of states per node of a model is 2, then it is a Boolean model, with genes being either on, 0, or off, 1. In a model with 3 states, 0 can represent the state in which a gene is not expressed, 1 a gene with a medium expression level, and 2 a high level.

What is the Dependency Graph?

The dependency graph or wiring diagram shows the static relationship between the nodes by directed edges. A directed edge from variable xi to xj means that xi affects the state of xj. In ADAM, all edges in the dependency graph are functional.

What is Print Probabilities?

For probabilistic networks, ADAM can print the probability for each transition in the state space. See Probabilistic Networks.

What is the State Space Graph?

The state space is a graph where the nodes are the states of the system, and the arrows indicate, how the state dynamically change with each iteration.

What is the Updating Scheme?

This will determine the order in which to evaluate the functions.

• Synchronous: all functions get evaluated at the same time
• Sequential: the functions are evaluated in some specified order. The function indices must be entered in the input box provided with each index used exactly once and should be in the range 1 to n (number of nodes)
• For all polynomial dynamical systems asynchronous/synchronous updating yields the same fixed points. This is particularly helpful for the logical modeling community because most of their updating is done asynchronously. Note that this option applies only to PDS.

What is the Simulation Option?

If the user selects the option to view the Complete State Space, the software computes the number of connected components in the state space, as well as some statistics of the components. It displays the number of states in a component and the length of the cycle. (Since these discrete models are finite, each component necessarily has a cycle. Because the models are deterministic - they are characterized by a set of rules, given by functions - there is only one cycle per component.) If there are fixed points (i.e., cycles of length 1), then it prints the state, along with the size of its component. If the user selects the option to view the graphs, the corresponding links will be displayed which will show the graph.

The user can view the trajectory of one initialization only, if he selects that option. The input text box next to the option is where the user needs to provide the initialization. The states in the initialization should be separated by spaces. For example 1 0 0 0 1 , 2 0 3 2 1 or 11 12 10 0 1. It is important to separate the states by spaces in order for the software to distinguish between the different states. On clicking Analyze, the trajectory will be printed in a vertical fashion (one on each line) and will stop once it finds a repeated pattern. If the user has selected the option to view the state space graph, a link will be displayed which will show the graph and the cycle will be colored. The initial states provided by the user will be in the box shaped node. Below is a snapshot of the trajectory generated using example functions from Figure a with initialization 2 0 1. Single trajectories can be computed and visualized, when the network is too complex to generate the complete state space.

What is Limit Cycle Length?

For large networks, the user has to specify the length of limit cycles that ADAM is computing. Limit cycles of length 1 are the same as fixed points.

What is Feedback Circuit output option?

ADAM can analyze the model for feedback circuits. It will list all functional circuits.

What is Boolean Input Format?

ADAM provides the user withs the option to specify how the operations in the function file should be interpreted. For example, 'x1*x2' could be interpreted as polynomial multiplication of variables or as the Boolean AND operation. If the user provides functions that are in the Boolean format, ADAM will convert the Boolean functions to polynomial functions to do the computations. This only works, when number of states per node is 2. The Boolean function file must adhere to the following format:

 Boolean operator Written as AND * OR + NOT ~

The Boolean functions should also be fully bracketed infix expressions. For example, the Boolean function

x1 OR x3 OR (x2 AND NOT x3)

should be entered as

((x1+x3)+(x2*(~x3)))

or

(x1+(x3+(x2*(~x3))).

In particular, please do not use unnecessary parenthesis. For example, the following is interpreted wrongly because of the extra parenthesis around x1:

(x1*((x1)+x2)).

How is the Analysis without Simulation implemented?

There are two options for analysis without simulation. The first is specifically for conjunctive/disjunctive networks. If the user has a Boolean network consisting solely of AND operators (conjunctive) or solely of OR operators (disjunctive), then ADAM will compute the number of fixed points and limit cycles according to algorithms from Salam Jarrah et al.2. It will also output what the fixed points and limit cycles are using Gröbner basis computations.

The second option is for general networks. For networks that are too large to analyze with simulation, we use Gröbner bases. The user specifies a limit cycle length they would like to find, and our algorithm finds all limit cycles of that length.

In the worst case, computing Gröbner bases for a polynomial system has a complexity of doubly exponential in the number of solutions to the system. However, in practice Gröbner bases are computable in a reasonable time. Furthermore, for sparse systems in a finite field it is actually fairly quick. It has been shown that computing Gröbner bases in modular form is much faster in general. 3 In addition, sparse polynomials mean that simpler S-polynomials, usually of comparable length, will be added to the basis, which means less computation is involved. In short, the sparse structure of biological systems is preserved by Gröbner bases, causing our algorithms to be both efficient and fast.

What if the Analysis is too Slow?

If the analysis is too slow, it is probably due to a combination of: having too many nodes in the network, having functions that are too dense, and searching for limit cycle lengths that are too long. Finding a limit cycle of length n involves composing the system of equations n times - this means functions become more dense as n increases. As explained in How is the Analysis without Simulation implemented?, the Gröbner basis algorithm is faster for sparse polynomials.

Where can I get the source code?

The source code is not on a public repository at the moment. If you would like a copy of it, please e-mail Franziska Hinkelmann for now.

Where can I get the source code?

Please email us if you have any problems!
Nick Eriksson
Bonny Guang
Abdul Jarrah
Franziska Hinkelmann
Reinhard Laubenbacher
Rustin McNeill
Brandilyn Stigler
Hussein Vastani
Seda Arat

References

1Veliz-Cube A., Salam Jarrah A., Laubenbacher R., (2010) Polynomial Algebra of Discrete Models in Systems Biology.
2Salam Jarrah A., Laubenbacher R., Veliz-Cuba A., (2008) The Dynamics of Conjunctive and Disjunctive Boolean Network Models. Bioinformatics
3Brown W.S. (1971) On Euclid's Algorithm and the Computation of Polynomial Greatest Common Divisors. Journal of the ACM.