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

Author(s): Nidhi Kalra , Ajay Kumar .

Journal Name: Current Bioinformatics

Volume 11 , Issue 4 , 2016

Become EABM
Become Reviewer

Graphical Abstract:


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.

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

Rights & PermissionsPrintExport Cite as

Article Details

VOLUME: 11
ISSUE: 4
Year: 2016
Page: [470 - 479]
Pages: 10
DOI: 10.2174/1574893611666151231185112
Price: $58

Article Metrics

PDF: 21
HTML: 2
EPUB: 1
PRC: 1