Evolving state grammar for modeling DNA and RNA structures

  • Authors

    • Ajay Kumar Thapar UniversityPatiala
    • Nidhi Kalra Thapar University, Patiala
    • Sunita Garhwal Thapar University, Patiala
    2017-12-07
    https://doi.org/10.14419/ijet.v7i1.8627
  • Descriptional Complexity, Kissing Hairpin, Pseudoknot, Ribonucleic Acid, Simple H-Type, State Grammar, Three-Knot.

  • 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.

  • References

    1. [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.

  • Downloads

  • How to Cite

    Kumar, A., Kalra, N., & Garhwal, S. (2017). Evolving state grammar for modeling DNA and RNA structures. International Journal of Engineering & Technology, 7(1), 19-24. https://doi.org/10.14419/ijet.v7i1.8627

    Received date: 2017-11-08

    Accepted date: 2017-11-20

    Published date: 2017-12-07