# Program

## Invited talks

### 10.30 - 11.30 **Interaction between biochemical reactions - Natural Computing point of view**

#### Grzegorz Rozenberg, director of the Leiden Center for Natural Computing, Leiden University

The functioning of a living cell consists of a huge number of individual reactions that interact with each other. These reactions are regulated, and the two main regulation
mechanisms are facilitation/acceleration and inhibition/retardation. The interaction between individual biochemical reactions takes place through their influence on each other, and this influence happens through the two mechanisms mentioned above.

In our lecture we present a formal framework for the investigation of biochemical reactions - it is based on reaction systems. We motivate this framework by explicitely stating a number of assumptions/axioms that (we believe) hold for a great number of biochemical reactions - we point out that these assumptions are very different from the ones underlying traditional models of computation such as,e.g., Petri Nets. We discuss some basic properties of reaction systems, and demonstrate how to capture and analyze, in our formal framework, some biochemistry related notions.

The lecture is of a tutorial character and self-contained.

### 11.30 - 12.00 **Splicing systems**

#### Clelia De Felice, Università di Salerno

Recombinant DNA (rDNA) is a general term which refers to the DNA resulting from the process of combining a piece of DNA, with another strand of DNA.
In 1987 Tom Head pioneered a language-theoretic approach for studying recombinant DNA. He introduced the splicing systems, abstract models which are a formal counterpart of the DNA recombination under the action of restriction and ligase enzymes (gene splicing).
In spite of a vast literature on splicing systems, briefly surveyed here, a few problems related to their computational power are still open. We intend to evidence how classical techniques and concepts in automata theory are a legitimate tool for investigating some of these problems.

### 12.00 - 12.30 **Distributed, probabilistic and quantum automata: a uniform compositional approach**

#### Nicoletta Sabadini, Università dell'Insubria

## Contributed talks

### 12.30 - 12.50 **On regular languages with equal generating functions**

#### Jacques Sakarovitch, Ecole nationale supérieure des télécommunications, Paris

If two regular languages L and K have the same generating functions, that is, for every integer n they have the same number of words of length n, there exists a rational bijection realised by a letter-to-letter transducer that maps L onto K.

This statement is a consequence of a refinement of the decidability of the equivalence of two automata with multiplicity in N: two N-automata are equivalent if and only if there are conjugate (by matrices with entries in N) to a same third one, and of the interpretation of conjugacy as a sequence of a state splitting and a state amalgamation.

### 13.00 - 14.30 *Lunch*

## Invited talks

### 14.30 - 15.30 **Ask not what stringology can do for you - Advances in pattern matching and discovery driven by computational biology**

#### Alberto Apostolico, Università di Padova and Georgia Institute of Technology

With its native lexicon of characters, sequences and trees, molecular biology has posed a number of interesting computational problems, some more challenging than others, of which a few have also found elegant and even useful solutions in the domain which originally inspired them. Among the many ideas and paradigms brought up in the course of the development of computational molecular biology, and the numerous implements developed in response to its needs, several have found use in remote applications, so that it may be argued that by way of inspiration and challenge molecular biology ultimately did more for computing than vice versa.

That computational problems arising, e.g., in molecular sequence analysis might have an impact in distant areas is not new.
Nuances of the phenomenon resonate across the milestone *time warps* volume edited by D. Sankoff and J. Kruskal in the early Eighties, which listed applications of string editing ranging from tectonics to the study of songs and bird signals. Therefore, the point of this talk is not to show that such a fascinating interplay is possible, but only to display a few of the more recent instances, taken somewhat arbitrarily from the direct exposure of this speaker.

### 15.30 - 16.00 **Grammatical compression**

#### Alberto Bertoni, Università di Milano

### 16.00 - 16.15 *Coffee break*

### 16.15 - 16.45 **A catalog of metabolic oscillators**

#### Vincenzo Manca, Università di Verona

A brief introduction of metabolic P systems (MP systems) will be given, as a mathematical discrete setting for analyzing metabolic phenomena and for designing, in a systematic and significant way, rewriting systems reproducing observed dynamics. Then, it will be shown as MP systems are a natural framework for studying biological oscillators, which represent a very important class of metabolic dynamics. Many examples of MP oscillators are presented and some general metabolic schemata are given which cover many relevant behaviors. Finally, some open problems and research lines will be outlined.

## Contributed talks

### 16.45 - 17.05 **Stochastic modeling and simulation of biological systems**

#### Daniela Besozzi, Università di Milano

Nowadays, one of the biggest challenges in Biology consists in the understanding of complex cellular processes, such as metabolic processes, gene regulatory networks and signaling pathways, which are the core mechanisms governing the functionality of living cells. This issue is taking advantage of mathematical modeling and computer simulations, which are becoming indispensable tools to derive formal descriptions of biological systems and to analyze how they behave in normal or altered conditions. Indeed, in silico simulations can reach a gain over conventional experimental biology in terms of cost, ease to use and speed. On the other side, standard modeling approaches based on ordinary differential equations do not always represent the most suitable formalism for the study of cellular processes. As a matter of facts, laboratory experiments are evidencing more and more often the effect of biological noise at the single-cell level, which is due to stochastic interactions between molecular species that occur in low amounts inside the cell. Taking into account this matter, many algorithms for stochastic simulations of biochemical reaction systems have been proposed, and their intrinsic suitability for reproducing the dynamics of cellular processes has been proved.

With this perspective, in this talk I will review the work that has been carried out so far by the research group leaded by Giancarlo Mauri, within the area of stochastic modeling and simulation of biological systems. In particular, I will describe the formalism we use for modeling biochemical processes, and present the simulator that has been developed for investigating the stochastic dynamics of single and multi-volume systems. I will discuss the additional problem of parameter estimation in biological systems, and describe how optimization techniques can be integrated with stochastic simulation algorithms for its solution. Finally, I will present some applications of these methodologies to the study of signal transduction pathways in yeast and in bacteria, gene regulatory networks, intracellular communication mechanisms, ecological systems, and other simple systems of biochemical reactions

### 17.05 - 17.25 **Solving computationally difficult problems by polarizationless recognizer P systems**

#### Alberto Leporati, Università di Milano-Bicocca

We briefly review two results concerning the computational power of recognizer P systems. Specifically, we show that the NP-complete problem 3-sat can be efficiently solved by polarizationless recognizer P systems using only rules for the division of non–elementary membranes and dissolution rules. A stronger version of division rules allows to solve the PSPACE-complete problem Quantified 3-sat.

### 17.30 Discussion