CSAIL Event Calendar: Previous Series
Efficiently computing the landscape of locally optimal RNA secondary structures
Speaker: Peter Clote , Biology Dept/ Boston College
Relevant URL: http://www-math.mit.edu/compbiosem/
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.