DNA computing in vitro and in vivo

This is a review paper addressing two main aspects of DNA computing researc h: DNA computing in vitro (in the test tube) and in vivo (in a living organ ism). We describe the first successful in vitro DNA computing experiment [L .M. Adleman, Science 266 (1994) 1021-1024] which solved a mathematical prob lem, the Directed Hamiltonian Path Problem, solely by manipulation of DNA s trands in test tubes. We then address DNA computing in vivo by presenting a model proposed by Head Gin: G. Rozenberg, A. Salomaa (Eds.), Lindenmayer S ystems, Springer, Berlin, 1991,pp. 371-383] and also by Landweber and Kari [in: L. Kari, I-I. Rubin, D.H. Wood (Eds.), Biosystems, Vol. 52, Nos. 1-3, Elsevier, Amsterdam, 1999, pp. 3-13] and developed by Landweber and Kari [i n: L.F Landweber, E. Winfree (Eds.), Evolution as Computation, Springer, Be rlin, 1999], for the homologous recombinations that take place during gene rearrangement in ciliates. Results given by Kari, Kari and Landweber [in: J . Karhumaki, H. Maurer. G. Paun, G. Rozenberg (Eds.), Jewels are Forever, S pringer, Berlin, 1999, pp. 353-363] and Landweber and Kari [in: L.F Landweb er, E. Winfree (Eds.), Evolution as Computation, Springer, Berlin, 1999] ha ve shown that a generalization of this model that assumes context-controlle d recombinations has universal computational power. We review results obtai ned by Kari and Kari [in: Words, Sequences, Languages: Where Computer Scien ce, Biology and Linguistics Meet, Kluwer Academic Publishers, The Netherlan ds, in press] on properties of context-free recombinations and characterize the languages generated by context-free recombination systems. As a coroll ary, we show [J. Kari, L. Kari, in: Words, Sequences, Languages: Where Comp uter Science, Biology and Linguistics Meet, Kluwer Academic Publishers, The Netherlands, in press], that context-free recombinations are computational ly weak, being able to generate only regular languages. (C) 2001 Elsevier S cience B.V. All rights reserved.