Speeding up dynamic programming without omitting any optimal solution and some applications in molecular biology

We extend the algorithm of Galil and Giancarlo, which speeds up dynamic pro gramming in the case of concave cost functions, such that a compact represe ntation of all optimal solutions is computed. Compared to the. Galil-Gianca rlo algorithm our time bound grows only by a small constant factor. With a compact representation, we develop efficient algorithms for the solution of problems in molecular biology concerning the computation of all optimal lo cal alignments and all optimal subalignments in genetic sequences. (C) 2000 Academic Press.