×

On some operations on strings suggested by gene assembly in ciliates. (English) Zbl 1021.68039

Summary: We define three operations on strings and languages suggested by the process of gene assembly in hypotrichous ciliates. This process is considered to be a prime example of DNA computing in vivo. This paper is devoted to some computational aspects of these operations from a formal language point of view. The closure of the classes of regular and context-free languages under these operations is settled. Then, we consider the \(ld\)-macronuclear language of a given language \(L\), which consists of all \(ld\)-macronuclear strings obtained from the strings of \(L\) by iteratively applying the loop-direct repeat-excision. Finally, we discuss some open problems and further directions of research.

MSC:

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

References:

[1] Dassow, J. and Mitrana, V., “On Some Operations Suggested by Genome Evolution,”in Proc. of Second Pacific Symposium on Biocomputing (Altman, R. B., Dunker, A. K., Hunter, L. and Klein, T., eds.), World Scientific, pp. 97-108, 1997.
[2] Dassow, J. and Pâun, Gh., “Remarks on Operations Suggested by Mutations in Genomes,”Fundam. Inform. 36, pp. 183-200, 1998. · Zbl 0930.68078
[3] Dassow, J., Mitrana, V. and Salomaa, A., “Context-free Evolutionary Grammars and the Structural Language of Nucleic Acids,”BioSystems, 43, pp. 169-177, 1997. · doi:10.1016/S0303-2647(97)00036-1
[4] Ehrenfeucht, A.; Prescott, D. M.; Rozenberg, G.; Landweber, L. (ed.); Winfree, E. (ed.), Computational Aspects of Gene (un)Scrambling in Cilitates, 45-86 (2001), Berlin
[5] Ehrenfeucht, A.; Petre, I.; Prescott, D. M.; Rozenberg, G.; Martín-Vide, C. (ed.); Mitrana, V. (ed.), Universal and Simple Operations for Gene Assembly in Ciliates, 329-343 (2000), Dordrecht
[6] Ehrenfeucht, A., Harju, T., Petre, I. and Rozenberg, G., “Patterns of Micronuclear Genes in Ciliates,”in Proc. of the 7th DIMACS meeting on DNA based computers, Tampa, Florida, pp. 33-42, 2001. · Zbl 1065.68541
[7] Knuth, D. E., Morris, J. H. and Pratt, V. R., “Fast Pattern Matching in Strings,”SIAM J. Comput., 6, pp. 323-350, 1977. · Zbl 0372.68005 · doi:10.1137/0206024
[8] Landweber, L. F. and Kari, L., “The Evolution of Cellular Computing: Nature”s Solution to a Computational Problem,“<Emphasis Type=”Italic”>in Proc. of the 4th Meeting on DNA Based Computers. BioSystems (special issue) 52, pp. 3-13, 1999. · doi:10.1016/S0303-2647(99)00027-1
[9] Landweber, L. F. and Kari, L., “Universal Molecular Computation in Ciliates,” to appear inEvolution as Computation (Landweber, L. and Winfree, E., eds.), Springer Verlag, Berlin. · Zbl 0946.68044
[10] Prescott, D. M., “Genome Gymnastics: Unique Modes of DNA Evolution and Processing in Ciliates,”Nature Reviews Genetics, 1, 3, pp. 191-198, 2000. · doi:10.1038/35042057
[11] Handbook of Formal Languages, 3 (Rozenberg, G. and Salomaa, A., eds.), Springer-Verlag, Berlin, 1997. · Zbl 0866.68057
[12] Searls, D. B., “The Computational Linguistics of Biological Sequences,”Artificial Intelligence and Molecular Biology (Hunter, L., ed.), AAAI Press, The MIT Press, pp. 47-120, 1993.
[13] Therman, E. and Susman, M.,Human Chromosomes, Structure, Behavior, and Effects, Springer-Verlag, 1993. · doi:10.1007/978-1-4684-0529-3
[14] Yokomori, T. and Kobayashi, S., “DNA Evolutionary Linguistics and RNA Structure Modelling: a Computational Approach,”in IEEE Symp. on Intelligence in Neural and Biological Systems, IEEE Computer Society Press, pp. 38-45, 1995.
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.