Affiliations: [a] University of South Florida, Tampa FL, 33620 USA. jonoska@mail.usf.edu | [b] University of South Florida, Tampa FL, 33620 USA. lnabergall@mail.usf.edu | [c] University of South Florida, Tampa FL, 33620 USA. saito@usf.edu
Correspondence:
[†]
Address for correspondence: Department of Mathematics and Statistics, University of South Florida, Tampa FL, 33620 USA
Note: [*] Partially supported by National Science Foundation CCF-1526485 and National Institutes of Health R01GM109459.
Note: [‡] Partially supported by National Institutes of Health R01GM109459.
Abstract: We initiate studies of patterns in words that appear as subwords (not necessarily factors) of words. A pattern is a string of variables, and we say that a pattern appears in a word if each variable can be morphically mapped to a factor in the word. We define pattern indices and distances between two words relative to a given set of patterns. The distance is defined as the minimal number of ‘pattern reductions’ that transfer one word into another. Motivated by patterns detected in certain scrambled ciliate genomes, we focus on double occurrence words (words where every symbol appears twice) and patterns in those words. Specifically, we show that in double occurrence words the distance relative to patterns αα (repeat words) and ααR (return words) is computable. We also compare some pattern indices of highly scrambled genes in O. trifallax relative to random sequences.
