## Tesi etd-09202007-143716 |

Thesis type

Tesi di laurea specialistica

Author

CARAVAGNA, GIULIO

URN

etd-09202007-143716

Title

An Intermediate Language for Simulation of Biological Systems

Struttura

SCIENZE MATEMATICHE, FISICHE E NATURALI

Corso di studi

INFORMATICA

Supervisors

**Relatore**Prof. Barbuti, Roberto

**Relatore**Dott. Milazzo, Paolo

Parole chiave

- multiset rewriting
- Gillespie
- P-Systems
- CLS
- system biology
- string multiset rewriting

Data inizio appello

12/10/2007;

Consultabilità

Completa

Riassunto analitico

In the last few years many formalisms, originally developed by

computer scientists to model systems of interacting components,

have been applied to Biology. Moreover, some

new formalisms have been proposed to describe biomolecular and membrane

interactions. All these formalisms can describe

biological systems at different levels of abstraction.

The first advantage of using formal models to describe biological systems is

that they avoid ambiguities. In fact, ambiguity is often a problem of the

notations used by biologists. Moreover, the formal modeling of biological

systems allows the development of simulators, which can be used to

understand how the described system behaves in normal conditions, and how

it reacts to changes in the environment and to alterations of some of its

components. Furthermore, formal models allow the verification of properties of

the described systems, by means of tools (such as model checkers) which are

well established and widely used in other application fields of Computer

Science, but unknown to biologists. It must be noticed that the development

of simulators for these formalisms may not be easy, in particular

also the definition of a stochastic semantics for those formalisms

may not be trivial.

In this thesis we propose an extension of multiset rewriting,

called \emph{String MultiSet Rewriting (SMSR)}, in which multiset

elements are strings and left hand sides of rewrite rules may

contain an operator, called maximal matching operator, which

allows representing the multiset of all strings having a common

given prefix.

SMSR can be used as an intermediate language for simulation

of higher level languages; here with the term high we refer to their

ability of describing biological systems at different level of abstraction.

On the one end, it is easy to develop simulators for SMSR, for

instance by extending the GBS simulator. On the other

hand, the maximal matching operator facilitates the translation of

higher level languages, in particular those based on term

rewriting. The idea is that a term can be seen as a tree, a tree

can be seen as a set of strings representing all paths from root

to leaves, and the replacement of a subtree becomes the replacement

of a set of strings having a common prefix. As an example we

start giving intuitions on the encoding of P-Systems

and then we show how a formalism based on term rewriting, CLS+,

can be translated into SMSR, and prove translation correctness and

completeness.

Higher level formalisms could be translated into

SMSR directly or via their translation into CLS+.

In both cases one would have the possibility of using the simulator

for SMSR to simulate high level descriptions.

computer scientists to model systems of interacting components,

have been applied to Biology. Moreover, some

new formalisms have been proposed to describe biomolecular and membrane

interactions. All these formalisms can describe

biological systems at different levels of abstraction.

The first advantage of using formal models to describe biological systems is

that they avoid ambiguities. In fact, ambiguity is often a problem of the

notations used by biologists. Moreover, the formal modeling of biological

systems allows the development of simulators, which can be used to

understand how the described system behaves in normal conditions, and how

it reacts to changes in the environment and to alterations of some of its

components. Furthermore, formal models allow the verification of properties of

the described systems, by means of tools (such as model checkers) which are

well established and widely used in other application fields of Computer

Science, but unknown to biologists. It must be noticed that the development

of simulators for these formalisms may not be easy, in particular

also the definition of a stochastic semantics for those formalisms

may not be trivial.

In this thesis we propose an extension of multiset rewriting,

called \emph{String MultiSet Rewriting (SMSR)}, in which multiset

elements are strings and left hand sides of rewrite rules may

contain an operator, called maximal matching operator, which

allows representing the multiset of all strings having a common

given prefix.

SMSR can be used as an intermediate language for simulation

of higher level languages; here with the term high we refer to their

ability of describing biological systems at different level of abstraction.

On the one end, it is easy to develop simulators for SMSR, for

instance by extending the GBS simulator. On the other

hand, the maximal matching operator facilitates the translation of

higher level languages, in particular those based on term

rewriting. The idea is that a term can be seen as a tree, a tree

can be seen as a set of strings representing all paths from root

to leaves, and the replacement of a subtree becomes the replacement

of a set of strings having a common prefix. As an example we

start giving intuitions on the encoding of P-Systems

and then we show how a formalism based on term rewriting, CLS+,

can be translated into SMSR, and prove translation correctness and

completeness.

Higher level formalisms could be translated into

SMSR directly or via their translation into CLS+.

In both cases one would have the possibility of using the simulator

for SMSR to simulate high level descriptions.

File

Nome file | Dimensione |
---|---|

caravagn...hesis.pdf | 482.30 Kb |

Contatta l'autore |