A Formal Language Analysis of DNA Hairpin Structures

• Autorzy: Kari L. , Losseva E. , Konstantindis S. , Sosik P. , Thierrin G.
• Języki publikacji: EN

Abstrakty

EN

The concept of hairpin structures in formal languages is motivated from the biocomputing and bioinformatics fields. Hairpin (-free) DNA structures have numerous applications to DNA computing and molecular genetics in general. A word is called hairpin-free if it cannot be written in the form xvyq(v)z, with certain additional conditions, for an involution q (a function q with the property that q2 equals the identity function). A particular involution, the so-called Watson-Crick involution, can characterize binding of two DNA strands. We study algebraic and decision properties, finiteness and descriptional complexity of hairpin (-free) languages. We show an existence of polynomial-time algorithms deciding hairpin-freeness of regular and context-free sets. Two related DNA secondary structures are considered, taking into the account imperfect bonds (bulges, mismatches) and multiple hairpins. Finally, effective methods for design of long hairpin-free DNA words are given.

Słowa kluczowe

EN

DNA computing; DNA hairpin; involution; formal languages

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 71, nr 4
• Strony: 453--475
• Opis fizyczny: bibliogr. 28 poz.

Twórcy

autor

Kari L.

autor

Losseva E.

autor

Konstantindis S.

autor

Sosik P.

autor

Thierrin G.

• Department of Computer Science, University of Western Ontario, N6A 5B7, London, Ontario, Canada,

Bibliografia

• [1] Amos, M.: Theoretical and Experimental DNA Computations, Springer-Verlag, Berlin, 2005.
• [2] Andronescu, M., Dees, D., Slaybaugh, L., Zhao, Y., Condon, A., Cohen, B., Skiena, S.: Algorithms for testing that sets of DNA words concatenate without secondary structure. Proc. 8th Workshop on DNA-Based Computers (M. Hagiya, A. Ohuchi, Eds.), LNCS 2568, Springer-Verlag, Berlin, 2002, 182-195.
• [3] Benenson, Y., Gil, B., Ben-Dor, U., Adar, R., Shapiro, E.: An autonomous molecular computer for logical control of gene expression. Nature, 429, 2004, 423-429.
• [4] Birget, J. C.: Intersection and union of regular languages and state complexity, Information Processing Letters, 43, 1992, 185-190.
• [5] Brodal, G. S., Lyngsø, R. B., Pedersen, C. N. S., Stoye, J.: Finding maximal pairs with bounded gap. Proc. 10th Annual Symposium on Combinatorial Pattern Matching (CPM) (M. Crochemore and M. Paterson, Eds.), LNCS 1645, Springer-Verlag, Berlin, 1999, 134-149.
• [6] Calladine, C. R., Drew, H. R.: Understanding DNA: The Molecule and How It Works, 2nd edition, Academic Press, San Diego, 1999.
• [7] Choffrut, C., Karhumäki, J.: Combinatorics of words, in [26], 329-438.
• [8] Daley, M., Kari, L.: Some properties of ciliate bio-operations, Proc. of DLT 2002 (M. Ito, M. Toyama, Eds.), LNCS 2450, Springer-Verlag, Berlin, 2003, 116-127.
• [9] Dekking, F. M.: On repetitions of blocks in binary sequences, J. Combin. Theory Ser. A, 20, 1976, 292-299.
• [10] Ehrenfeucht, A., Harju, T., Petre, I., Prescott, D., Rozenberg, G.: Computation in Living Cells: Gene Assembly in Ciliates, Springer-Verlag, Berlin, 2004.
• [11] Haines, L. H.: On free monoids partially ordered by embedding, J. of Combinatorial Theory, 6, 1969, 94-98.
• [12] Harju, T., Karhum¨aki, J.: Morphisms, in [26], 439-510.
• [13] Hopcroft, J., Ullman, J., Motwani, R.: Introduction to Automata Theory, Languages, and Computation, 2nd ed., Addison-Wesley, 2001.
• [14] Jonoska, N., Kephart, D., Mahalingam, K.: Generating DNA code words, Congressus Numerantium, 156, 2002, 99-110.
• [15] Jonoska, N., Mahalingam, K.: Languages of DNA based code words, Proc. DNA Computing, 9th International Workshop on DNA Based Computers (J. Chen and J. H. Reif, Eds.), LNCS 2943, Springer-Verlag, Berlin, 2004, 61-73.
• [16] Kobayashi, S.: Testing structure-freeness of regular sets of biomolecular sequences, Proc. DNA 10 (C. Feretti, G. Mauri, C. Zandron, Eds.), LNCS 3384, Springer-Verlag, Berlin, 2005, 192-201.
• [17] Kijima, A., Kobayashi, S.: Efficient algorithms for testing structure-freeness of finite sets of biomolecular sequences, Proc. DNA 11 (A. Carbone et al., Eds.), London, The University of Western Ontario, 2005, 278-288.
• [18] Lothaire, M.: Algebraic Combinatorics on Words, Cambridge University Press, 2002.
• [19] de Luca, A.: On the combinatorics of finite words, Theoretical Computer Science, 218, 1999, 13-39.
• [20] Kari, L., Konstantinidis, S., Sos´ık, P.: Bond-free languages: formalizations, maximality and construction methods, Proc. DNA 10 (C. Feretti, G. Mauri, C. Zandron, Eds.), LNCS 3384, Springer-Verlag, Berlin, 2005, 169-181.
• [21] Mauri, G., Ferretti, C.: Word Design for Molecular Computing: A Survey, Proc. DNA Computing, 9th International Workshop on DNA Based Computers (J. Chen and J. H. Reif, Eds.), LNCS 2943, Springer-Verlag, Berlin, 2004, 37-46.
• [22] Pǎun, G., Rozenberg, G., Salomaa, A.: DNA Computing: New Computing Paradigms, Springer Verlag, Berlin, 1998.
• [23] Pǎun, G., Rozenberg, G., Yokomori, T.: Hairpin languages, Intern. J. Found. Computer Sci., 12 (6), 2001, 849-857.
• [24] Roman, S.: Coding and Information Theory, Springer-Verlag, New York, 1992.
• [25] Rose, J. A., Deaton, R. J., Hagiya, M., Suyama, A.: PNA-mediated Whiplash PCR, Proc. DNA Computing, 7th International Workshop on DNA Based Computers (N. Jonoska and N. C. Seeman, Eds.), LNCS 2340, Springer-Verlag, Berlin, 2002, 104-116.
• [26] Rozenberg, G., Salomaa, A. (Eds.): Handbook of Formal Languages, vol. 1, Springer Verlag, Berlin, 1997.
• [27] Takahashi, N., Kameda, A., Yamamoto, M., Ohuchi, A.: Aqueous computing with DNA hairpin-based RAM. Proc. DNA 10, Tenth International Meeting on DNA Computing (G. Mauri, C. Ferretti, Eds.), University of Milano-Bicocca, 2004, 50-59.
• [28] Thierrin, G.: Convex languages, Proc. IRIA Symp. North Holland, 1972, 481-492.