×

Formal systems for gene assembly in ciliates. (English) Zbl 1063.68054

Summary: DNA processing in ciliates, a very ancient group of organisms, is among the most sophisticated DNA processing in living organisms. It has a quite clear computational structure and even uses explicitly the linked list data structure! Particularly interesting from the computational point of view is the process of gene assembly from its micronuclear to its macronuclear form. We investigate here the string rewriting and the graph rewriting models of this process, involving three molecular operations, which together form a universal set of operations in the sense that they can assembly any macronuclear gene from its micronuclear form. In particular we prove that although the graph rewriting system is more “abstract” than the string rewriting system, no “essential information” is lost, in the sense that one can translate assembly strategies from one system into the other.

MSC:

68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68Q42 Grammars and rewriting systems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bouchet, A., Graphic presentations of isotropic systems, J. Combin. Theory Ser B, 45, 58-76 (1988) · Zbl 0662.05014
[2] Bouchet, A., Circle graph obstructions, J. Combin. Theory Ser B, 60, 107-144 (1994) · Zbl 0793.05116
[3] (Condon, A.; Rozenberg, G., Proc. 6th Internat. Meeting on DNA Based Computers, Lecture Notes in Computer Science (2000), Springer: Springer Berlin)
[4] Ehrenfeucht, A.; Petre, I.; Prescott, D. M.; Rozenberg, G., Universal and simple operations for gene assembly in ciliates, (Martin-Vide, C.; Mitrana, V., Where Mathematics, Computer Science, Linguistics and Biology Meet (2001), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht/Boston), 329-342 · Zbl 1007.68067
[5] A. Ehrenfeucht, I. Petre, D.M. Prescott, G. Rozenberg, String and graph reduction systems for gene assembly in ciliates, to appear in Math. Struct. in Comput. Sci., 2001.; A. Ehrenfeucht, I. Petre, D.M. Prescott, G. Rozenberg, String and graph reduction systems for gene assembly in ciliates, to appear in Math. Struct. in Comput. Sci., 2001. · Zbl 1007.68127
[6] Ehrenfeucht, A.; Prescott, D. M.; Rozenberg, G., Computational aspects of gene (un)scrambling in ciliates, (Landweber, L.; Winfree, E., Evolution as Computation (2000), Springer: Springer Berlin), 45-86
[7] Gasse, E., A proof of a circle graph characterization, Discrete Math., 173, 277-283 (1997) · Zbl 0882.05111
[8] Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press: Academic Press New York · Zbl 0541.05054
[9] L.F. Landweber, L. Kari, The evolution of cellular computing: nature’s solution to a computational problem, Proc. 4th DIMACS Meeting on DNA Based Computers, Philadelphia, 1998, pp. 3-15.; L.F. Landweber, L. Kari, The evolution of cellular computing: nature’s solution to a computational problem, Proc. 4th DIMACS Meeting on DNA Based Computers, Philadelphia, 1998, pp. 3-15.
[10] L.F. Landweber, L. Kari, Universal molecular computation in ciliates, in: L. Landweber, E. Winfree, (Eds.), Evolution as Computation, Springer Verlag. Berlin, Heidelberg, to appear, 2001.; L.F. Landweber, L. Kari, Universal molecular computation in ciliates, in: L. Landweber, E. Winfree, (Eds.), Evolution as Computation, Springer Verlag. Berlin, Heidelberg, to appear, 2001. · Zbl 0946.68044
[11] Paun, G.; Rozenberg, G.; Salomaa, A., DNA Computing (1998), Springer: Springer Berlin · Zbl 0940.68053
[12] D.M. Prescott, A. Ehrenfeucht, G. Rozenberg, Molecular operations for DNA processing in hypotrichous ciliates, Manuscript, 1999.; D.M. Prescott, A. Ehrenfeucht, G. Rozenberg, Molecular operations for DNA processing in hypotrichous ciliates, Manuscript, 1999.
[13] W.D. Smith, DNA computers in vitro and vivo, Proc. 1st DIMACS Meeting on DNA Based Computers, Princeton, 1995, pp. 121-186.; W.D. Smith, DNA computers in vitro and vivo, Proc. 1st DIMACS Meeting on DNA Based Computers, Princeton, 1995, pp. 121-186.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.