
News
Colloquia
New algorithms for RNA: asymptotic Zscores 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 stemloop structures situated 3'
to frameshift sites of retroviral gagpol and propol regions of several viruses
(human immunodeficiency virus HIV1, 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 firstorder Markov chain from
given dinucleotide frequencies. This allows a very fast whole genome, moving window
asymptotic Zscore 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 ksuboptimal 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(n^{4}) time and
O(n^{3}) space, which
computes for a given RNA sequence a_{1},...,a_{n} and all k, the number of ksuboptimal
secondary structures on a_{1},...,a_{n}. 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

