Insertions Yielding Equivalent Double Occurrence Words

• Autorzy: Cruz Daniel A. , Ferrari Margherita Maria , Jonoska Nataša , Nabergall Lukas , Saito Masahico

Identyfikatory

DOI

10.3233/FI-2020-1875

• Języki publikacji: EN

Abstrakty

EN

A double occurrence 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. 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.

Słowa kluczowe

EN

vocabulary; families

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2020
• Tom: Vol. 171, nr 1-4
• Strony: 113--132
• Opis fizyczny: Bibliogr. 19 poz., rys., tab.

Twórcy

autor

Cruz Daniel A.

• University of South Florida, Tampa FL, 33620, USA

autor

Ferrari Margherita Maria

• University of South Florida, Tampa FL, 33620, USA

autor

Jonoska Nataša

• University of South Florida, Tampa FL, 33620, USA

autor

Nabergall Lukas

• University of Waterloo, Waterloo ON, N2L 3G1, Canada

autor

Saito Masahico

• University of South Florida, Tampa FL, 33620, USA

Bibliografia

• [1] Arredondo RC. Properties of graphs used to model DNA recombination. Graduate Theses and Dissertations, University of South Florida. 2014.
• [2] Braun J, Nabergall L, Neme R, Landweber LF, Saito M, Jonoska N. Russian doll genes and complex chromosome rearrangements in Oxytricha trifallax. G3: Genes, Genomes, Genetics. 2018; 8(5):1669-1674. doi:10.1534/g3.118.200176.
• [3] Burns J, Dolzhenko E, Jonoska N, Muche T, Saito M. Four-regular graphs with rigid vertices associated to DNA recombination. Discrete Applied Mathematics. 2013; 161(10-11):1378-1394. doi:10.1016/j.dam.2013.01.003.
• [4] Burns J, Jonoska N, Saito M. Genus ranges of chord diagrams. Journal of Knot Theory and its Ramifications. 2015; 24(4):1550022, doi:10.1142/S0218216515500224.
• [5] Burns J, Kukushkin D, Chen X, Landweber LF, Saito M, Jonoska N. Recurring patterns among scrambled genes in the encrypted genome of the ciliate Oxytricha trifallax. Journal of Theoretical Biology. 2016; 410:171-180. doi:10.1016/j.jtbi.2016.08.038.
• [6] Chang WJ, Bryson PD, Liang H, Shin MK, Landweber LF. The evolutionary origin of a complex scrambled gene. Proceedings of the National Academy of Sciences of the United States of America. 2005; 102(42):15149-15154. doi:10.1073/pnas.0507682102.
• [7] Choffrut C, Karhumäki J. Combinatorics of words. Handbook of Formal Languages, Springer Berlin/Heidelberg. 1997; 329-438. doi:10.1007/978-3-642-59136-5_6.
• [8] Courcelle B. Circle graphs and monadic second-order logic. Journal of Applied Logic. 2008; 6(3):416-442. doi:10.1016/j.jal.2007.05.001.
• [9] Ehrenfeucht A, Harju T, Petre I, Prescott DM, Rozenberg G. Computation in living cells: gene assembly in ciliates. Natural Computing Series, Springer Berlin/Heidelberg. 2003. doi:10.1007/978-3-662-06371-2.
• [10] Gibson A. Homotopy invariants of Gauss words. Mathematische Annalen. 2011; 349(4):871-887. doi:10.1007/s00208-010-0536-0.
• [11] Jonoska N, Nabergall L, Saito M. Patterns and distances in words related to DNA rearrangement. Fundamenta Informaticae. 2017; 154(1-4):225-238. doi:10.3233/FI-2017-1563.
• [12] Levenshtein V. Binary codes capable of correcting spurious insertions and deletions of ones. Russian Problemy Peredachi Informatsii. 1965; 1:12-25.
• [13] Lothaire M. Algebraic combinatorics on words. Cambridge University Press. 2002. doi:10.1017/CBO9781107326019.
• [14] Lyndon RC, Schützenberger MP. The equation aM = bNcP in a free group. Michigan Math. J. 1962; 9(4):289-298. doi:10.1307/mmj/1028998766.
• [15] Needleman S, Wunsch C. A general method applicable to the search for similarities in the amino acid sequences of two proteins. Journal of Molecular Biology. 1970; 48(3):444-453. doi:10.1016/0022-2836(70)90057-4.
• [16] Sankoff D, Kruskal J. Time Warps, String Edits, and Macromolecules. The Theory and Practice of Sequence Comparison, Reading. 1983.
• [17] Shtylla B, Traldi L, Zulli L. On the realization of double occurrence words. Discrete Mathematics. 2009; 309(6):1769-1773. doi:10.1016/j.disc.2008.02.035.
• [18] Stein PR. On a class of linked diagrams, I. Enumeration. Journal of Combinatorial Theory, Series A. 1978; 24(3):357-366. doi:10.1016/0097-3165(78)90065-1.
• [19] Turaev V. Virtual strings, Annales de l’Institut Fourier. 2004; 54(7):2455-2525. doi:10.5802/aif.2086.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).