RNA-Editing with Combined Insertion and Deletion Preserves Regularity

Scientific Annals of Computer Science

article

E.P. de Vink¹  H. Zantema²  D. Bošnački³ 

[1] Department of Mathematics and Computer Science, Technische Universiteit Eindhoven and Centrum Wiskunde en Informatica;Department of Mathematics and Computer Science, Technische Universiteit Eindhoven and Institute for Computing and Information Sciences, Radboud University Nijmegen.;Department of Mathematics and Computer Science and Department of Biomedical Engineering, Technische Universiteit Eindhoven.

关键词: RNA editing;    string rewriting;    guided insertion/deletion;    guided rewriting;    regular languages;   

DOI  :  10.7561/SACS.2013.1.39

来源: Alexandru Ioan Cuza University of Iasi

【 摘 要 】

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.

【 授权许可】

CC BY-ND