Paris/mgs
From 2007.igem.org
(→MGS for SMB) |
|||
| (8 intermediate revisions not shown) | |||
| Line 2: | Line 2: | ||
<br> | <br> | ||
| - | MGS is | + | MGS is an experimental programming language developed at the university of Evry dedicated to the ''modeling'' and the ''simulation'' of ''dynamical systems with a dynamical structure''. We briefly present in this section the philosophy of MGS programming. A complete presentation of the language is available [http://mgs.ibisc.univ-evry.fr/ here]. |
= Dynamical Systems with a Dynamical Structure = | = Dynamical Systems with a Dynamical Structure = | ||
| - | + | == Dynamical Structure == | |
| - | The state of a DS at a given <code>t</code> can be characterized by the elements that composed the system at <code>t</code>. The most of the time, interactions | + | Intuitively, characterizing a ''dynamical system'' (DS) is giving a formal description of how a point, the ''state'' of the system, moves in the ''phase space'', the set of all possible states of the system. This displacement specifies a rule, the ''evolution function'', saying where the point goes from its current position. A lot of formalisms have been developed to describe DS like differential equations, iterating of functions, cellular automata, ... providing the right formalism in accordance with the discrete or continuous nature of time and space. |
| + | |||
| + | The state of a DS at a given <code>t</code> can be characterized by the elements that composed the system at <code>t</code>. The most of the time, interactions occur between parts that are neighbor in this partition of the system. So the definition of the evolution function (that specifies which parts are interacting) relies on this neighborhood and often corresponds to ''local evolution laws''. | ||
From the biological point of view, we can note that a lot of dynamical systems exhibit a ''dynamical structure'': not only do the values of state variables evolve, but the phase space and the definition of the evolution function do. The phase space has to be considered as an observable of the system. We call these systems ''Dynamical Systems with a Dynamical Structure'' (DS<sup>2</sup>). | From the biological point of view, we can note that a lot of dynamical systems exhibit a ''dynamical structure'': not only do the values of state variables evolve, but the phase space and the definition of the evolution function do. The phase space has to be considered as an observable of the system. We call these systems ''Dynamical Systems with a Dynamical Structure'' (DS<sup>2</sup>). | ||
| Line 16: | Line 18: | ||
In terms of simulation, DS<sup>2</sup> are very hard to model/implement cause the data structure required for the representation of the system state, can be topologically modified. MGS was developed to answer this question. | In terms of simulation, DS<sup>2</sup> are very hard to model/implement cause the data structure required for the representation of the system state, can be topologically modified. MGS was developed to answer this question. | ||
| - | = Rewriting to Model and Simulate = | + | == Rewriting to Model and Simulate DS<sup>2</sup> == |
| - | A rewriting system (RS) is a computational device. Computations are done by replacing a subpart of an object by another one. By iterating this process on | + | A rewriting system (RS) is a computational device. Computations are done by replacing a subpart of an object by another one. By iterating this process on an object, it can be transformed in another one with respect to a set of rewriting rules. A computational example is arithmetical expression evaluation: given an expression <code>e</code> (for example <code>e=1+0</code>), it is reduced in an other expression <code>e'</code> by a simplification rule like <code>x + 0 -> x</code> meaning that <code>0</code> is neutral for <code>+</code>. |
This computational process is suitable for specifying the evolution of a DS<sup>2</sup>. The relation between DS<sup>2</sup> and RS is given as follows: | This computational process is suitable for specifying the evolution of a DS<sup>2</sup>. The relation between DS<sup>2</sup> and RS is given as follows: | ||
| Line 33: | Line 35: | ||
= MGS Features = | = MGS Features = | ||
| - | MGS embeds these notions through the | + | MGS embeds these notions through the concepts of ''topological collections'', ''transformations'' and ''rules application strategies''. |
== Topological Collections == | == Topological Collections == | ||
| - | They are the only way to aggregate data in MGS. Collections are used to describe the state of a DS<sup>2</sup>. They are composed of a set of elements, the different parts of the system, together with a neighborhood relationship between | + | They are the only way to aggregate data in MGS. Collections are used to describe the state of a DS<sup>2</sup>. They are composed of a set of elements, the different parts of the system, together with a neighborhood relationship between elements, representing possible interactions. For example, if collection elements are molecules, when two molecules are neighbor that means they are "close" enough to react. |
| - | There | + | There exist several types of topological collections in MGS. In this project we have used three of them: |
| - | * '''square grids''': this collection is typically used to specify cellular automaton based models. The elements of the collection are the cases of the square grid and the neighborhood is regular: each case has four neighbors following north, south, east and west | + | * '''square grids''': this collection is typically used to specify cellular automaton based models. The elements of the collection are the cases of the square grid and the neighborhood is regular: each case has four neighbors following north, south, east and west directions. We use them to simulate the [[Paris/Cell_auto|DAP diffusion]] in our system. |
| - | * '''Delaunay triangulations''': a Delaunay triangulation is procedure that, given a finite set of points localized in | + | * '''Delaunay triangulations''': a Delaunay triangulation is procedure that, given a finite set of points localized in an euclidean space, computes the triangulation between the points that is as regular as possible. This provides a very natural neighborhood between points. As the neighborhood depends on the localization of each element of the collection, Delaunay triangulations are useful to describe dynamical structure. We use this triangulation to represent the spatial organization of cells in [[Paris/Cell_auto_2|this model]]. The points used for the triangulation are the position of cells. As the cells are diffusing, dividing, dying, ... , the neighborhood is recomputed and updated. This example also considers that a spring exists between two neightbor cells in order to simulate the aggregation of the population. |
| - | * '''bags''': the last collection is also called ''multi-sets''. They are collections when each element is neighbor of all the | + | * '''bags''': the last collection is also called ''multi-sets''. They are collections when each element is neighbor of all the others. They are particularly suitable for representing well-mixed chemical solutions. We used them is the [[Paris/Stochastic_model|Gillespie based simulation]]. |
== Transformations == | == Transformations == | ||
| - | Transformations are functions of topological | + | Transformations are functions of topological collections. They are defined by sets of rewriting rules; the following expression is a skeleton of a transformation definition: |
<code> | <code> | ||
| Line 59: | Line 61: | ||
</code> | </code> | ||
| - | Each rule is composed of a pattern used to specify an interaction, ''i.e.'' a subpart of the collection where an interaction occurs. Typically, the pattern <code>x, y</code> matches two elements of the collection (we can refer to these elements in the right hand side using <code>x</code> and <code>y</code> variables) that neighbor (this is the meaning of the comma). The right hand side is an MGS expression that evaluates a sequence of values. This sequence will be put in the collection at the place of the matched sub-collection. | + | Each rule is composed of a pattern used to specify an interaction, ''i.e.'' a subpart of the collection where an interaction occurs. Typically, the pattern <code>x, y</code> matches two elements of the collection (we can refer to these elements in the right hand side using <code>x</code> and <code>y</code> variables) that are neighbor (this is the meaning of the comma). The right hand side is an MGS expression that evaluates a sequence of values. This sequence will be put in the collection at the place of the matched sub-collection. |
A lot of examples of transformations are given in the [[Paris/Sources|sources]] of our programs. Example of MGS programs are also available in the MGS [http://mgs.ibisc.univ-evry.fr/ImageGallery/mgs_gallery.html official gallery]. | A lot of examples of transformations are given in the [[Paris/Sources|sources]] of our programs. Example of MGS programs are also available in the MGS [http://mgs.ibisc.univ-evry.fr/ImageGallery/mgs_gallery.html official gallery]. | ||
| Line 65: | Line 67: | ||
== Rules Application Strategies == | == Rules Application Strategies == | ||
| - | + | This last feature allows to parametrize the application of a transformation on a collection by a rules application strategy, that is a policy specifying the order, the number of applications, and the priority of the rules. Rules can for example be applied synchronously everywhere in the collection or asynchronously when only one rule is chosen and applied once. MGS provides some strategies. Our programs use two of them: | |
| + | |||
| + | * the ''maximal-parallel'' strategy: this strategy is standard in the simulation of DS. It consists in applying each rule (on separated sub-collection) as many times as possible. Intuitively, this means that the local evolution laws specified by the transformation rules are concurrent and act all together at each time step. This strategy is used in the [[Paris/Cell_auto|DAP diffusion]] model and in the [[Paris/Cell_auto_2|dynamical structure]] model. | ||
| + | |||
| + | * the ''gillespie'' strategy: this strategy is specific to the exact stochastic simulation of chemical reactions. An introduction to Gillespie simulation method is given [[Paris/Stochastic_model#Gillespie.27s_SSA|here]]. Each rule of the transformation is considered to be a chemical reaction. An application of a transformation with this strategy consists in choosing the chemical reaction with the highest probability to occur as soon as possible (knowing the chemicals concentrations and the kinetics of the represented reaction), and to apply it once in the collection. | ||
| + | |||
| + | = MGS Top-level = | ||
| + | |||
| + | All our programs have been executed using the MGS top-level available [http://mgs.ibisc.univ-evry.fr here]. This implementation of the language is a prototype but it can be used to quickly design models of complex systems as we did for SMB. In fact, one of the major advantage of using MGS is time-saving when developing models. The concepts behind the three models have been programmed in about half a day each. All the rest of the time we spent in developing programs was dedicated to optimize execution time, generate outputs and tune parameters. | ||
Latest revision as of 23:53, 26 October 2007
MGS is an experimental programming language developed at the university of Evry dedicated to the modeling and the simulation of dynamical systems with a dynamical structure. We briefly present in this section the philosophy of MGS programming. A complete presentation of the language is available [http://mgs.ibisc.univ-evry.fr/ here].
Contents |
Dynamical Systems with a Dynamical Structure
Dynamical Structure
Intuitively, characterizing a dynamical system (DS) is giving a formal description of how a point, the state of the system, moves in the phase space, the set of all possible states of the system. This displacement specifies a rule, the evolution function, saying where the point goes from its current position. A lot of formalisms have been developed to describe DS like differential equations, iterating of functions, cellular automata, ... providing the right formalism in accordance with the discrete or continuous nature of time and space.
The state of a DS at a given t can be characterized by the elements that composed the system at t. The most of the time, interactions occur between parts that are neighbor in this partition of the system. So the definition of the evolution function (that specifies which parts are interacting) relies on this neighborhood and often corresponds to local evolution laws.
From the biological point of view, we can note that a lot of dynamical systems exhibit a dynamical structure: not only do the values of state variables evolve, but the phase space and the definition of the evolution function do. The phase space has to be considered as an observable of the system. We call these systems Dynamical Systems with a Dynamical Structure (DS2).
An obvious example of biological DS2 is the embryo development. Initially, the state of the system is described by the chemical state of the egg (however complex is this description). After many divisions, the systems is not well described by the chemical state of one cell, but many cells. Moreover the spatial organization of the cells matter in the future (spatial) development of the organism. The number of cells, their spatial organization and the interactions continually evolve.
In terms of simulation, DS2 are very hard to model/implement cause the data structure required for the representation of the system state, can be topologically modified. MGS was developed to answer this question.
Rewriting to Model and Simulate DS2
A rewriting system (RS) is a computational device. Computations are done by replacing a subpart of an object by another one. By iterating this process on an object, it can be transformed in another one with respect to a set of rewriting rules. A computational example is arithmetical expression evaluation: given an expression e (for example e=1+0), it is reduced in an other expression e' by a simplification rule like x + 0 -> x meaning that 0 is neutral for +.
This computational process is suitable for specifying the evolution of a DS2. The relation between DS2 and RS is given as follows:
- the state of the system = a data structure (this structure fits the organization of the system)
- the dynamics of the system = a set of rewriting rules. A rewriting rule
a => bspecifies a local evolution law. It is composed of two parts: the left hand sideais a pattern of interaction, and the right hand sidebevaluates the products of the interaction. The application of a rule works as follows:
-
ais used to select a subpartAof the systemSwhere an interaction occurs,
-
-
bis used to evaluate the productBof the interaction,
-
-
Ais finally replaced byBinS.
-
MGS Features
MGS embeds these notions through the concepts of topological collections, transformations and rules application strategies.
Topological Collections
They are the only way to aggregate data in MGS. Collections are used to describe the state of a DS2. They are composed of a set of elements, the different parts of the system, together with a neighborhood relationship between elements, representing possible interactions. For example, if collection elements are molecules, when two molecules are neighbor that means they are "close" enough to react.
There exist several types of topological collections in MGS. In this project we have used three of them:
- square grids: this collection is typically used to specify cellular automaton based models. The elements of the collection are the cases of the square grid and the neighborhood is regular: each case has four neighbors following north, south, east and west directions. We use them to simulate the DAP diffusion in our system.
- Delaunay triangulations: a Delaunay triangulation is procedure that, given a finite set of points localized in an euclidean space, computes the triangulation between the points that is as regular as possible. This provides a very natural neighborhood between points. As the neighborhood depends on the localization of each element of the collection, Delaunay triangulations are useful to describe dynamical structure. We use this triangulation to represent the spatial organization of cells in this model. The points used for the triangulation are the position of cells. As the cells are diffusing, dividing, dying, ... , the neighborhood is recomputed and updated. This example also considers that a spring exists between two neightbor cells in order to simulate the aggregation of the population.
- bags: the last collection is also called multi-sets. They are collections when each element is neighbor of all the others. They are particularly suitable for representing well-mixed chemical solutions. We used them is the Gillespie based simulation.
Transformations
Transformations are functions of topological collections. They are defined by sets of rewriting rules; the following expression is a skeleton of a transformation definition:
trans name = {
pattern1 => expression1 ;
...
patternN => expressionN ;
}
Each rule is composed of a pattern used to specify an interaction, i.e. a subpart of the collection where an interaction occurs. Typically, the pattern x, y matches two elements of the collection (we can refer to these elements in the right hand side using x and y variables) that are neighbor (this is the meaning of the comma). The right hand side is an MGS expression that evaluates a sequence of values. This sequence will be put in the collection at the place of the matched sub-collection.
A lot of examples of transformations are given in the sources of our programs. Example of MGS programs are also available in the MGS [http://mgs.ibisc.univ-evry.fr/ImageGallery/mgs_gallery.html official gallery].
Rules Application Strategies
This last feature allows to parametrize the application of a transformation on a collection by a rules application strategy, that is a policy specifying the order, the number of applications, and the priority of the rules. Rules can for example be applied synchronously everywhere in the collection or asynchronously when only one rule is chosen and applied once. MGS provides some strategies. Our programs use two of them:
- the maximal-parallel strategy: this strategy is standard in the simulation of DS. It consists in applying each rule (on separated sub-collection) as many times as possible. Intuitively, this means that the local evolution laws specified by the transformation rules are concurrent and act all together at each time step. This strategy is used in the DAP diffusion model and in the dynamical structure model.
- the gillespie strategy: this strategy is specific to the exact stochastic simulation of chemical reactions. An introduction to Gillespie simulation method is given here. Each rule of the transformation is considered to be a chemical reaction. An application of a transformation with this strategy consists in choosing the chemical reaction with the highest probability to occur as soon as possible (knowing the chemicals concentrations and the kinetics of the represented reaction), and to apply it once in the collection.
MGS Top-level
All our programs have been executed using the MGS top-level available [http://mgs.ibisc.univ-evry.fr here]. This implementation of the language is a prototype but it can be used to quickly design models of complex systems as we did for SMB. In fact, one of the major advantage of using MGS is time-saving when developing models. The concepts behind the three models have been programmed in about half a day each. All the rest of the time we spent in developing programs was dedicated to optimize execution time, generate outputs and tune parameters.
