DNA computing in vitro and in vivo

摘要

This is a review paper addressing two main aspects of DNA computing research : DNA computing in vitro (in the test tube) and in vivo (in a living organism). We describe the first successful in vitro DNA computing experiment [L.M. Adleman, Science 266 (1994) 1021--1024] which solved a mathematical problem, the Directed Hamiltonian Path Problem, solely by manipulation of DNA strands in test tubes. We then address DNA computing in vivo by presenting a model proposed by Head [in; G. Rozenberg, A. Salomaa (Eds.), Lindenmayer Systems, Springer, Berlin, 1991. pp. 371 --383] and also by Landweber and Kari [in f L. Kari, H. Rubin, D.H. Wood (Eds.), Biosystems, Vol. 52, Nos. 1 --3, Elsevier, Amsterdam, l999, pp. 3--13] and developed by Landweber and Kari [in f L.F Landweber, E. Winfree (Eds.), Evolution as Computation, Springer, Berlin, 19991, for the homologous recombinations that take place during gene rearrangement in ciliates. Results given by Kari, Kari and Landweber [in f J. Karhumaki, H. Maurer, G. Paun, G. Rozenberg (Eds.), Jewels are Forever, Springer, Berlin, l999, pp. 353--363] and Landweber and Kari [in: L.F Landweber, E. Winfree (Eds.), Evolution as Computation, Springer, Berlin, 1999] have shown that a generalization of this model that assumes context-controlled recombinations has universal computational power. We review results obtained by Kari and Kari [in : Words, Sequences, Languages : Where Computer Science, Biology and Linguistics Meet, Kluwer Academic Publishers, The Netherlands, in press] on properties of context-free recombinations and characterize the languages generated by context-free recombination systems. As a corollary, we show [J. Kari, L. Kari, in f Words, Sequences, Languages f Where Computer Science, Biology and Linguistics Meet, Kluwer Academic Publishers, The Netherlands, in press], that context-free recombinations are computationally weak, being able to generate only regular languages.