On the Regularity of Iterated Hairpin Completion of a Single Word

• Autorzy: Kari L. , Seki S. , Kopecki S.
• Języki publikacji: EN

Abstrakty

EN

Hairpin completion is an abstract operation modeling a DNA bio-operation which receives as input a DNA strand w = xaya, and outputs w' = xayax, where x denotes the Watson- Crick complement of x. In this paper, we focus on the problem of finding conditions under which the iterated hairpin completion of a given word is regular. According to the numbers of words a and a that initiate hairpin completion and how they are scattered, we classify the set of all words w. For some basic classes of words w containing small numbers of occurrences of a and a, we prove that the iterated hairpin completion of w is regular. For other classes with higher numbers of occurrences of a and a, we prove a necessary and sufficient condition for the iterated hairpin completion of a word in these classes to be regular.

Słowa kluczowe

EN

combinatorics on words; commutativity of words; DNA computing; iterated hairpin completion; regularity test; single-primer hairpin completion

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 110, nr 1-4
• Strony: 201--215
• Opis fizyczny: Bibliogr. 21 poz., wykr.

Twórcy

autor

Kari L.

autor

Seki S.

autor

Kopecki S.

• Department of Systems Biosciences for Drug Discovery, Kyoto University, 46-29, Yoshida- Shimo-Adachi-cho, Sakyo-ku, Kyoto, 606-8501, Japan,

Bibliografia

• [1] Adleman, L.M.: Molecular Computation of Solutions to Combinatorial Problems, Science, 266(5187), 1994, 1021-1024.
• [2] Arita, M., Kobayashi, S.: DNA Sequence Design Using Templates, New Generation Computing, 20, 2002, 263-277.
• [3] Cheptea, D., Mart´ın-Vide, C., Mitrana, V.: A New Operation on Words Suggested by DNA Biochemistry: Hairpin Completion, Transgressive Computing (J.-G. Dumas, Ed.), 2006, 216-228.
• [4] Choffrut, C., Karhumäki, J.: Combinatorics of Words, in: Handbook of Formal Languages (G. Rozenberg, A. Salomaa, Eds.), vol. 1, Springer-Verlag, Berlin-Heidelberg-New York, 1997, 329-438.
• [5] Diekert, V., Kopecki, S.: Complexity Results and the Growths of Hairpin Completions of Regular Languages (Extended Abstract), Proc. of CIAA 2010 (M. Domaratzki, K. Salomaa, Eds.), LNCS 6482, Springer, 2011, 105-114.
• [6] Fine, N. J., Wilf, H. S.: Uniqueness Theorem for Periodic Functions, Proceedings of the American Mathematical Society, 16(1), 1965, 109-114.
• [7] Hagiya, M., Arita, M., Kiga, D., Sakamoto, K., Yokoyama, S.: Towards Parallel Evaluation and Learning of Boolean μ-Formulas with Molecules, Proc. of 3rd DIMACS Workshop on DNA Based Computers (H. Rubin, D. Wood, Eds.), DIMACS Series in Discrete Mathematics and Theoretical Computer Science 48, 1999, 57-72.
• [8] Ito, M., Leupold, P., Manea, F., Mitrana, V.: Bounded Hairpin Completion, Information and Computation, 209(3), 2011, 471-485.
• [9] Jonoska, N., Kephart, D., Mahalingam, K.: Generating DNA Codewords, Congressus Numerantium, 156, 2002, 99-110.
• [10] Jonoska, N., Mahalingam, K.: Languages of DNA Based Code Words, Proc. of DNA Computing 9 (J. Chen, J. Reif, Eds.), LNCS 2943, Springer, 2004, 61-73.
• [11] Kameda, A., Yamamoto, M., Ohuchi, A., Yaegashi, S., Hagiya, M.: Unravel Four Hairpins!, Natural Computing, 7, 2008, 287-298.
• [12] Kopecki, S.: On Iterated Hairpin Completion, Theoretical Computer Science, 412(29), 2011, 3629-3638.
• [13] Manea, F.,Mart´ın-Vide, C.,Mitrana, V.: On Some Algorithmic Problems Regarding the Hairpin Completion, Discrete Applied Mathematics, 157, 2009, 2143-2152.
• [14] Manea, F., Mitrana, V., Yokomori, T.: Two Complementary Operations Inspired by the DNA Hairpin Formations: Completion and Reduction, Theoretical Computer Science, 410(4-5), 2009, 417-425.
• [15] Manea, F., Mitrana, V., Yokomori, T.: Some Remarks on the Hairpin Completion, International Journal of Foundations of Computer Science, 21(5), 2010, 859-872.
• [16] Okazaki, R., Okazaki, T., Sakabe, K., Sugimoto, K., Sugino, A.: Mechanism of DNA Chain Growth, I. Possible Discontinuity and Unusual Secondary Structure of Newly Synthesized Chains, Proceedings of the National Academy of Sciences of the United States of America, 59(2), 1968, 598-605.
• [17] Pǎun, G., Rozenberg, G., Yokomori, T.: Hairpin Languages, International Journal of Foundations of Computer Science, 12(6), 2001, 837-847.
• [18] Sakamoto, K., Kiga, D., Komiya, K., Gouzu, H., Yokoyama, S., Ikeda, S., Sugiyama, H., Hagiya, M.: State Transitions by Molecules, Biosystems, 52(1-3), 1999, 81-91.
• [19] Takinoue,M., Suyama, A.: Molecular Reactions for aMolecularMemory Based on Hairpin DNA, Chem-Bio Informatics Journal, 4, 2004, 93-100.
• [20] Takinoue, M., Suyama, A.: Hairpin-DNA Memory Using Molecular Addressing, Small, 2(11), 2006, 1244-1247.
• [21] Wilson, K. S., von Hippel, P. H.: Transcription Termination at Intrinsic Terminators: The Role of the RNA Hairpin, Proceedings of the National Academy of Sciences of the United States of America, 92(19), 1995, 8793-8797.