Title: Dynamic Programming in Secondary Structure Inference

Abstract: Given an RNA sequence, secondary structure inference is the problem of predicting that sequence's base pairs. A variety of methods for this problem exist; among the most popular are minimum free energy (MFE) methods, which assign each possible secondary structure an energy based on the presence or absence of various substructures, with negative energy structures being more likely to occur naturally. These methods then use dynamic programming to predict the lowest free energy structure(s) efficiently. We will give an introduction to dynamic programming, talk about why it is necessary for approaching this problem efficiently, and discuss some of the shortcomings of the method. If time permits, we will also talk about connections to machine learning methods for secondary structure prediction.