Closure and decidability properties of some language classes with respect to ciliate bio-operations. (English) Zbl 1060.68060
Summary: The process of gene unscrambling in ciliates (a type of unicellular protozoa), which accomplishes the difficult task of re-arranging gene segments in the correct order and deleting non-coding sequences from an “encrypted” version of a DNA strand, has been modeled and studied so far from the point of view of the computational power of the DNA bio-operations involved. Here we concentrate on a different aspect of the process, by considering only the linear version of the bio-operations, that do not involve thus any circular strands, and by studying the resulting formal operations from a purely language-theoretic point of view. We investigate closure properties of language families under the mentioned bio-operations and study language equations involving them. We also study the decidability of the existence of solutions to equations of the form \(L \diamond Y=R\), \(X \diamond L=R\) where \(L\) and \(R\) are given languages, \(X\) and \(Y\) are unknowns, and \(\diamond\) signifies one of the defined bio-operations.
MSC:
| 68Q45 | Formal languages and automata |
| 92D10 | Genetics and epigenetics |
| 92D20 | Protein sequences, DNA sequences |
Keywords:
unscrambling in ciliatesReferences:
| [1] | Baker, B. S.; Book, R. V., Reversal-bounded multipushdown machines, J. Comput. System Sci., 8, 315-332 (1974) · Zbl 0309.68043 |
| [2] | M. Daley, L. Kari, Some properties of ciliate bio-operations, Preproc. 6th Internat. Conf. on Developments in Language Theory, 2002, pp. 122-139.; M. Daley, L. Kari, Some properties of ciliate bio-operations, Preproc. 6th Internat. Conf. on Developments in Language Theory, 2002, pp. 122-139. · Zbl 1015.68113 |
| [3] | Dassow, J.; Mitrana, V.; Salomaa, A., Operations and language generating devices suggested by the genome evolution, Theoret. Comput. Sci., 270, 701-738 (2002) · Zbl 0992.68129 |
| [4] | Ehrenfeucht, A.; Prescott, D. M.; Rozenberg, G., Computational aspects of gene (un)scrambling in ciliates, (Landweber, L. F.; Winfree, E., Evolution as Computation (2001), Springer: Springer Berlin, Heidelberg), 45-86 |
| [5] | Freund, R.; Martin-Vide, C.; Mitrana, V., On some operations on strings suggested by gene assembly in ciliates, New Gen. Comput., 20, 279-293 (2002) · Zbl 1021.68039 |
| [6] | Ginsburg, S., Algebraic and Automata-Theoretic Properties of Formal Languages (1975), North-Holland: North-Holland Amsterdam · Zbl 0325.68002 |
| [7] | T. Harju, O.H. Ibarra, J. Karhumaki, A. Salomaa, Some decision problems concerning semilinearity and commutation, in: J. Comput. System Sci. extended abstract has appeared in Proc. Twenty Eighth Internat. Colloq. 2002, Automata, Languages and Programming, 2001, pp. 579-590, to appear.; T. Harju, O.H. Ibarra, J. Karhumaki, A. Salomaa, Some decision problems concerning semilinearity and commutation, in: J. Comput. System Sci. extended abstract has appeared in Proc. Twenty Eighth Internat. Colloq. 2002, Automata, Languages and Programming, 2001, pp. 579-590, to appear. · Zbl 0986.68048 |
| [8] | Hopcroft, J. E.; Motwani, R.; Ullman, J. D., Introduction to Automata Theory, Languages, and Computation (2001), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0980.68066 |
| [9] | Ibarra, O. H., Reversal-bounded multicounter machines and their decision problems, J. Assoc. Comput. Mach., 25, 116-133 (1978) · Zbl 0365.68059 |
| [10] | L. Kari, L.F. Landweber, Computational power of gene rearrangement, in: E. Winfree, D. Gifford (Eds.), DNA5, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society, Vol. 54, 2000, pp. 207-216.; L. Kari, L.F. Landweber, Computational power of gene rearrangement, in: E. Winfree, D. Gifford (Eds.), DNA5, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society, Vol. 54, 2000, pp. 207-216. · Zbl 0971.68054 |
| [11] | Kari, L., On language equations with invertible operations, Theoret. Comput. Sci., 132, 129-150 (1994) · Zbl 0821.68075 |
| [12] | L.F. Landweber, L. Kari, The evolution of cellular computing: nature’s solutions to a computational problem, in: L. Kari, H. Rubin, D.H. Wood (Eds.), DNA4, BioSystems, Elsevier, Amsterdam, 1999, pp. 3-13.; L.F. Landweber, L. Kari, The evolution of cellular computing: nature’s solutions to a computational problem, in: L. Kari, H. Rubin, D.H. Wood (Eds.), DNA4, BioSystems, Elsevier, Amsterdam, 1999, pp. 3-13. |
| [13] | Landweber, L. F.; Kuo, T.; Curtis, E., Evolution and assembly of an extremely scrambled gene, Proc. Nat. Acad. Sci., 97, 7, 3298-3303 (2000) |
| [14] | Petre, I.; Ehrenfeucht, A.; Harju, T.; Rozenberg, G., Patterns of micronuclear genes in cilliates, (Jonoska, N.; Seeman, N., DNA7. DNA7, Lecture Notes in Computer Science, Vol. 2340 (2002), Springer: Springer Berlin), 279-289 · Zbl 1065.68541 |
| [15] | Prescott, D. M., Cutting, splicing, reordering, and elimination of DNA sequences in hypotrichous ciliates, BioEssays, 14, 5, 317-324 (1992) |
| [16] | Prescott, D. M., The unusual organization and processing of genomic DNA in hypotrichous ciliates, Trends in Genet., 8, 439-445 (1992) |
| [17] | Prescott, D. M., Genome gymnasticsUnique modes of DNA evolution and processing in ciliates, Nature Rev. Gen., 1, 191-198 (2000) |
| [18] | Prescott, D. M.; Ehrenfeucht, A.; Rozenberg, G., Molecular operations for DNA processing in hypotrichous ciliates, Eur. J. Protistol., 37, 241-260 (2001) |
| [19] | Salomaa, A., Formal Languages (1973), Academic Press: Academic Press New York · Zbl 0262.68025 |
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.
