* News


New algorithms for RNA: asymptotic Z-scores and kinetic traps

Peter Clote
Boston College

Tuesday, February 15, 2005
Walker 5113 - 4:00 p.m. to 5:00 p.m.
Refreshments in AE 401 at 3:30

Fifteen years ago, Le et al. showed that RNA stem-loop structures situated 3' to frameshift sites of retroviral gag-pol and pro-pol regions of several viruses (human immunodeficiency virus HIV-1, Rous sarcoma virus RSV, etc.) are thermodynamically stable and recognizable among positions 300 nucleotides upstream and downstream of the frameshift site. Extending this work and that of Workman and Krogh, and Rivas and Eddy, we show that structural RNA has lower folding energy than random RNA of the same dinucleotide frequency. Applying Kingman's ergodicity theorem on subadditive stochastic processes, we prove that there exist asymptotic limits and sigma, respectively for the mean and standard deviation of the minimum free energy per nucleotide for random RNA generated by a first-order Markov chain from given dinucleotide frequencies. This allows a very fast whole genome, moving window asymptotic Z-score computation, which could be used as a first filter in the identification of potential RNA genes.
Not only does structural RNA have lower folding energy than random RNA, but it appears that natural selection has evolved nucleotide sequences of structural RNA to have a distinct distribution of kinetic traps in the folding landscape, when contrasted with random RNA. Specifically, for each k, define a k-suboptimal secondary structure of a given RNA sequence to be a secondary structure having k fewer base pairs than the optimum structure, yet for which one cannot add any base pairs without introducing a pseudoknot. We describe a new algorithm running in O(n4) time and O(n3) space, which computes for a given RNA sequence a1,...,an and all k, the number of k-suboptimal secondary structures on a1,...,an. The resulting density of states histogram for structurally important RNAs (tRNAs, hammerhead ribozymes, SECIS elements) shows a significant difference with that of RNAs of the same dinucleotide frequency, indicating more likely kinetic entrapment of random RNA.

Hosts: Michael Zuker, x6902 (Mathematical Sciences), Petros Drineas, x8265 (Computer Science)

Last updated: January 26, 2005