THE APPLICATION OF STOCHASTIC CONTEXT-FREE GRAMMARS TO FOLDING, ALIGNING AND MODELING HOMOLOGOUS RNA SEQUENCES

摘要: Stochastic context-free grammars (SCFGs) are applied to the problems of folding, aligning and modeling families homologous RNA sequences. SCFGs capture sequences'' common primary secondary structure generalize hidden Markov models (HMMs) used in related work on protein DNA. The novel aspect this is that SCFG parameters learned automatically from unaligned, unfolded training A generalization HMM forward-backward algorithm introduced do this. new algorithm, Tree-Grammar EM, based tree faster than previously proposed inside-outside produced a model we tested transfer (tRNA) family. Results show after having been trained as few 20 tRNA sequences only two subfamilies (mitochondrial cytoplasmic), can discern general similar-length other kinds, find sequences, produce multiple alignments large sets Our results suggest potential improvements D- T-domains some mitochdondrial tRNAs cannot be fitted into canonical structure.