Biocomputation in Ciliates - Cellular Computing - page 215

biological process, it awaits rigorous testing by the tools of molecular genetics.
The model in its present form is capable of universal computation. This hints at
future directions and the use of ciliates as model systems for exploring cellular
computation.
Acknowledgments This research was partially supported by the Natural Sciences and
Engineering Research Council of Canada grant R2824AO1 to L.K. and National Insti-
tute of General Medical Sciences grant GM59708 to L.F.L. We thank Mark Daley for
comments and Jeremy Newton-Smith with help in preparing the manuscript.
References
[1] E. Csuhaj-Varju, R. Freund, L. Kari, and G. Paun. DNA computing based on
splicing: universality results. In L. Hunter and T. Klein, editors, Proceedings of 1st
Pacific Symposium on Biocomputing , pages 179-190. World Scientific Publishing,
Singapore, 1996.
[2] M. Daley. Complexity of gene unscrambling, 2002. Unpublished manuscript.
[3] T. Head. Formal language theory and DNA: an analysis of the generative capacity
of specific recombinant behaviors. Bull. Math. Biol. , 49:737-759, 1987.
[4] T. Head. Splicing schemes and DNA. In G. Rozenberg and A. Salomaa, editors,
Lindenmayer Systems , pages 371-383. Springer-Verlag, Berlin, 1991.
[5] T. Head and G. Paun, and D. Pixton. Language theory and molecular genetics. In
G. Rozenberg and A. Salomaa, editors, Handbook of Formal Languages , vol. 2,
pages 295-358. Springer-Verlag, Berlin, 1997.
[6] J. Kari and L. Kari. Context-free recombinations. In C. Martin-Vide and V. Mitrana,
editors, Where Mathematics, Computer Science, Linguistics and Biology Meet ,
pages 361-375. Kluwer, Dordrecht, The Netherlands, 2001.
[7] L. Kari, J. Kari, and L. Landweber. Reversible molecular computation in ciliates. In
J. Karhumaki, H. Maurer, G. Paun, and G. Rozenberg, editors, Jewels are Forever ,
pages 353-363. Springer-Verlag, Berlin, 1999.
[8] L. F. Landweber and L. Kari. The evolution of cellular computing: nature's solution
to a computational problem. BioSystems , 52(1-3):3-13, 1999.
[9] L. F. Landweber and L. Kari. Universal molecular computation in ciliates. In
L. Landweber and E. Winfree, editors, Evolution as Computation . Springer-Verlag,
Berlin, 2002.
[10] L. F. Landweber, T. Kuo, and E. Curtis. Evolution and assembly of an extremely
scrambled gene. Proc. Natl. Acad. Sci. , 97(7):3298-3303, 2000.
[11] E. Meyer and S. Duharcourt. Epigenetic programming of developmental genome
rearrangements in ciliates. Cell , 87:9-12, 1996.
[12] J. L. Mitcham, A. J. Lynn, and D. M. Prescott. Analysis of a scrambled gene:
the gene encoding α -telomere-binding protein in Oxytricha nova . Genes Devel. ,
6:788-800, 1992.
[13] G. Paun. On the power of the splicing operation. Int. J. Comp. Math , 59:27-35,
1995.