Static Watson-Crick regular grammar

Authors

  • Aqilahfarhana Abdul Rahman Universiti Teknologi Malaysia
  • Wan Heng Fong Universiti Teknologi Malaysia
  • Nor Haniza Sarmin Universiti Teknologi Malaysia
  • Sherzod Turaev International Islamic University Malaysia
  • Nurul Liyana Mohamad Zulkufli International Islamic University Malaysia

DOI:

https://doi.org/10.11113/mjfas.v14n0.1282

Keywords:

Sticker system, Watson-Crick grammar, regular grammar, computational power, Chomsky hierarchy

Abstract

DNA computing, or more generally, molecular computing, is a recent development at the interface of computer science and molecular biology. In DNA computing, many computational models have been proposed in the framework of formal language theory and automata such as Watson-Crick grammars and sticker systems. A Watson-Crick grammar is a grammar model that generates double stranded strings, whereas a sticker system is a DNA computing model of the ligation and annealing operations over DNA strands using the Watson-Crick complementarity to form a complete double stranded DNA sequence. Most of the proposed DNA computing models make use of this concept, including the Watson-Crick grammars and sticker systems. Watson-Crick grammars and their variants can be explored using formal language theory which allows the development of new concepts of Watson-Crick grammars.  In this research, a new variant of Watson-Crick grammar called a static Watson-Crick regular grammar is introduced as an analytical counterpart of sticker systems. The computation of a sticker system starts from a given set of incomplete double stranded sequence to form a complete double stranded sequence. Here, a static Watson-Crick regular grammar differs from a dynamic Watson-Crick regular grammar in generating double stranded strings: the latter grammar produces each strand string “independently” and only check for the Watson-Crick complementarity of a generated complete double stranded string at the end, while the former grammar generates both strand strings “dependently”, i.e., checking for the Watson-Crick complementarity for each complete substring. In this paper, computational properties of static Watson-Crick regular grammars are investigated to correlate with the Chomsky hierarchy and hierarchy of the families of dynamic Watson-Crick regular languages. The relationship between families of languages generated by static Watson-Crick regular grammars with several variants of sticker systems, Watson-Crick regular grammars and Chomsky grammars are presented by showing the hierarchy.

Author Biographies

Aqilahfarhana Abdul Rahman, Universiti Teknologi Malaysia

Department of Mathematical Sciences, Faculty of Science

Wan Heng Fong, Universiti Teknologi Malaysia

Department of Mathematical Sciences, Faculty of Science

Nor Haniza Sarmin, Universiti Teknologi Malaysia

Department of Mathematical Sciences, Faculty of Science

Sherzod Turaev, International Islamic University Malaysia

Department of Computer Science, Faculty of Information and Communication Technology

Nurul Liyana Mohamad Zulkufli, International Islamic University Malaysia

Department of Computer Science, Faculty of Information and Communication Technology

References

L.M. Adleman, Molecular Computation of Solutions to Combinatorial Problems, Science 266 (1994) 1021-1024.

D. Boneh, C. Dunworth, R.J. Lipton, J. Sgall, On the Computational Power of DNA, Discrete Applied Mathematics 71 (1996) 79-94.

R.J. Lipton, DNA Solution of Hard Computational Probelms, Science 268 (1995) 542–545.

N. Bouhmala, A Variable Neighborhood Walksat-based Algorithm for MAX-SAT Problems, The Scientific World Journal (2014) 1-11.

M. Darehmiraki, A New Solution for Maximal Clique Problem, Biosystems 95(2) (2009) 145-149.

M. Razzazi, M. Roayaei, Using Sticker Model of DNA Computing to Solve Domatic Partition, Kernel and Induced Path Problems, Journal Information Sciences 181(17) (2011) 3581-3600.

T. Head, Formal Language Theory and DNA: An Analysis of the Generative Capacity of Specific Recombinant Behaviors, Bulletin of Mathematical Biology 49(6) (1987) 737-759.

L. Kari, G. Paun, G. Rozenberg, A. Salomaa, S. Yu, DNA Computing, Sticker Systems and Universality, Acta Informatica 35(5) (1998) 401-420.

Y.S. Gan, W.H. Fong, N.H. Sarmin, The Generative Power of Weighted One-Sided and Regular Sticker Systems, In AIP Conference Proceedings, 2014, 1602 (1) p. 855-862.

R. Freund, G. Paun, G. Rozenberg, A. Salomaa, Watson-Crick Finite Automata, in: Proc. 3rd DIMACS Workshop on DNA based Computers, Philadelphia, 1997, p. 297-328.

K.G. Subramanian, S. Hemalatha, I. Venkat, On Watson-Crick Automata, In: Proc. the Second International Conference on Computational Science, Engineering and Information Technology, Coimbatore, India, 2012, p. 151-156.

N.L.M. Zulkufli, S. Turaev, M.I.M. Tamrin, M. Azeddine, Closure Properties of Watson-Crick Grammars, In AIP Conference Proceedings, 2015, 1691 (1) p. 040032.

E. Czeizler, E. Czeizler, A Short Survey on Watson-Crick Automata, Bulletin of the EATCS 88 (2006). 104-119.

G. Pa ̌un, G. Rozenberg, A. Salomaa, DNA Computing: New Computing Paradigms, Springer, 1998, p. 82-153.

P. Linz, An Introduction to Formal Languages and Automata, Jones and Barlett Publishers, 2006, p. 16.

G. Pa ̌un, G. Rozenberg, Sticker Systems, Theoretical Computer Science 204 (1998) 183-203.

Downloads

Published

25-10-2018