×

Hairpin structures defined by DNA trajectories. (English) Zbl 1192.68407

Summary: We examine scattered hairpins, which are structures formed when a single strand of nucleotides folds into a partially hybridized stem and a loop. To specify different classes of hairpins, we use the concept of DNA trajectories, which allows precise descriptions of valid bonding patterns on the stem of the hairpin. DNA trajectories have previously been used to describe bonding between separate strands.
We are interested in the mathematical properties of scattered hairpins described by DNA trajectories. We examine the complexity of the set of hairpin-free words described by a set of DNA trajectories. In particular, we consider the closure properties of language classes under sets of DNA trajectories of differing complexity. We address decidability of recognition problems for hairpin structures.

MSC:

68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Cassaigne, J.: Motifs évitables et régularités dans les mots. Ph.D. thesis, Université Paris 6 (1994)
[2] Choffrut, C., Karhumäki, J.: Combinatorics on words. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, pp. 329–438. Springer, New York (1997)
[3] Domaratzki, M.: Trajectory-based embedding relations. Fund. Inf. 59(4), 349–363 (2004) · Zbl 1097.68107
[4] Domaratzki, M., Ibarra, O., Dang, Z.: Characterizing DNA bond shapes using trajectories. In: Developments in Language Theory. Lecture Notes in Computer Science, vol. 4036, pp. 180–191. Springer, New York (2006) · Zbl 1227.68052
[5] Entringer, R., Jackson, D., Schatz, J.: On nonrepetitive sequences. J. Comb. Theory. Ser. A 16, 159–164 (1974) · Zbl 0279.05001 · doi:10.1016/0097-3165(74)90041-7
[6] Fraenkel, A., Simpson, J.: How many squares must a binary sequence contain? Electon. J. Comb. 2, 2 (1995) · Zbl 0816.11007
[7] Harju, T., Karhumäki, J.: Morphisms. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, pp. 439–510. Springer, New York (1997)
[8] Jonoska, N., Mahalingam, K.: Languages of DNA based code words. In: Chen, J., Reif, J. (eds.) DNA Computing, 9th International Workshop on DNA Based Computers. Lecture Notes in Computer Science, vol. 2943, pp. 61–73. Springer, New York (2004) · Zbl 1098.68043
[9] Jonoska, N., Kephart, D., Mahalingam, K.: Generating DNA code words. Congr. Numer. 156, 99–110 (2002) · Zbl 1015.92016
[10] Kari, L., Konstantinidis, S., Sosík, P.: On properties of bond-free DNA languages. Theor. Comput. Sci. 334, 131–159 (2005) · Zbl 1080.68036 · doi:10.1016/j.tcs.2004.12.032
[11] Kari, L., Konstantinidis, S., Sosík, P., Thierrin, G.: On hairpin-free words and languages. In: Felice, C.D., Restivo, A. (eds.) Developments in Language Theory: 9th International Conference. Lecture Notes in Computer Science, vol. 3572, pp. 296–307. Springer, New York (2005) · Zbl 1132.68451
[12] Kari, L., Konstantinidis, S., Losseva, E., Sosík, P., Thierrin, G.: Hairpin structures in DNA words. In: Carbone, A., Pierce, N. (eds.) DNA Computing. Lecture Notes in Computer Science, vol. 3892, pp. 158–170. Springer, New York (2006) · Zbl 1234.68216
[13] Kari, L., Losseva, E., Konstantinidis, S., Sosík, P., Thierrin, G.: A formal language analysis of DNA hairpin structures. Fund. Inf. 71, 453–475 (2006) · Zbl 1096.68084
[14] Lothaire, M.: Combinatorics on Words. Addison-Wesley, Reading (1983) · Zbl 0514.20045
[15] Mateescu, A., Rozenberg, G., Salomaa, A.: Shuffle on trajectories: syntactic constraints. Theor. Comput. Sci. 197, 1–56 (1998) · Zbl 0902.68096 · doi:10.1016/S0304-3975(97)00163-1
[16] Pǎun, G., Salomaa, A.: Thin and slender languages. Discrete Appl. Math. 61, 257–270 (1995) · Zbl 0831.68057 · doi:10.1016/0166-218X(94)00014-5
[17] Păun, G., Rozenberg, G., Salomaa, A.: DNA Computing: New Computing Paradigms. Springer, New York (1998) · Zbl 0940.68053
[18] Rampersad, N., Shallit, J.: Words avoiding reversed subwords. J. Comb. Math. Comb. Comput. 54, 157–164 (2005) · Zbl 1081.68076
[19] Rampersad, N., Shallit, J., Wang, M.-W.: Avoiding large squares in infinite binary words. Theor. Comput. Sci. 339, 19–34 (2005) · Zbl 1099.68080 · doi:10.1016/j.tcs.2005.01.005
[20] Rothemund, P., Papadakis, N., Winfree, E.: Algorithmic self-assembly of DNA Sierpinski triangles. PLoS Biol. 2(12), e424 (2004) · doi:10.1371/journal.pbio.0020424
[21] Rozenberg, G., Salomaa, A.: Handbook of Formal Languages. Springer, New York (1997) · Zbl 0866.68057
[22] Shallit, J.: Numeration systems, linear recurrences, and regular sets. Inf. Comput. 113(2), 331–347 (1994) · Zbl 0810.11006 · doi:10.1006/inco.1994.1076
[23] Szilard, A., Yu, S., Zhang, K., Shallit, J.: Characterizing regular languages with polynomial densities. In: Havel, I., Koubek, V. (eds.) Mathematical Foundations of Computer Science 1992. Lecture Notes in Computer Science, vol. 629, pp. 494–503. Springer, New York (1992)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.