Modelling DNA and RNA secondary structures using matrix insertion-deletion systems

Lakshmanan Kuppusamy; Anand Mahendran

International Journal of Applied Mathematics and Computer Science (2016)

  • Volume: 26, Issue: 1, page 245-258
  • ISSN: 1641-876X

Abstract

top
Insertion and deletion are operations that occur commonly in DNA processing and RNA editing. Since biological macromolecules can be viewed as symbols, gene sequences can be represented as strings and structures can be interpreted as languages. This suggests that the bio-molecular structures that occur at different levels can be theoretically studied by formal languages. In the literature, there is no unique grammar formalism that captures various bio-molecular structures. To overcome this deficiency, in this paper, we introduce a simple grammar model called the matrix insertion-deletion system, and using it we model several bio-molecular structures that occur at the intramolecular, intermolecular and RNA secondary levels.

How to cite

top

Lakshmanan Kuppusamy, and Anand Mahendran. "Modelling DNA and RNA secondary structures using matrix insertion-deletion systems." International Journal of Applied Mathematics and Computer Science 26.1 (2016): 245-258. <http://eudml.org/doc/276672>.

@article{LakshmananKuppusamy2016,
abstract = {Insertion and deletion are operations that occur commonly in DNA processing and RNA editing. Since biological macromolecules can be viewed as symbols, gene sequences can be represented as strings and structures can be interpreted as languages. This suggests that the bio-molecular structures that occur at different levels can be theoretically studied by formal languages. In the literature, there is no unique grammar formalism that captures various bio-molecular structures. To overcome this deficiency, in this paper, we introduce a simple grammar model called the matrix insertion-deletion system, and using it we model several bio-molecular structures that occur at the intramolecular, intermolecular and RNA secondary levels.},
author = {Lakshmanan Kuppusamy, Anand Mahendran},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {bio-molecular structures; insertion-deletion systems; intermolecular; intramolecular; secondary structures},
language = {eng},
number = {1},
pages = {245-258},
title = {Modelling DNA and RNA secondary structures using matrix insertion-deletion systems},
url = {http://eudml.org/doc/276672},
volume = {26},
year = {2016},
}

TY - JOUR
AU - Lakshmanan Kuppusamy
AU - Anand Mahendran
TI - Modelling DNA and RNA secondary structures using matrix insertion-deletion systems
JO - International Journal of Applied Mathematics and Computer Science
PY - 2016
VL - 26
IS - 1
SP - 245
EP - 258
AB - Insertion and deletion are operations that occur commonly in DNA processing and RNA editing. Since biological macromolecules can be viewed as symbols, gene sequences can be represented as strings and structures can be interpreted as languages. This suggests that the bio-molecular structures that occur at different levels can be theoretically studied by formal languages. In the literature, there is no unique grammar formalism that captures various bio-molecular structures. To overcome this deficiency, in this paper, we introduce a simple grammar model called the matrix insertion-deletion system, and using it we model several bio-molecular structures that occur at the intramolecular, intermolecular and RNA secondary levels.
LA - eng
KW - bio-molecular structures; insertion-deletion systems; intermolecular; intramolecular; secondary structures
UR - http://eudml.org/doc/276672
ER -

References

top
  1. Boullier, P. and Sagot, B. (2011). Multi-component tree insertion grammars, in P. De Groote et al. (Eds.), Formal Grammar 2009, Lecture Notes in Artificial Intelligence, Vol. 5591, Springer, Berlin/Heidelberg, pp. 31-46. Zbl1325.68118
  2. Brendel, V. and Busse, H.G. (1984). Genome structure described by formal languages, Nucleic Acids Research 12(5): 2561-2568. 
  3. Brown, M. and Wilson, C. (1995). RNA pseudoknot modelling using intersections of stochastic context free grammars with applications to database search, Proceedings of the Pacific Symposium on Biocomputing, Big Island, HI, USA, pp. 109-125. 
  4. Cai, L., Russell, L. and Wu, Y. (2003). Stochastic modelling of RNA pseudoknotted structures: A grammatical approach, Bioinformatics 19(1): 66-73. 
  5. Calude, C.S. and Pa˘un, Gh. (2001). Computing with Cells and Atoms: An Introduction to Quantum, DNA and Membrane Computing, Taylor and Francis, London. 
  6. Chiang, D., Joshi, A.K. and Searls, D.B. (2006). Grammatical representations of macromolecular structure, Journal of Computational Biology 13(5): 1077-1100. 
  7. Dong, S. and Searls, D.B. (1994). Gene structure prediction by linguistic methods, Genomics 23(3): 540-551. 
  8. Dorigo, M. and Stutzle, T. (2004). Ant Colony Optimization, MIT Press, Cambridge, MA. Zbl1092.90066
  9. Durbin, R., Eddy, S., Krogh, A. and Mitchison, G. (1998). Biological Sequence Analysis, Cambridge University Press, Cambridge. Zbl0929.92010
  10. Eiben, A.E. and Smith, J.E. (2003). Introduction to Evolutionary Computing, Springer, Berlin/Heidelberg. Zbl1028.68022
  11. Galiukschov, B.S. (1981). Semicontextual grammars, Matematicheskaya Logika i Matematicheskaya Lingvistika: 38-50, (in Russian). 
  12. Goldberg, E.D. (1989). Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley, Boston, MA. Zbl0721.68056
  13. Haussler, D. (1982). Insertion and Iterated Insertion as Operations on Formal Languages, Ph.D. thesis, University of Colorado, Boulder, CO. 
  14. Haussler, D. (1983). Insertion languages, Information Science 131(1): 77-89. Zbl0544.68049
  15. Head, T. (1987). Formal language theory and DNA: An analysis of the generative capacity of specific recombinant behaviors, Bulletin of Mathematical Biology 49(6): 737-750. Zbl0655.92008
  16. Kuppusamy, L., Mahendran, A. and Krishna, S.N. (2011a). Matrix insertion-deletion systems for bio-molecular structures, in R. Natarajan and A. Ojo (Eds.), ICDCIT2011, Lecture Notes in Computer Science, Vol. 6536, Springer, Berlin/Heidelberg, pp. 301-311. 
  17. Kuppusamy, L., Mahendran, A. and Clergerie, E.V. (2011b). Modelling intermolecular structures and defining ambiguity in gene sequences using matrix insertion-deletion systems in biology, computation and linguistics, in G.B. Enguix et al. (Eds.), New Interdisciplinary Paradigms, IOS Press, Amsterdam, pp. 71-85. 
  18. Lyngso, R.B., Zuker, M. and Pedersen, C.N.S. (1999). Internal loops in RNA secondary structure prediction, RECOMB99, Proceedings of the 3rd International Conference on Computational Molecular Biology, Lyon, France, pp. 260-267. 
  19. Lyngso, R.B. and Pedersen, C.N.S. (2000). Pseudoknots in RNA secondary structure, RECOMB00, Proceedings of the 4th Annual International Conference on Computational Molecular Biology, Tokyo, Japan pp. 201-209. 
  20. Mamitsuka, H. and Abe, N. (1994). Prediction of beta-sheet structures using stochastic tree grammars, Proceedings of the 5th Workshop on Genome Informatics, Yokohama, Japan, pp. 19-28. 
  21. Pardo, M.A.A., Clergerie, E.V. and Ferro, M.V. (1997). Automata-based parsing in dynamic programming for LIG, in A.S. Narinyani (Ed.), Proceedings of the DIALOGUE'97 Computational Linguistics and Its Applications Workshop, Moscow, Russia, pp. 22-27. 
  22. Păun, Gh., Rozenberg, G. and Salomaa, A. (1998). DNA Computing: New Computing Paradigms, Springer, Berlin/Heidelberg. Zbl0940.68053
  23. Păun, Gh. (2002). Membrane Computing: An Introduction, Springer, Berlin/Heidelberg. Zbl1034.68037
  24. Petre, I. and Verlan, S. (2012). Matrix insertion-deletion systems, Theoretical Computer Science 456: 80-88. Zbl1279.68087
  25. Rivas, E. and Eddy, S.R. (2000). The language of RNA: A formal grammar that includes pseudoknots, Bioinformatics 16(4): 334-340. 
  26. Rozenberg, G. and Salomaa, A. (1997). Handbook of Formal Languages, Vol. 1, Springer, New York, NY. Zbl0866.68057
  27. Sakakibara, Y., Brown, R., Hughey, R., Mian, I.S., Sjolander, K., Underwood, R.C. and Haussler, D. (1996). Stochastic context-free grammars for tRNA modelling, Nucleic Acids Research 22(23): 5112-5120. 
  28. Sakakibara, Y. (2003). Pair hidden Markov models on tree structures, Bioinformatics 19(1): 232-240. 
  29. Searls, D.B. (1988). Representing genetic information with formal grammars, Proceedings of the National Conference on Artificial Intelligence, Saint Paul, MN, USA, pp. 386-391. 
  30. Searls, D.B. (1992). The linguistics of DNA, American Scientist 80(6): 579-591. 
  31. Searls, D.B. (1993). The computational linguistics of biological sequences, in L. Hunter (Ed.), Artificial Intelligence and Molecular Biology, AAAI Press, Paolo Alto, CA, pp. 47-120. 
  32. Searls, D.B. (1995). Formal grammars for intermolecular structures, 1st International IEEE Symposium on Intelligence and Biological Systems, Washington, DC, USA, pp. 30-37. 
  33. Searls, D.B. (2002). The language of genes, Nature 420(6912): 211-217. 
  34. Theis, C., Janssen, S. and Giegerich, R. (2010). Prediction of RNA secondary structure including kissing hairpin motifs, Proceedings of WABI 2010, Liverpool, UK, pp. 52-64. 
  35. Uemura, Y, Hasegawa, A., Kobayashi, S. and Yokomori, T. (1999). Tree adjoining grammars for RNA structure prediction, Theoretical Computer Science 210(2): 277-303. Zbl0912.68121
  36. Yuki, S. and Kasami, T. (2006). RNA pseudoknotted structure prediction using stochastic multiple context-free grammar, IPSJ Transactions on Bioinformatics 47: 12-21. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.