Speeding up dynamic programming with applications to molecular biology (Q1121182)

Consider the problem of computing \[ E[j]=\min_{0\leq k\leq j- 1}\{D[k]+w(k,j)\},\quad 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]. Obviously, it can be solved in time \(O(n^ 2)\), and for a general weight function no better algorithm is possible. In this paper, two dual cases that arise in applications are considered: In the concave case, the weight function satisfies the quadrangle inequality: \[ w(k,j)+w(\ell,j')\leq w(\ell,j)+w(k,j'),\quad for\quad all\quad k\leq \ell \leq j\leq j'. \] In the convex case, the weight function satisfies the inverse quadrangle inequality. In both cases it is shown 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 \(\ell\) and k, \(\ell <k\), the real number a, the smallest zero of \(f(x)=w(\ell,x)-w(k,x)-a\) which is larger than k can be found in constant time. The two algorithms speed up several dynamic programming routines that solve as a subproblem the problem above. The speed-up is from \(O(n^ 3)\) to \(O(n^ 2 \log n)\) or \(O(n^ 2)\). Applications include algorithms for comparing DNA sequences and algorithms used in speech recognition and geology. One typical problem is the following: Given the cost of substituting any pair of symbols and a convex cost function g for gaps (where g(r) is the cost of a gap of size r), compute the modified edit distance between the two given sequences.