Title: An O(n^5) Algorithm for MFE Prediction of Kissing Hairpins and 4-Chains in Nucleic Acids
Speaker: Hosna Jabbari
Department of Computer Science, University of British Columbia

Efficient methods for prediction of minimum free energy (MFE) nucleic secondary structures are widely used, both to better understand structure and function of biological RNA's and to design novel nano-structures. Here, we present a new algorithm for MFE secondary structure prediction, which significantly expands the class of structures that can be handled in O(n^5) time. Our algorithm can handle H-type pseudoknotted structures, kissing hairpins, and chains of four overlapping stems, as well as nested substructures of these types.