• Calendar

June 29, Tuesday
12:00 – 13:30

Imposing constraints in the form of a finite automaton or a regular expression is an effective way to incorporate additional a priori knowledge into sequence alignment procedures. With this motivation, Arslan introduced the Regular Language Constrained Sequence Alignment problem and proposed an $O(n^2t^4)$ time and $O(n^2t^2)$ space algorithm for solving it, where $n$ is the length of the input strings and $t$ is the number of states in the non deterministic automaton which is given as input. Chung et al. proposed a faster $O(n^2t^3)$ time algorithm for the same problem.

In this talk, I present an additional speed up to the algorithms for Regular Language Constrained Sequence Alignment by reducing their worst case time complexity bound to $O(n^2t^3/log t)$. This is done by establishing an optimal bound on the size of Straight-Line Programs solving the maxima computation subproblem of the basic dynamic programming algorithm.

In addition, I present a another solution we have studied, which is based on a Steiner Tree computation. While this solution does not yield an improvement in the worst case, our simulations show that both approaches are efficient in practice, especially when the input automata are dense.

Joint work with Gregory Kucherov and Michal Ziv-Ukelson.