Grzegorz Rozenberg: Natural Computing Lectures

Natural Computing is a dynamic and fast growing research area concerned with computing taking place in nature and with human-designed computing inspired by nature. A popular and important topic in the former line of research is computation in living cells, and a good example of this research is the investigation of gene assembly in ciliates.

Ciliates, a very ancient group of unicellular organisms, have evolved extraordinary ways of organizing, manipulating and replicating the DNA in their micronuclear genomes. The way that ciliates transform genes from their micronuclear (storage) form into their macronuclear (expression) form is the most involved DNA processing in nature that is known to us. This gene assembly process is also very interesting from the computational point of view.

Current research concerning gene assembly is an example of flourishing interdisciplinary research involving computer scientists and molecular biologists. The results obtained thus far are interesting and beneficial for both molecular biology and computer science. One of the central research issues is the quest for discovery of "molecular hardware" needed for the implementation (in vivo) of molecular operations accomplishing gene assembly. This quest will be the topic of our lectures.

In the first lecture we will discuss the biology of gene assembly and demonstrate a solution to the molecular hardware problem - it is based on the template-guided recombination. This recombination is very different from the standard homologous recombination of DNA strands, but it has the properties that are necessary to ensure the DNA acrobatics required for the implementation of the gene assembly process.

In the second lecture we present a mathematical theory based on the template-guided recombination. Surprisingly enough this theory turns out to be quite fundamental for theoretical computer science.

The lectures are organized in such a way that they can be followed independently of each other. However the two lectures together provide an example of a "complete package" of interdisciplinary research:

• An important problem from biology is explained and a solution for it is presented,
• A formal theory instigated by the solution turns out to be relevant for theoretical computer science,
• The implications of the formal theory provide relevant guidelines for the research on the original biological problem.

The lectures are of a tutorial character and self-contained. In particular, no knowledge of basic molecular biology is required.

Prof. Dr. Grzegorz Rozenberg
Leiden Institute of Advanced Computer Science (LIACS)
Leiden Center for Natural Computing (LCNC)
Leiden University, The Netherlands
and
Department of Computer Science
University of Colorado at Boulder, USA