Speeding up dynamic programming with applications to molecular biology

AbstractConsider the problem of computing E[j]=min0⩽k⩽j−1 {D[k]+w(k,j)},j=1,…,n, where w is a given weight function, D[0] is given and for every k=1,…, n, D[k] is easily computable from E[k]. This problem appears as a subproblem in dynamic programming solutions to various problems. Obviously, it can be solved in time O(n2), and for a general weight function no better algorithm is possible.We consider two dual cases that arise in applications: In the concave case, the weight function satisfies the quadrangle inequality: w(k,j)+w(l,j′)⩽w(l,j)+w(k,j′) for all k⩽l⩽j⩽j′.In the convex case, the weight function satisfies the inverse quadrangle inequality.In both cases we show how to use the assumed property of w to derive an O(n log n) algorithm. Even better, linear-time algorithms are obtained if w satisfies the following additional closest zero property: for every two integers l and k, l