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

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

Volume: 11 Issue: 4

Author(s): Nidhi Kalra and Ajay Kumar

Affiliation:

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

Abstract: 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.

Cite this article as:

Kalra Nidhi and Kumar Ajay, State Grammar and Deep Pushdown Automata for Biological Sequences of Nucleic Acids, Current Bioinformatics 2016; 11 (4) . https://dx.doi.org/10.2174/1574893611666151231185112