Recent Computability Models Inspired from Biology: DNA and Membrane Computing

Recent Computability Models Inspired from Biology: DNA and Membrane Computing Gheorghe PÃUN, Mario J. PÉREZ-JIMÉNEZ ABSTRACT: We briefly present two areas of natural computing, vividly investigated in the recent years: DNA computing and membrane computing. Both of them have the roots in cellular biology and are rather developed at the theoretical level (new concepts, models, paradigms of computer science, with mathematical and epistemological significance have been considered in this framework), but both areas are still looking for implementations of a practical interest. Keywords: Computer Science, Mathematics, Turing computability, Biochemistry, DNA computing, Membrane Computing. 1 Introduction In a great extent, the history of (theoretical) computer science is the history of attempting to model (formalize) the computations performed in nature, starting with the way the humans compute (this was, for instance, the explicit goal of Leibniz, at the turn of seventeenth and eighteenth centuries, and of Turing, in 1935–36), going through the supposed organization and functioning of the brain, of the networks of neurons (this is the origin of finite automata, see McCulloch & Pitts 1943, Kleene 1956, and of neural networks area, see, e.g., Andersson 1996), and getting closer and closer to the molecular biology, to the cell and its constituents. The general assumption/observation is that life has used for millions of years many processes, taking places in specific material environments and using specific material structures, which may be considered as computing processes and devices. This assertion is debatable: What is a computation? Does nature computes? At which levels? Which processes are and which are not computations? And so on and so forth. We do not enter here this debate (we adhere to the opinion that nature just evolves, the goal of life is life itself, and a process can be considered a computation only by a human being, ‘computing’ is not a natural activity, but an artifact) and we adopt a mathematical perspective: computing means Turing computing (an inputoutput relation, established by “mechanically” following an algorithm: a precise sequence of instructions which always halts). Moreover, when we look to a piece of reality we search suggestions for two basic ingredients of a computing model: data structures (supports for computing) and operations about these data structures. Of course, these elements of any computing model do not exist as such, we abstract them from the biochemical objects/structures and processes. (We anticipate, illustrating this discussion with the structure of the DNA molecules and the many operations which are possible with these molecules.) After abstracting a data structure and some operations about it, we can proceed in a rather standard way in order to obtain a computing device where the data structure can be processed by means of the considered operations: consider an initial configuration of our device, consisting of one or several sets of operation-based ‘instructions’ and a given collection of data; by using the instructions in a specified manner we pass to a new configuration; by iterating the operations we ob- Gheorghe PÃUN, Mario J. PÉREZ-JIMÉNEZ 72 tain a computation; define in some way the notion of a successful computation; starting from the initial configuration of the ‘device’, where the input of the computation is placed, and proceeding along a successful computation, we can get the output of the computation, its result. This scenario is followed both in DNA and membrane computing, the two areas of natural computing we are going to discuss in the next sections. Before going into some details, some generalities are still worth mentioning. Natural computing is an important trend of computer science looking for computing models – perhaps also computers – inspired from the way nature “computes”, and it contains areas which were already proved as successful both theoretically and practically. The examples of neural networks and of genetic algorithms (more generally, of evolutionary computing) are illustrative in this respect. Especially interesting from our point of view are genetic algorithms (see, e.g., Beyer 2001): optimization problems are formulated in terms of improving a fittness function over a population of “chromosomes”, represented by strings of digits, which evolve by means of operations known from the genetics, such as recombination and point mutation. At the first sight, this is just a random walk through the space of possible solutions, a brute force approach, which highly contrasts with the surprising success of such algorithms in a large number of applications. There is no mathematical “explanation” of this success, but this observation brings optimism to natural computing research: the fact that life uses certain tools (again, at an abstract level: data structures and operations), which were improved during evolution, during a long interval of time, can be an indication that these tools have some features which make them useful also for computing. If recombination, point mutation, selection, etc, were useful and so efficient in genetic algorithms, why not assuming that other similarly useful tools and computing ideas can be found at the genetic level or at upper levels, such as the living cell. Insisting at the DNA level we get DNA computing, insisting at the cellular level we get the membrane computing. Some differences between the above mentioned areas are visible and interesting for what follows. Neural networks and genetic algorithms are inspired from biology and implemented on usual electronic computers. They aim at finding new types of algorithms, for a better use of the classic computer, maybe for also improving the architecture of the classic computer. In turn, DNA computing has a different goal, a new ambition: to use DNA molecules as a support for computing, to replace/supplement the electronic chip with a “wet chip”. The need for this arises from the observation that the electronic chips cannot continue too much to become smaller, cheaper, faster, because, if they will do it as in the last decades (in sixties was formulated the so-called Moore law, saying that every year the computers will become twice smaller, cheaper, and faster; later the interval was increased to 18 months, then to two years, now the law seems to be abandoned), they will soon reach the quantum barrier. Moreover, the sequential computers have intrinsic efficiency limits (they cannot solve problems of exponential complexity in a feasible time); a possible way to overpass this intrinsic limit is the parallelism, but this raises serious difficulties in the electronic case, for instance, in what concerns the control of processors, the energy they dissipate, etc. A promise comes from biology, from DNA and cellular levels. The parallelism made Recent Computability Models Inspired from Biology: DNA and Membrane Computing 73 possible by DNA molecules is really massive: billions of molecules – hence “processors” – can find room in a tiny biochemical test tube; moreover, biochemistry is highly nondeterministic, which means that the control of computations could be of a new type, “cheap” from several points of view. DNA computing deals with computing in vitro, with implementing algorithms in a laboratory (there also are researches about DNA computing in vivo, mainly dealing with the computing-like processes which take place in certain cells at the genetic level, for instance, in ciliates). What about the cell, the smallest living unit we know? The cell is a very complex biochemical “factory”, where many processes take place, some of them of an informational type. Can the living cell be considered/interpreted/used as a computing device? The question is not simple: What is a cell (from a mathematical point of view)? Which features of the cell structure and which processes taking place in the cell compartments are useful/essential for a computing model? After abstracting a cell-like computing model, as we will immediately see, where should we try to implement it, on a usual electronic computer (like in the case of genetic algorithms) or on a bio-support (as it is the goal of DNA computing)? We do not answer here these questions; the aim of this paper is only to let the reader having a first contact with DNA and membrane computing areas, at an introductory and informal level. Details (including further questions) can be found in the titles mentioned in the bibliography, and the web pages devoted to the two discussed domains. 2 A Glimpse to DNA Computing The fact that the DNA molecules can be used as a support for computing has been speculated since several decades (Ch. Bennett, M. Conrad, etc), but the first (successful) experiment has been reported in 1994, by L.M. Adleman. The problem dealt with was the so-called Hamiltonian path problem for directed graphs: whether or not a path exists which visits each node of a graph exactly once. The problem is known to be computationally difficult (it is NP-complete), but the solution was very efficient (obtained in linear time). Seen after eight years, the experiment looks simple from a biochemical point of view: one encodes the nodes by single stranded DNA molecules of length 20 (consisting of 20 nucleotides), then one encodes the edges of the graph by single stranded DNA molecules which are complementary, in the Watson-Crick sense, to the node-codes and consist of the second half of the code of the emerging node and the first half of the target node of the edge, one places billions of such molecules in a test tubes and one lets them to anneal and form double stranded molecules; in this way, the edge-codes act as splints of node-codes, hence the possible paths in the graph are encoded by chains of node-codes and edge-codes; by wellknown filtering procedures one selects the paths which visit all nodes exactly once (the Hamiltonian ones); if any molecule exists which encodes such a path, then the problem has the answer “yes”. Adleman’s experiment was a great event in computer science, in spite of the fact that the graph considered was a small one, with only seven nodes and thirteen edges. However, the experiment was the first one of this type, it proved that DNA computing is possible; in the terms of Hartmanis (1994), this was a demo. Many experiments Gheorghe PÃUN, Mario J. PÉREZ-JIMÉNEZ 74 have followed, in USA, Japan, Europe, conferences were initiated in this area, a large number of papers were published. However, up to now no computation of a practical interest was reported. The passing from a toy-problem to a problem of a significant size is not at all easy, because of the quantity of required DNA (and of other biochemical tools), and, mainly, because of the difficulty of coping with errors. The biochemical reactions cannot (yet) be perfectly controlled, the algorithms based on them are error-prone, and this requests both progresses in bioengineering and in improving the theoretical models (and in finding the adequate classes of problems to be attacked in this area, e.g., with error resistant solutions). To abstract a little bit, Adleman has used as data structure the DNA molecule (single or double stranded) and the annealing operations as the basic operation. In a massively parallel manner, this operation ensures the generation of all candidate solutions of the problem (providing that “enough” DNA is present). The filtering phase, when it was checked whether or not a solution exits, can be considered as the phase of reading the result; it was done manually, but the number of steps was of the same order of magnitude as the number of nodes of the graph – hence the linear time of solving the problem. The many experiments which were reported in the meantime use similar data structures (sometimes, circular molecules, or molecules with other shapes, such as hairpins), but several other operations. One of the most interesting case is that of the splicing operation, considered for the first time by T. Head, in 1987, in a theoretical framework not directly dealing with computing. This operation was explicitly used in a computing model by Pãun, Rozenberg, and Salomaa (1996), where the notion of an H system was introduced. Because these systems are among the most investigated DNA computing models and because they are typical for this area, we will present them with some details in the next section. For further models of DNA computing we refer to the web page www.wi.liacs.nl/home/pier/aaa, to the monograph Pãun, Rozenberg, and Salomaa, 1998, to the proceedings volumes of the series of conferences DNA Based Computers, initiated in 1995 in Princeton, as well as to the new Kluwer journal Natural Computing and the new Springer series of books with the same title. 3 Computing by Splicing: H Systems The abstract splicing operation was introduced in 1987 by T. Head, as a mathematical model of the recombination of DNA molecules under the influence of restriction enzymes (and ligases) –therefore (theoretical investigations of) computing by splicing has been initiated seven years before Adleman’s experiment. The splicing of two DNA molecules corresponds to two operations: cutting the molecules by restriction enzymes and pasting together the fragments obtained in this way, providing that they have matching sticky ends. For example, consider the following two (double stranded) DNA molecules: 5' - CCCCCTCGACCCCC - 3' 3' - GGGGGAGCTGGGGG - 5' and 5' - AAAAAGCGCAAAAA - 3' Recent Computability Models Inspired from Biology: DNA and Membrane Computing 75 3' - TTTTTCGCGTTTTT - 5' and the restriction enzymes TaqI and SciNI, for which the recognition sites are: T C G A G C G C A G C T and C G C G espectively (we have also indicated the cuts that these enzymes make within their recognition sites). These enzymes will cut the above two molecules producing the following four molecules: 5' - CCCCCT CGACCCCC - 3' 3' - GGGGGAGC, TGGGGG - 5' 5' - AAAAAG CGCAAAAA - 3' 3' - TTTTTCGC, GTTTTT - 5' Because the fragments obtained in this way have complementary sticky ends, the annealing of sticky ends followed by ligation will either reproduce the two original molecules, or the following two new molecules will be formed: 5' - CCCCCTCGCAAAAA - 3' 3' - GGGGGAGCGTTTTT - 5' 5' - AAAAAGCGACCCCC - 3' 3' - TTTTTCGCTGGGGG - 5' As a model of the above biochemical operation, T. Head considered a string operation (passing from double stranded sequences to strings is allowed due to the precise WatsonCrick complementarity of nucleotides) which was further abstracted in (Pãun 1996a). In short, one considers splicing rules of the form r=u1#u2$u3#u4, where u1, u2, u3, u4 are strings over a given alphabet. Given such a rule r, and two strings w1u1u2w2, z1u3u4z2, by the splicing of these strings we get the strings w1u1u4z2, z1u3u2w2. The relation with the biochemical operation of recombination is clear: each string u1u2, u3u4 corresponds to the site of a restriction enzyme, two sites stay together in the same rule if they produce matching sticky ends, while the crossing is supposed to be included in the context strings (hence it can be empty). From string operations we pass to language operations in the natural manner: consider a set R of splicing rules (of any type) and a set L of strings; by splicing any two possible strings from L we get a new set of strings, R(L); the process can be iterated, starting either from R(L) or from L∪R(L) (the latter case corresponds to the observation that when a DNA molecule is present, we may assume that arbitrarily many copies of it are present, obtained by amplification; in the first case we may assume that the reaction is complete, all old strings having been processed). In this way, a computing (language generating) device is obtained, of the form γ=(V, A, R), where V is an alphabet, A is a set of strings over V , and R is a set of splicing rules over V . Such a machinery generates a language in the following way: start from the strings in A, splice them in all possible ways with respect to the rules in R, add all resulting strings to A and iterate the process. The language generated by , denoted by L(γ), consists of all strings which can be obtained in this way. A standard extension is to also consider a terminal alphabet, T⊆V , and to accept in L(γ) only the strings consisting of symbols from T. Gheorghe PÃUN, Mario J. PÉREZ-JIMÉNEZ 76 Splicing systems γ=(V, A, R) with finite sets A and R (hence without a terminal alphabet) cannot generate all regular languages, but, conversely, the language L(γ) generated by such a system is regular. For Head rules this was proved by K. Culik II and T. Harju already in 1991, while for Pãun rules it was proved by D. Pixton (1996). Splicing systems of the form γ=(V, T, A, R), with finite A and R, characterize the family of regular languages, hence the power of finite automata. From a computational point of view, the competence of finite automata is too limited. A characterization of recursively enumerable languages (hence of the power of Turing machines) is obtained when using a set of splicing rules which is a regular languages (the rules are written as strings, hence it makes sense to speak about the type of their language). From a computational point of view, the above mentioned results are quite “frustrating”: finite H systems compute only at the level of finite automata, while the computational universality is obtained by using an infinite set of splicing rules. Fortunately, the proof of the universality (Pãun 1996b) indicates a number of ways for overcoming this drawback. This proof goes as follows. Starting from a type-0 Chomsky grammar G, one constructs an equivalent extended H system γ whose sentential forms are circularly permuted versions of the sentential forms of G, and the simulation of the rules of G takes place within suffixes of the sentential forms of γ (the circular permutation ensures that each derivation step in G can be simulated in this way). Very crucial for this “rotateandsimulate” procedure are the first and the last symbols of each sentential form, which in fact are markers, holding some information about the current stage of the simulation. That is, we can ignore the strings we splice as long as we know their first and last symbols, and the splicing sites. In other words, it is sufficient to have a finite number of splicing rules, and to associate with each rule certain “promoters”, which are symbols whose presence allows the splicing of a given string. This observation leads to extended H systems with permitting contexts, whose rules have associated finite sets of symbols such that a rule is applicable only to strings which contain the associated symbols. Actually, many other types of controlled H systems were considered. About a dozen such systems can be found in the literature, in general imitating the types of controls known from the “classic” regulated rewriting area in formal language theory. In particular, the following controls were investigated: forbidding contexts (symbols are associated with rules and a string cannot be spliced if it contains such a symbol), target languages (the splicing of two strings is allowed only if the resulting strings belong to a given regular language which is associated with the rule or associated with the whole set of rules; in the former case we say that we have local targets, and in the latter case we have a global target), programmed control (a next mapping is given on the set of rules, which indicates the sequencing of rules), evolving sets of rules (at each step, a different set of rules is produced, by point mutation rules which act on the splicing rules themselves), double splicing (the strings resulting from the splicing of two strings are immediately spliced again by any available rule), considering multisets of strings (the strings are counted, by splicing they are consumed, the multiplicity of strings resulting from a splicing operation is increased by one). References can be found in the sources mentioned at the end of the previous section. Recent Computability Models Inspired from Biology: DNA and Membrane Computing 77 In all these cases one gets characterizations of recursively enumerable languages. Similar results are obtained for various types of distributed H systems, where the strings and the set of splicing rules are separated in various ways, so that a system of several “simple” H systems is obtained, working in a parallel manner and cooperating in obtaining a common result. All the proofs are constructive, hence, starting from universal type-0 grammars, one can obtain universal H systems, hence programmable H systems able of computing at the level of Turing machines. These results have some general consequences. The fact that iterated splicing with respect to a finite set of rules computes only regular languages indicates that what we can compute in the free mode (hence in the mode encountered in nature) is not too much. Therefore, we need a further ingredient in order to achieve the desired universality. A series of possibilities are suggested by the controlled and the distributed H systems mentioned above. However, the controls and the distributed architectures considered up to now seem not easy to be implemented within the present day biotechnology. So, an important dilemma arises: should we confine at the level of finite automata and hope to implement a weak computing device based on splicing soon, or, providing that we need a higher computing power, should we have to look for improved models and for improved bio-technologies in order to, hopefully, implement a universal DNA computer? A question of a great interest, to be addressed in an interdisciplinary team, in the near future. 4 Membrane Computing DNA computing deals with processes taking place at the genetic level, with the hope to repeat them in vitro. However, many processes which are observed in vivo cannot be repeated at all, or they develop in a different way in vitro. A possible solution is to use the cell itself as the environment of a computation, and this is the starting point of membrane computing. The area is rather young – it was initiated by (Pãun 2000) (the paper was circulated on web at the end of 1998) –but it is rather developed from a mathematical point of view. We will recall here only the most basic ideas and results, the main classes of membrane systems and their properties; for further details, we refer the reader to the web page http://psystems.disco.unimib.it and to the monograph (Pãun 2002). Membrane computing starts from the assumption that the processes taking place in the compartmental structure of a living cell can be interpreted as computations. Abstracting from the biochemical details, one gets membrane systems (called also P systems), which, roughly speaking, consists of a cell-like membrane structure, in the compartments of which one places multisets of objects which evolve according to given rules in a synchronous, parallel, and non-deterministic manner. The objects can be described by symbols or by strings of symbols from a given alphabet. The objects can also pass through membranes, the membranes can be dissolved, divided, created. An evolution of a membrane system is a computation; we consider as successful only the Gheorghe PÃUN, Mario J. PÉREZ-JIMÉNEZ 78 halting computations, with which a result is associated. Many classes of P systems were already considered in the literature. Most of them are computationally complete, i.e., equal in power to Turing machines. If an exponential workspace can be created (in polynomial time), by dividing membranes, or by replicating string-objects, or by creating membranes from objects which can be replicated, then polynomial time solutions to NP-complete problems can be obtained. The membranes appearing in a P system try to mimic the role and the functioning of membranes from living cells. The basic function of biological membranes is to define compartments and to relate compartments to their environment, including neighbouring compartments. The currently accepted model of the membrane structure is the socalled fluid-mosaic model, proposed in 1972 by S. Singer and G. Nicolson. According to this model, a membrane is a phospholipid bilayer in which protein molecules (as well as other molecules) are totally or partially embedded. Figure 1: A membrane structure The (plasma) membrane is only partially permeable (in general, to small noncharged molecules), but various molecules can pass through membranes by means of protein channels. The transmembrane transfer can take place in a passive manner, e.g., by diffusion towards the region of lower concentration, and in an active (mediated) manner. Actually, there are two main types of protein channels: those which just select the moving objects by their size, and those which interact with specific molecules when helping them to cross the membrane; the latter type is called carrier protein. The protein channels are also important for the inter-cellular communication: neighbouring cells can link their protein channels, and in this way, a complex communication network can be established among cells. It is important to note that the protein channels can be open or closed, depending on the contents of the adjacent compartments. For instance, if one of the cells is invaded by “undesired” molecules, then the cell isolates itself from the neighbouring cells by closing the passage channels – they may be re-opened again, once the emergency situation has been resolved. Membrane Systems (with Symbol-Objects) – An Informal Introduction. The membrane structure of a P system is a hierarchical arrangement of membranes (understood as three dimensional vesicles), embedded in a skin membrane, the one which separates the system from its environment. A membrane without any membrane inside is called elementary. Each membrane defines a region. For an elementary membrane this is Recent Computability Models Inspired from Biology: DNA and Membrane Computing 79 the space enclosed by it, while the region of a non-elementary membrane is the space inbetween the membrane and the membranes directly included in it. Figure 1 illustrates these notions. We label membranes (by positive integers in Figure 1) in order to be able to address them in programming computations by membrane systems. Since each region is delimited (“from the outside”) by a unique membrane, we will use the labels of membranes to also identify (label) the regions they delimit. Each region contains a multiset of objects, and a set of (evolution) rules. The objects are represented by symbols from a given alphabet. Typically, an evolution rule from region r is of the form ca→cbinjdoutehere, and it “says” that a copy of the object a, in the presence of a copy of the catalyst c (this is an object which is never modified, it only assists the evolution of other objects), is replaced by a copy of the object b and two copies of the object d. Moreover, the copy of b has to enter “immediately” the inner membrane of region r labeled by j (hence to enter region j), one copy of object d is sent out through the membrane of region r, and one copy of e remains in region r. Note that the considered evolution rule can be applied in the region r only if this region includes the membrane j. Membrane systems are synchronous, in the sense that a global clock is assumed, i.e., the same clock holds for all regions of the system. In each time unit a transformation of a configuration of the system takes place by applying the rules in each region, in a nondeterministic and maximally parallel manner. This means that the objects to evolve and the rules governing this evolution are chosen in a nondeterministic way; this choice is “exhaustive” in the sense that, after the choice was made, no rule can be applied anymore in the same evolution step (there are not enough objects available anymore for any rule to be applied now –this is the maximality of application). In this way, one gets transitions between the configurations of the system. A sequence of transitions is called a computation. A configuration is halting, if no rule is applicable in any region. A computation is halting if it reaches a halting configuration. The result of a (halting) computation is the number of objects sent (through the skin membrane) to the environment during the computation. Many modifications/extensions of this very basic model sketched above are discussed in the literature. We will briefly mention here only a few of them. The first extension is to consider a priority relation among rules. This means that in each region a strict partial order relation on the set of rules from this region is given –then, a rule can be chosen (to process a multiset of objects) in a given step only if no rule of a higher priority is applicable. Another useful “control device” is the possibility to modify the membrane permeability. Thus, a membrane can be made thinner (action δ) or thicker (action τ). A membrane of normal thickness is dissolved by action δ (the objects of a dissolved membrane remain in the region surrounding it, while the rules are removed; the skin membrane cannot be dissolved), or made impermeable (no object can pass through such a membrane) by action τ. An impermeable membrane is returned to normal thickness (hence it is again permeable) by action δ. Many possibilities are offered by the communication commands. For instance, there are a number of ways of weakening the programming power provided by inj : to