Insertions on Double Occurrence Words Motivated by DNA Rearrangement

Speaker:  Margherita Maria Ferrari - Department of Mathematics and Statistics University of South Florida (USF)
  Friday, May 29, 2020 at 3:30 PM le persone interessate posso richiedere il link via email al Prof.Mazzuoccolo
A double occurence word (DOW) is a word in which every symbol appears exactly twice; two DOWs are equivalent if one is a symbol-to-symbol image of the other. We consider the so called repeat pattern (αα) and the return pattern (ααR), with gaps allowed between the α’s. These patterns generalize square and palindromic factors of DOWs, respectively. DOWs and repeat/return words have been used in studies of DNA rearrangements in certain species of ciliates. Motivated by the genome architecture of the ciliate Oxytricha trifallax, we introduce a notion of inserting repeat/return words into DOWs and study how two distinct insertions into the same word can produce equivalent DOWs. Given a DOW w, we characterize the structure of w which allows two distinct insertions to yield equivalent DOWs. This characterization depends on the locations of the insertions and on the length of the inserted repeat/return words and implies that when one inserted word is a repeat word and the other is a return word, then both words must be trivial (i.e., have only one symbol). The characterization also introduces a method to generate families of words recursively.

Programme Director
Giuseppe Mazzuoccolo

Publication date
May 21, 2020