Genomics Inform.  2012 Dec;10(4):266-270. 10.5808/GI.2012.10.4.266.

Developing JSequitur to Study the Hierarchical Structure of Biological Sequences in a Grammatical Inference Framework of String Compression Algorithms

• Galbadrakh B
• Lee KE
• Park HS

• KMID: 2053308
• DOI: http://doi.org/10.5808/GI.2012.10.4.266

Abstract

Grammatical inference methods are expected to find grammatical structures hidden in biological sequences. One hopes that studies of grammar serve as an appropriate tool for theory formation. Thus, we have developed JSequitur for automatically generating the grammatical structure of biological sequences in an inference framework of string compression algorithms. Our original motivation was to find any grammatical traits of several cancer genes that can be detected by string compression algorithms. Through this research, we could not find any meaningful unique traits of the cancer genes yet, but we could observe some interesting traits in regards to the relationship among gene length, similarity of sequences, the patterns of the generated grammar, and compression rate.

Keyword

context-free grammar; formal language theory; natural language processing; stochastic modeling

MeSH Terms

Genes, Neoplasm
Motivation
Natural Language Processing