Evolving state grammar for modeling DNA and RNA structures

  • Abstract
  • Keywords
  • References
  • PDF
  • Abstract

    In this paper, we represent bio-molecular structures (Attenuator, Extended Pseudoknot Structure, Kissing Hairpin, Simple H-type structure, Recursive Pseudoknot and Three-knot Structure) using state grammar. These representations will be measured using descriptional complexity point of views. Results indicate that the proposed approach is more succinct in terms of production rules and variables over the existing approaches. Another major advantage of the proposed approach is state grammar can be represented by deep pushdown automata, whereas no such automaton exists for matrix ins-del system.

  • Keywords

    Descriptional Complexity; Kissing Hairpin; Pseudoknot; Ribonucleic Acid; Simple H-Type; State Grammar; Three-Knot.

  • References

      [1] L. Cai, L.R. Malmberg and Y. Wu, “Stochastic modeling of RNA pseudoknotted structures: a grammatical approach”, Bioinformatics, Vol. 19, No. 1, i66-i73, (2003). https://doi.org/10.1093/bioinformatics/btg1007.

      [2] T. Kasai, “An hierarchy between context-free and context-sensitive languages, Journal of Computer and System Sciences”, Vol. 4, No. 5, (1970), pp: 492-508. https://doi.org/10.1016/S0022-0000(70)80045-9.

      [3] K.Y. Sung, “The Use of Context-Sensitive Grammar For Modeling RNA Pseudoknots”, In- Proceedings of the International Conference on Bioinformatics & Computational Biology (BIOCOMP’06); Las Vegas, Nevada, USA, 338-344, 26-29 June (2006).

      [4] Y. Sakakibara, M. Brown, R. Hughey, I.S. Mian, K. Sjölander, R.C. Underwood, D. Haussler, “Stochastic context-free grammars for tRNA modelling”, Nucleic Acids Research, Vol. 22, No. 23, (1996), pp: 5112-5120. https://doi.org/10.1093/nar/22.23.5112.

      [5] Y. Sakakibara, “Pair hidden Markov models on tree structures”, Bioinformatics, Vol. 19, No. 1, (2003), pp: 232-240. https://doi.org/10.1093/bioinformatics/btg1032.

      [6] S. Yuki and T. Kasami, “RNA pseudoknotted structure prediction using stochastic multiple context-free grammar”, IPSJ Transactions on Bioinformatics, Vol. 47, (2006), pp: 12-21.

      [7] M. Brown and C. Wilson, “RNA pseudoknot modeling using intersections of stochastic context free grammars with applications to database search”, Proceedings of the Pacific Symposium on Biocomputing, Big Island, HI, USA, (1995), pp: 109-125.

      [8] E. Rivas and S. R. Eddy, “The language of RNA: a formal grammar that includes pseudoknots”, Bioinformatics, Vol. 16, No. 4, (2000), pp: 334-340. https://doi.org/10.1093/bioinformatics/16.4.334.

      [9] D. B. Searls, “The computational linguistics of biological sequences, Artificial intelligence and molecular biology”, American Association for Artificial Intelligence Menlo Park, CA, USA, Vol. 2, (1993), pp: 47-120.

      [10] D. B. Searls, “String variable grammar: A logic grammar formalism for the biological language of DNA”, The Journal of Logic Programming, Vol. 24, No. 1, (1995), pp: 73-102. https://doi.org/10.1016/0743-1066(95)00034-H.

      [11] N. Mizoguchi, Y. Kato, and H. Seki, “A grammar-based approach to RNA pseudoknotted structure prediction for aligned sequences”, In - Proceedings of 1st IEEE International Conference on Computational Advances in Bio and Medical Sciences (ICCABS), Orlando, FL, (2011), pp: 135-140. https://doi.org/10.1109/ICCABS.2011.5729868.

      [12] L. Kuppusamy and A. Mahendran, “Modelling DNA and RNA secondary structures using matrix insertion-deletion systems”, International Journal of Applied Mathematics and Computer Science, Vol. 26, No. 1, (2016), pp: 245-258. https://doi.org/10.1515/amcs-2016-0017.

      [13] N. Kalra and A. Kumar, “State Grammar and Deep Pushdown Automata for Biological Sequences of Nucleic Acids”, Current Bioinformatics, Vol. 11, No. 4, (2016), pp: 470-479. https://doi.org/10.2174/1574893611666151231185112.

      [14] A. Meduna and P. Zemek, “Regulated Grammars and Automata”, Springer, New York, 2014. https://doi.org/10.1007/978-1-4939-0369-6.

      [15] J. Dassow and G. Pawn, “Regulated rewriting in formal language theory”, 1st ed Springer-Verlag Berlin Heidelberg, (2012).

      [16] J. Dassow, “Grammars with regulated rewriting”, In: Formal Languages and Applications: Studies in Fuzziness and Soft Computing Ed. Springer Berlin Heidelberg, 148, (2004), pp: 249-273. https://doi.org/10.1007/978-3-540-39886-8_13.

      [17] L. Kuppusamy, I. Raman and K. Krithivasan, “On Succinct Description of Certain Context-Free Languages by Ins-Del and Matrix Ins-Del Systems”, International Journal of Foundations of Computer Science, Vol. 27, No.7, (2016), pp: 775-786. https://doi.org/10.1142/S0129054116500295.

      [18] N. Kalra and A. Kumar, “Fuzzy state grammar and fuzzy deep pushdown automaton”, Journal of Intelligent and Fuzzy Systems, Vol. 31, No.1, (2016), pp: 249-258. https://doi.org/10.3233/IFS-162138.

      [19] K. Singh, “Conversion of deterministic finite automata to regular expression using bridge state”, M.E. Thesis, Thapar University, (2011).

      [20] N. Kalra and A. Kumar, “Deterministic Deep Pushdown Transducer and its Parallel Version”, The Computer Journal, doi.org/10.1093/comjnl/bxx036. https://doi.org/10.1093/comjnl/bxx036.

      [21] T. Singla and A. Kumar, “Reducing Mutation Testing Endeavor using the similar conditions for the same Mutation Operators occurs at Different Locations”, Applied mathematics & Information Science, Vol. 8, No. 5, (2014), pp: 2389-2393. https://doi.org/10.12785/amis/080534.

      [22] R. Kumar and A. Kumar, “Metamorphosis of fuzzy regular expressions to fuzzy automata using the follow automata”, arXiv preprint arXiv: 1411.2865.




Article ID: 8627
DOI: 10.14419/ijet.v7i1.8627

Copyright © 2012-2015 Science Publishing Corporation Inc. All rights reserved.