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

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.