Published in Volume XXIII, Issue 1, 2013, pages 39-73, doi: 10.7561/SACS.2013.1.39
Authors: E.P. de Vink, H. Zantema, D. Bošnački
Abstract
We consider two elementary forms of string rewriting called guided insertion/deletion and guided rewriting. The original strings are modified depending on the match with a given set of auxiliary strings, called guides. Guided insertion/deletion considers matching of a string and a guide with respect to a specific correspondence of strings. Guided rewriting considers matching of a string and a guide with respect to an equivalence relation on the alphabet. Guided insertion/deletion is inspired by {RNA}-editing, a biological process by which the original genetic information stored in DNA is modified before its final expression. The formalism here allows for simultaneous insertion and deletion of string elements. Guided rewriting, based on a letter-to-letter relation, is technically more appealing than guided insertion/deletion. We prove that guided rewriting preserves regularity: for every regular language its closure under guided rewriting is regular too. In the proof we will rely on the auxiliary notion of a slice sequence. We establish a correspondence of slice sequences and guide rewrite sequences. Because of their left-to-right nature, slice sequences are more convenient to deal with than guided rewrite sequences in the construction of the finite automata that we encounter in the proofs of regularity. Based on the result for guided rewriting we establish that guided insertion/deletion preserves regularity as well.
Full Text (PDF)References
[1] J.D. Alfonzo, O. Thiemann, and L. Simpson. The mechanism of U insertion/deletion RNA editing in kinetoplastid mitochondria. Nucleic Acids Research, 25(19):3751-3759, 1997. http://dx.doi.org/10.1093/nar/25.19.3571 .
[2] G.J. Arts and R. Benne. Mechanism and evolution of RNA editing in kinetoplastida. Biochimica et Biophysica Acta, 1307(1):39-54, 1996. http://dx.doi.org/10.1016/0167-4781(96)00021-8 .
[3] R. Benne, J. van de Burg, J. Brakenhoff, P. Sloof, J. van Boom, and M. Tromp. Major transcript of the frameshifted coxii gene from Trypanosome Mitochondria contains four nucleotides that are not encoded in the DNA. Cell, 46(6):819-826, 1986. http://dx.doi.org/10.1016/0092-8674(86)90063-2 .
[4] F. Biegler, M.J. Burrell, and M. Daley. Regulated RNA rewriting: Modelling RNA editing with guided insertion. Theoretical Computer Science, 387(2):103-112, 2007. http://dx.doi.org/10.1016/j.tcs.2007.07.030 .
[5] S. Binder and A. Brennicke. Gene expression in plant mitochondria: Transcriptional and post-transcriptional control. Philosophical Transactions of the Royal Society B: Biological Sciences, 358(1429):181-188, 2003. http://dx.doi.org/10.1098/rstb.2002.1179 .
[6] B. Blum, N. Bakalara, and L. Simpson. A model for RNA editing in kinetoplastid mitochondria: RNA molecules transcribed from maxicircle DNA provide the edited information. Cell, 60(2):189-198, 1990. http://dx.doi.org/10.1016/0092-8674(90)90735-W .
[7] J. van Engelen. Guided rewriting in families of languages. Technical Report 2012-2013-12, LIACS, July 2013. 16pp .
[8] X.Z. Fu, H. Wang, W. Harrison, and R. Harrison. RNA pseudoknot prediction using term rewriting. In Proceedings of BIBE’05, pages 169-176. IEEE Computer Society, 2005. http://dx.doi.org/10.1109/BIBE.2005.50 .
[9] T. Head. Formal language theory and DNA: an analysis of the generative capacity of specific recombinant behaviors. Bulletin of Mathematical Biology, 49(6):737-759, 1987. http://dx.doi.org/10.1007/BF02481771 .
[10] D. Hofbauer and J. Waldmann. Deleting string rewriting systems preserve regularity. Theoretical Computer Science, 327(3):301-317, 2004. http://dx.doi.org/10.1016/j.tcs.2004.04.009 .
[11] H.J. Hoogeboom. Private communication, 2013. [12] K. Cullik II and T. Harju. Splicing semigroups and dominoes and DNA. Discrete Applied Mathematics, 31(3):261-271, 1991. http://dx.doi.org/10.1016/0166-218X(91)90054-Z .
[13] P. Leupold. On regularity-preservation by string-rewriting systems. In C. Martín-Vide, F. Otto, and H. Fernau, editors, Proceedings of LATA’08, pages 345-356. LNCS 5196, 2008. http://dx.doi.org/10.1007/978-3-540-88282-4_32 .
[14] M. Margenstern, G. Paun, Y. Rogozhin, and S. Verlan. Context-free insertion-deletion systems. Theoretical Computer Science, 330(2):339- 348, 2005. http://dx.doi.org/10.1016/j.tcs.2004.06.031 .
[15] D. Pixton. Regularity of splicing languages. Discrete Applied Mathe- matics, 69(1-2):101-124, 1996. http://dx.doi.org/10.1016/0166-218X(95)00079-7 .
[16] G. Rozenberg and A. Salomaa, editors. Handbook of Formal Languages: Word, Language, Grammar. Springer, 1997 .
[17] J. Skarda, N. Amariglio, and G. Rechavi. RNA editing in human cancer: Review. APMIS, 117(8):551-557, 2009. http://dx.doi.org/10.1111/j.1600-0463 .
2009.02505.x. [18] H. van der Spek, G.J. Arts, R.R. Zwaal, J. van den Burg, P. Sloof, and R. Benne. Conserved genes encode guide RNAs in mitochondria of Crithidia fasciculata. EMBO, 10(5):1217-1224, 1991 .
[19] K. Stuart, T.E. Allen, S. Heidmann, and S.D. Seiwert. RNA editing in kinteoplastid protozoa. Microbiology and Molecular Biology Reviews, 61(1):105-120, 1997 .
[20] A. Takahara and T. Yokomori. On the computational power of insertion- deletion systems. Natural Computing, 2(4):321-336, 2003. http://dx.doi.org/10.1023/B:NACO.0000006769.27984.23 .
[21] H. Zantema. Complexity of guided insertion-deletion in RNA-editing. In A.-H. Dediu, H. Fernau, and C. Martín-Vide, editors, Proceed- ings of LATA’10, pages 608-619. LNCS 6031, 2010. http://dx.doi.org/10.1007/978-3-642-13089-2_51 .
Bibtex
@article{sacscuza:de2013rwciadpr,
title={RNA-Editing with Combined Insertion and Deletion Preserves Regularity},
author={E.P. de Vink and H. Zantema and D. Bošnački},
journal={Scientific Annals of Computer Science},
volume={23},
number={1},
organization={``A.I. Cuza'' University, Iasi, Romania},
year={2013},
pages={39--73},
doi={10.7561/SACS.2013.1.39},
publisher={``A.I. Cuza'' University Press}
}