Submit Manuscript  

Article Details

State Grammar and Deep Pushdown Automata for Biological Sequences of Nucleic Acids

[ Vol. 11 , Issue. 4 ]


Nidhi Kalra and Ajay Kumar   Pages 470 - 479 ( 10 )


In this paper, we represent deoxyribonucleic acid (DNA) and ribonucleic acid (RNA) biological sequences using state grammar and deep pushdown automata. The major benefit of this approach is that the DNA and RNA sequences can be parsed in linear time O(n) , where n is the length of the string, which is a significant improvement over the existing approaches. In the various existing approaches in the literature, these sequences are represented using context-sensitive grammar or mildly context-sensitive with higher time complexities. To the best of the author's knowledge, this is the first attempt to represent these sequences using state grammar and deep pushdown automata.


Deoxyribonucleic acid, ribonucleic acid, state grammar, deep pushdown automata, tandem repeat, inverted repeat, interleaved repeat.


Department of Computer Science and Engineering, Thapar University, Patiala, Punjab, 147004, India.

Graphical Abstract:

Read Full-Text article