CSAIL Event Calendar: Previous Series

Efficiently computing the landscape of locally optimal RNA secondary structures

Speaker: Peter Clote , Biology Dept/ Boston College
Date: March 1 2004
Time: 11:30AM to 12:45PM
Location: 2-338
Host: P Clote, BC & B. Berger MIT/ CSAIL

We make a novel contribution to the theory of biopolymer folding, by developing an efficient algorithm to compute the number of locally optimal secondary structures of an RNA molecule, with respect to the Nussinov-Jacobson energy model. Given an RNA molecule a1,...,an and integer k>0, a k-locally optimal secondary structure S is a secondary structure on a1,...,an which has k fewer base pairs than the maximum possible number, yet for which no basepairs can be added without violation of the definition of secondary structure (e.g. introducing a pseudoknot). Despite the fact that the number NumStr(k) of k-locally optimal structures for a given RNA molecule in general exponential in n, we present an algorithm running in time O(n^4) and space O(n^3), which computes NumStr(k) for all k.

Structurally important RNA, such as SECIS elements, hammerhead ribozymes, tRNA, all have a markedly different distribution of k-locally optimal structures than that of random RNA of the same dinucleotide frequency, suggesting that molecular evolution has not only favored low minimum free energy of native state but has additionally optimized the folding landscape.
Refreshments: 11:00 am in the Applied Mathematics Common Room at MIT's Building 2, Room 349
MIT
Department of Mathematics
& The Theory of
Computation Group
At CSAIL

See other events that are part of Bioinformatics Seminar Series Spring 2004

See other events happening in March 2004