Talks
Spring 2016

# Two Stories: Modeling RNA folding by ILP and Trying to Simulate the History Bound by ILP

Monday, May 9th, 2016 11:25 am – 12:00 pm

Modeling RNA Folding by ILP - Yelena Frid

The basic RNA folding problem translated to maximizing the number of non-crossing complementary nucleotide pairs, can be solved efficiently by dynamic programming, but the DP becomes more involved when we try to model more complex features of an RNA fold.Then, an ILP approach is more flexible and promising. In this talk I show how to model RNA folding with nucleotide stacks and pseudoknots, using integer linear programming.

Trying to Simulate the History Bound by ILP - Julia Matsieva

The History Bound is a lower bound on the number of recombinations needed in an Ancestral Recombination Graph, to derive an input binary matrix. The History Bound was first defined only via an algorithm which had super-exponential running time. That time was improved to exponential via dynamic programming. However, as is common in DP, the worst-case and best-case times are the same. We have developed two ILP approaches to computing the History Bound, in hopes that, unlike DP, typical executions would be more efficient than worst-case. In this talk I will detail an effort that expresses the original (but optimized) algorithm as an ILP. This is work in progress (translation - so far, it doesn't work very well).