Duplications and Pseudo-Duplications
Da-Jung Cho, Yo-Sub Han, Hwee Kim, Alexandros Palioudakis and Kai Salomaa
A duplication is one of the basic phenomena that occur in molecular evolution on a biological sequence. A duplication on a string is a process of copying a substring of the string—Given w = x1x2x3, a duplication of w is x1x2x2x3,. We define k-pseudo-duplication of a string w to be a set of all strings obtained from w by inserting after a substring u of w another substring u’ such that the edit distance between u and u’ is at most k. We consider duplication, k-pseudo-duplication and reverseduplication as operations on formal languages. First, we demonstrate that regular languages and context-free languages are not closed under the duplication, k-pseudo-duplication and reverse-duplication operations. Second, we show that context-sensitive languages are closed under duplication, pseudo-duplication and reverse-duplication. Last, we present the necessary and sufficient number of states that a nondeterministic finite automaton needs to recognize all duplications of a string with respect to the string length.
Keywords: Bio-inspired operations, duplication, formal languages, closure properties