Title: Corpus based learning of stochastic, context-free grammars combined with Hidden Markov Models for tRNA modelling

Authors: Juan Miguel Garcia-Gomez, Jose Miguel Benedi, Javier Vicente, Montserrat Robles

Addresses: Informatica Medica-BET, Polytechnic University of Valencia, Camino de Vera s/n, Valencia, 46022, Spain. ' Dpto. Sistemas Informaticos y Computacion, Polytechnic University of Valencia, 9, Camino de Vera s/n, Valencia, 46022, Spain. ' Informatica Medica-BET, Polytechnic University of Valencia, Camino de Vera s/n, Valencia, 46022, Spain. ' Informatica Medica-BET, Polytechnic University of Valencia, Camino de Vera s/n, Valencia, 46022, Spain

Abstract: In this paper, a new method for modelling tRNA secondary structures is presented. This method is based on the combination of stochastic context-free grammars (SCFG) and Hidden Markov Models (HMM). HMM are used to capture the local relations in the loops of the molecule (nonstructured regions) and SCFG are used to capture the long term relations between nucleotides of the arms (structured regions). Given annotated public databases, the HMM and SCFG models are learned by means of automatic inductive learning methods. Two SCFG learning methods have been explored. Both of them take advantage of the structural information associated with the training sequences: one of them is based on a stochastic version of the Sakakibara algorithm and the other one is based on a Corpus based algorithm. A final model is then obtained by merging of the HMM of the nonstructured regions and the SCFG of the structured regions. Finally, the performed experiments on the tRNA sequence corpus and the non-tRNA sequence corpus give significant results. Comparative experiments with another published method are also presented.

Keywords: RNA; secondary structure modelling; language modelling; grammatical inference; stochastic context-free grammars; SCFG; Hidden Markov Models; HMM; syntactic pattern recognition; bioinformatics; corpus based learning; tRNA secondary structures; automatic inductive learning; tRNA sequences.

DOI: 10.1504/IJBRA.2005.007908

International Journal of Bioinformatics Research and Applications, 2005 Vol.1 No.3, pp.305 - 318

Published online: 30 Sep 2005 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article