ETD system

Electronic theses and dissertations repository


Tesi etd-09202007-143716

Thesis type
Tesi di laurea specialistica
An Intermediate Language for Simulation of Biological Systems
Corso di studi
Relatore Prof. Barbuti, Roberto
Relatore Dott. Milazzo, Paolo
Parole chiave
  • multiset rewriting
  • Gillespie
  • P-Systems
  • CLS
  • system biology
  • string multiset rewriting
Data inizio appello
Riassunto analitico
In the last few years many formalisms, originally developed by<br>computer scientists to model systems of interacting components,<br>have been applied to Biology. Moreover, some<br>new formalisms have been proposed to describe biomolecular and membrane<br>interactions. All these formalisms can describe<br>biological systems at different levels of abstraction.<br><br>The first advantage of using formal models to describe biological systems is<br>that they avoid ambiguities. In fact, ambiguity is often a problem of the<br>notations used by biologists. Moreover, the formal modeling of biological<br>systems allows the development of simulators, which can be used to<br>understand how the described system behaves in normal conditions, and how<br>it reacts to changes in the environment and to alterations of some of its<br>components. Furthermore, formal models allow the verification of properties of<br>the described systems, by means of tools (such as model checkers) which are<br>well established and widely used in other application fields of Computer<br>Science, but unknown to biologists. It must be noticed that the development<br>of simulators for these formalisms may not be easy, in particular<br>also the definition of a stochastic semantics for those formalisms<br>may not be trivial.<br><br>In this thesis we propose an extension of multiset rewriting,<br>called \emph{String MultiSet Rewriting (SMSR)}, in which multiset<br>elements are strings and left hand sides of rewrite rules may<br>contain an operator, called maximal matching operator, which<br>allows representing the multiset of all strings having a common<br>given prefix.<br><br>SMSR can be used as an intermediate language for simulation<br>of higher level languages; here with the term high we refer to their<br>ability of describing biological systems at different level of abstraction.<br>On the one end, it is easy to develop simulators for SMSR, for<br>instance by extending the GBS simulator. On the other<br>hand, the maximal matching operator facilitates the translation of<br>higher level languages, in particular those based on term<br>rewriting. The idea is that a term can be seen as a tree, a tree<br>can be seen as a set of strings representing all paths from root<br>to leaves, and the replacement of a subtree becomes the replacement<br>of a set of strings having a common prefix. As an example we<br>start giving intuitions on the encoding of P-Systems<br>and then we show how a formalism based on term rewriting, CLS+,<br>can be translated into SMSR, and prove translation correctness and<br>completeness.<br><br>Higher level formalisms could be translated into<br>SMSR directly or via their translation into CLS+.<br>In both cases one would have the possibility of using the simulator<br>for SMSR to simulate high level descriptions.<br>