A nice feedback

Just today I created this blog and consequently I am going to publish this nice piece of news… I will have a paper published in the TCS journal (Theoretical Computer Science, Elsevier). I mean, for those of you used to it, this seems to be normal (“embe??” in italian) but for me is a pleasure, a kind of a positive acknowledgment for my work. It is my third publication, i don’t care (by now) about the unknown impact factor, the relevance, the …, the…, I am just proud of that. Of course this would not have been possible without the help, write ”help” but read “substantial help” of my co-authors (Paolo Milazzo in primis…).

Lets discuss now about the work….. the title is “An Intermediate Language for the Stochastic Simulation of Biological Systems” and the authors, a part from me, are P.Milazzo (a research fellow at my CS Department), A.Maggiolo-Schettini and R.Barbuti (full professors at the same depatment of me). This work started from some ideas I developed during my master of science thesis (summer 2007) and finished before I started my phd (january 2008). The starting ideas have been published in a workshop, my first workshop, From Biology To Concurrency and Back (FBTC07 satellite event at CONCUR07), held in Lisbon, Portugal. In that paper we defined almost the same language without a formal stochastic semantics, so it was no suitable to be implemented. In this paper, which will be published in the special issue of TCS for the FBTC workshop, we added such a semantics… and now a bit of details about the work…

Firstly, why an intermediate language? This is quite easy to be explained if you have a bit of experience in writing simulation software based on formal languages in systems biology. This is, in fact, not a trivial issue and, generally, hides many difficulties (data structures, efficent algorithms, ….). This language, which you will see uses simple data structures, should (I hope ), permit the implementation of a very efficient simulator. Furthermore, there exist many languages and many simulation softwares developed within systems biology, so defining an intermediate language would be usefull to avoid programming too much other than a compiler. 

Some techincalities: we started from Multiset Rewriting, namely a multiset of elements and a set of rewriting rules. For instance, a multiset M containing molecules (a chemical solution in other words) A,A,A,B,B,C and a set of rules. Rule 1 replaces two molecules A with a molecule C, and rule 2 replaces two molucels B and one molecule C with two molecules A, namely (1) A|A->C and (2) C|C|B->AA. It is trivial to understand that the rules can be applied, in sequence, to the multiset M yielding to the multiset A|A|A|B|B|C–>C|B|B|C–>B|A|A. We enriched this formalism with a stochastic semantics, namely each rule can have a kinetic constant which represent the rate of the reaction. Furthermore, with respect to the kinetic theory of chemical reactions, each rule, when applied, will have a quickness. This allowed us to define a stochastic semantics based on the Gillespie’s Algorithm (SSA), a well-known stochastic framework for the simulation of biological systems. I will not go into details (now) with this semantics however, it is quite easy to understand the limits of this language. It is able to describe finite multisets (finite with respect to the molecules they store) and, from a theoretical perspective, it is not Turing complete (do you see the not-so-hidden Petri Net??). So we decided to define more expressive multisets, we added strings (modifiable) to the multisets. Of course string should be able to represent almost any interesting biological structure (DNA strands, preoteins, membranes, …). We enriched also rewriting rules, adding variables of many kinds and some novel operators in order to express logical propositions. Of course we added kinetic constants and defined the stochastic semantics of this new formalism, the Stochastic String Multiset Rewrting. Consequently, the state of a computation is represented by a multiset of strings which represent the encoded biological systems. The events that may happen in the biological systems are described by the mentioned stochastic rewriting rules. 

As the paper proposes an intermediate language, then we defined also the encoding of two higher level formalisms, the Stochastic Calculus of Looping Sequences and the Sotchastic \pi-calculus. Why these langauges?? Simply becasue they are base on different theoretical frameworks. The former is based on term rewriting systems while, the latter, is based on process algebras. The latter is also a very well known language in the world of systems biology. 

For the purists of proofs there are more then 15 pages of proofs for both soundness and completeness of the encodings. These proofs are big-but-boring ones ahahahahah 

The paper can be downloaded from my www page. Have fun and comments….