Patterns and Distances in Words Related to DNA Rearrangement

• Autorzy: Jonoska N. , Nabergall L. , Saito M.

Identyfikatory

DOI

10.3233/FI-2017-1563

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

patterns in words; pattern distance; double occurrence words; indices; scrambled genome

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 154, nr 1/4
• Strony: 225--238
• Opis fizyczny: Bibliogr. 26 poz., rys.

Twórcy

autor

Jonoska N.

• University of South Florida, Tampa FL, 33620 USA

autor

Nabergall L.

• University of South Florida, Tampa FL, 33620 USA

autor

Saito M.

• University of South Florida, Tampa FL, 33620 USA

Bibliografia

• [1] Abrahamson K. Generalized string matching, SIAM Journal of Computing, 1987;16(6):1039–1051. doi:10.1137/0216067.
• [2] Amir A, and Nor I. Generalized function matching, Journal of Discrete Algorithms, 2007;5(3):514–523. URL https://doi.org/10.1016/j.jda.2006.10.001.
• [3] Angluin D. Finding patterns common to a set of strings, Journal of Computer and System Sciences, 1980;21(1):46–62. URL https://doi.org/10.1016/0022-0000(80)90041-0.
• [4] Apostolico A, and Galil Z. (Eds.) Pattern Matching Algorithms, Oxford University Press, Oxford (1997). ISBN:0-19-511367-5.
• [5] Baker BS. A theory of parameterized pattern matching: algorithms and applications, Proc. 25th Annual ACM Symposium on the Theory of Computation, ACM New York, NY, USA, 1993 pp. 71–80. doi:10.1145/167088.167115.
• [6] Baker KA, McNulty GF, and Taylor W. Growth problems for avoidable words, Theoretical Computer Science, 1989;69:319–345. URL https://doi.org/10.1016/0304-3975(89)90071-6.
• [7] Bean D, Ehrenfeucht A, and McNulty G. Avoidable patterns in strings of symbols, Pacific Journal of Mathematics, 1979;85:261–294. URL http://projecteuclid.org/euclid.pjm/1102783913.
• [8] Burns J, Dolzhenko E, Jonoska N, Muche T, and Saito M. Polygonal hamiltonian paths in rigid 4-regular graphs and DNA assembly, Discrete Applied Mathematics, 2013;161:1378–1394.
• [9] Burns J, Kukushkin D, Chen X, Landweber LF, Saito M, and 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.
• [10] Cassaigne J. Unavoidable binary patterns, Acta Informatica, 1993;30(4):385–395. doi:10.1007/BF01209712.
• [11] Chen X, Bracht JR, Goldman AD, Dolzhenko E, Clay DM, Swart EC, Perlman DH, Doak TG, Stuart A, Amemiya CT, Sebra RP, and Landweber LF. The architecture of a scrambled genome reveals massive levels of genomic rearrangement during development, Cell, 2014;158(5):1187–1198. doi:10.1016/j.cell.2014.07.034.
• [12] Choffrut C, and Karhumäki J. Combinatorics of Words, Handbook of Formal Languages, (Eds. G. Rozenberg, A. Salomaa) Springer–Verlag, 1997 pp. 329–438. doi:10.1007/978-3-642-59136-5_6.
• [13] Currie JD. Open problems in pattern avoidance, American Mathematical Monthly, 1993;100(8):790–793. doi:10.2307/2324790.
• [14] Ehrenfeucht A, Harju T, Petre L, Prescott DM, and Rozenberg G. Computing in Living Cells, Springer 2005. doi:10.1007/978-3-662-06371-2.
• [15] Fernau H, and Schmid ML. Pattern matching with variables: a multivariate complexity analysis, Information and Computation, 2015;242:287–305. URL https://doi.org/10.1016/j.ic.2015.03.006.
• [16] Fernau H, Manea F, Mercas¸ R, and Schmid ML. Pattern matching with variables: fast algorithms and new hardness results, Proceedings of the 32nd Symposium on Theoretical Aspects of Computer Science, 2015;30:302–315. doi:10.4230/LIPIcs.STACS.2015.302.
• [17] Knuth DE, Morris JH, and Pratt VR. Fast pattern matching in strings, SIAM Journal of Computing, 1977;6(2):323–350. URL https://doi.org/10.1137/0206024.
• [18] Levenshtein V. Binary codes capable of correcting spurious insertions and deletions of ones, Problems of Inference Transmission, 1965;1:8–17.
• [19] Lothaire M. Algebraic Combinatorics onWords, Encyclopedia of Mathematics and its Applications, Cambridge University Press, 2002. URL https://doi.org/10.1017/CBO9781107326019.
• [20] Nabergall L. Patterns in Words Related to DNA Rearrangements, Masters thesis, University of South Florida, Tampa FL, 2017.
• [21] Needleman S, and 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. URL https://doi.org/10.1016/0022-2836(70)90057-4.
• [22] Ng YK, and Shinohara T. Developments from enquiries into the learnability of the pattern languages from positive data, Theoretical Computer Science, 2008;397(1-3):150–165. URL https://doi.org/10.1016/j.tcs.2008.02.028.
• [23] Reidenbach D, and Schmid ML. Patterns with bounded treewidth, Information and Computation, 2014; 239:87–99. URL https://doi.org/10.1016/j.ic.2014.08.010.
• [24] Sankoff D, and Kruskal J. Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison, Addison-Wesley (1983).
• [25] Schmidt U. Avoidable patterns on two letters, Theoretical Computer Science, 1989;63(1):1–17. URL https://doi.org/10.1016/0304-3975(89)90064-9.
• [26] Zimin AI. Blocking sets of terms, Matematicheskii Sbornik, 1982;119(161):363–375. URL http://mi.mathnet.ru/eng/msb/v161/i3/p363.