A Formal Language Model of DNA Polymerase Enzymatic Activity

• Autorzy: Enaganti S. K. , Kari L. , Kopecki S.

Identyfikatory

DOI

10.3233/FI-2015-1206

• Języki publikacji: EN

Abstrakty

EN

We propose and investigate a formal language operation inspired by the naturally occurring phenomenon of DNA primer extension by a DNA-template-directed DNA Polymerase enzyme. Given two DNA strings u and v, where the shorter string v (called primer) is Watson-Crick complementary and can thus bind to a substring of the longer string u (called template) the result of the primer extension is a DNA string that is complementary to a suffix of the template which starts at the binding position of the primer. The operation of DNA primer extension can be abstracted as a binary operation on two formal languages: a template language L₁ and a primer language L₂. We call this language operation L₁-directed extension of L₂ and study the closure properties of various language classes, including the classes in the Chomsky hierarchy, under directed extension. Furthermore, we answer the question under what conditions can a given language of target strings be generated from a given template language when the primer language is unknown. We use the canonic inverse of directed extension in order to obtain the optimal solution (the minimal primer language) to this question.

Słowa kluczowe

EN

formal languages; DNA primers; DNA polymerases; enzyme kinetics; binary system

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 138, nr 1/2
• Strony: 179--192
• Opis fizyczny: Bibliogr. 34 poz., tab.

Twórcy

autor

Enaganti S. K.

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

autor

Kari L.

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

autor

Kopecki S.

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

Bibliografia

• [1] A. Alhazov, A. Krassovitskiy, Y. Rogozhin, and S. Verlan. P systems with insertion and deletion exooperations. Fundamenta Informaticae, 110(1-4):13–28, 2011.
• [2] A. Alhazov, A. Krassovitskiy, Y. Rogozhin, and S. Verlan. P systems with minimal insertion and deletion. Theoretical Computuer Science, 412(1-2):136–144, 2011.
• [3] P. Bottoni, A. Labella, V. Manca, and V. Mitrana. Superposition based on Watson-Crick-like complementarity. Theory of Computing Systems, 39(4):503–524, 2006.
• [4] D. Cheptea, C. Mart´ın-Vide, and V. Mitrana. A new operation on words suggested by DNA biochemistry: Hairpin completion. In Transgressive Computing, TC 2006, pages 216–228, 2006.
• [5] M. Daley, L. Kari, G. Gloor, and R. Siromoney. Circular contextual insertions/deletions with applications to biomolecular computation. In Proceedings of 6th International Symposium on String Processing and Information Retrieval, SPIRE 1999, pages 47–54, 1999.
• [6] R. Freund, M. Kogler, Y. Rogozhin, and S. Verlan. Graph-controlled insertion-deletion systems. In I. Mc-Quillan and G. Pighizzini, editors, Proceedings of 12th International Workshop on Descriptional Complexity of Formal Systems, DCFS 2010, volume 31 of Electronic Proceedings in Theoretical Computer Science, pages 88–98, 2010.
• [7] R. Freund, Y. Rogozhin, and S. Verlan. P systems with minimal left and right insertion and deletion. In J. Durand-Lose and N. Jonoska, editors, Proceedings of 11th International Conference on Unconventional Computation and Natural Computation, UCNC 2012, volume 7445 of LNCS, pages 82–93, 2012.
• [8] R. Freund, Y. Rogozhin, and S. Verlan. Generating and accepting P systems with minimal left and right insertion and deletion. Natural Computing, 13(2):257–268, 2014.
• [9] R. W. Gatterdam. Splicing systems and regularity. International Journal of Computer Mathematics, 31(1-2):63–67, 1989.
• [10] T. Head. Formal language theory and DNA: An analysis of the generative capacity of specific recombinant behaviors. Bulletin of Mathematical Biology, 49(6):737–759, 1987.
• [11] T. Head, D. Pixton, and E. Goode. Splicing systems: Regularity and below. In M. Hagiya and A. Ohuchi, editors, Revised Papers from the 8th International Workshop on DNA Based Computers: DNA Computing, DNA 8, volume 2568 of LNCS, pages 262–268, 2003.
• [12] S. Hussini, L. Kari, and S. Konstantinidis. Coding properties of DNA languages. Theoretical Computer Science, 290(3):1557–1579, 2003.
• [13] L. Kari. On language equations with invertible operations. Theoretical Computer Science, 132(1-2):129–150, 1994.
• [14] L. Kari, R. Kitto, and G. Thierrin. Codes, involutions, and DNA encodings. InW. Brauer, H. Ehrig, J. Karhumaki, and A. Salomaa, editors, Formal and Natural Computing, volume 2300 of LNCS, pages 376–393, 2002.
• [15] L. Kari and S. Kopecki. Deciding whether a regular language is generated by a splicing system. In D. Stefanovic and A. Turberfield, editors, DNA Computing and Molecular Programming, volume 7433 of LNCS, pages 98–109, 2012.
• [16] L. Kari and E. Losseva. Block substitutions and their properties. Fundamenta Informaticae, 73(1-2):165–178, 2006.
• [17] L. Kari, G. P˘aun, G. Thierrin, and S. Yu. At the crossroads of DNA computing and formal languages: Characterizing recursively enumerable languages using insertion-deletion systems. In DNA Based Computers III (DNA3), volume 48 of DIMACS: Series in Discrete Mathematics and Theoretical Computer Science, pages 329–346, 1999.
• [18] L. Kari and P. Sos´ık. On the weight of universal insertion grammars. Theoretical Computer Science, 396(1-3):264–270, 2008.
• [19] S. Kim. An algorithm for identifying spliced languages. In D. Lee and S.-H. Teng, editors, Proceedings of 11th Annual International Symposium on Algorithms and Computation, ISAAC 2000, volume 1276 of LNCS, pages 403–411, 1997.
• [20] S. Kobayashi, V. Mitrana, G. P˘aun, and G. Rozenberg. Formal properties of PA-matching. Theoretical Computer Science, 262(1-2):117–131, 2001.
• [21] S. Kopecki. On iterated hairpin completion. Theoretical Computer Science, 412(29):3629–3638, 2011.
• [22] A. Krassovitskiy, Y. Rogozhin, and S. Verlan. Computational power of P systems with small size insertion and deletion rules. In T. Neary, D. Woods, A. K. Seda, and N. Murphy, editors, Proceedings of International Workshop on The Complexity of Simple Programs, CSP 2008, volume 1 of Electronic Proceedings in Theoretical Computer Science, pages 108–117, 2008.
• [23] A. Krassovitskiy, Y. Rogozhin, and S. Verlan. Further results on insertion-deletion systems with one-sided contexts. In C. Mart´ın-Vide, F. Otto, and H. Fernau, editors, Proceedings of 2nd International Conference on Language and Automata Theory and Applications, LATA 2008, volume 5196 of LNCS, pages 333–344, 2008.
• [24] A. Krassovitskiy, Y. Rogozhin, and S. Verlan. Computational power of insertion-deletion (P) systems with rules of size two. Natural Computing, 10(2):835–852, 2011.
• [25] F. Manea, C. Mart´ın-Vide, and V. Mitrana. On some algorithmic problems regarding the hairpin completion. Discrete Applied Mathematics, 157(9):2143–2152, 2009.
• [26] F. Manea and V. Mitrana. Hairpin completion versus hairpin reduction. In S. B. Cooper, B. Löwe, and A. Sorbi, editors, Proceedings of 3rd Conference on Computability in Europe, CiE 2007, volume 4497 of LNCS, pages 532–541, 2007.
• [27] M. Margenstern, G. Păun, Y. Rogozhin, and S. Verlan. Context-free insertion-deletion systems. Theoretical Computer Science, 330(2):339–348, 2005.
• [28] A. Matveevici, Y. Rogozhin, and S. Verlan. Insertion-deletion systems with one-sided contexts. In J. Durand-Lose and M. Margenstern, editors, Proceedings of 5th International Conference on Machines, Computations, and Universality, MCU 2007, volume 4664 of LNCS, pages 205–217, 2007.
• [29] D. Pixton. Regularity of splicing languages. Discrete Applied Mathematics, 69(1-2):101–124, 1996.
• [30] G. P˘aun, M. J. P`erez-Jim`enez, and T. Yokomori. Representations and characterizations of languages in Chomsky hierarchy by means of insertion-deletion systems. International Journal of Foundations of Computer Science, 19(4):859–871, 2008.
• [31] G. Păun, G. Rozenberg, and A. Salomaa. DNA Computing: New Computing Paradigms(Texts in Theoretical Computer Science. An EATCS Series). Springer-Verlag New York, Inc., 2006.
• [32] J. H. Reif. Parallel molecular computation. In Proceedings of the 7th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1995, pages 213–223, 1995.
• [33] A. Takahara and T. Yokomori. On the computational power of insertion-deletion systems. Natural Computing, 2(4):321–336, 2003.
• [34] M. Yong, J. Xiao-Gang, S. Xian-Chuang, and P. Bo. Minimizing of the only-insertion insdel systems. Journal of Zhejiang University Science A, 6(10):1021–1025, 2005.