Ab initio identification of regulatory RNAs using information-theoretic uncertainty

Abstract

RNA regulatory elements play a significant role in gene regulation. Riboswitches are regulatory elements which function by forming a ligand induced alternative fold that controls access to ribosome binding sites or other regulatory sites in RNA. Traditionally, riboswitches have been identified based on sequence and structural homology. In this work, in an attempt to devise an ab initio method for identification of regulatory elements, mainly riboswitches, we derive and implement Shannon's entropy of the SCFG ensemble on an RNA sequence in polynomial time for both structurally ambiguous and unambiguous grammars. We then evaluate the significance of this new measure of structural entropy in identifying riboswitches. Finally, simple lightweight stochastic context-free grammar folding models assign significant values to long extensive secondary structures in Bacillus subtilis.