Speeding up dynamic programming with applications to molecular biology
type: Item
instance of: scholarly article
title: Speeding up dynamic programming with applications to molecular biology
zbMATH Open document ID: 0673.90090
author: Zvi Galil
author: R. Giancarlo
published in: Theoretical Computer Science
publication date: 1989-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 90C39
Mathematics Subject Classification ID: 68T10
Mathematics Subject Classification ID: 92D10
Mathematics Subject Classification ID: 65K05
zbMATH DE Number: 4102840
zbMATH Keywords: weight function
zbMATH Keywords: linear-time algorithms
zbMATH Keywords: closest zero property
zbMATH Keywords: DNA sequences
zbMATH Keywords: speech recognition
zbMATH Keywords: geology
MaRDI profile type: Publication
full work available at URL: 0304-3975(89)90101-1
OpenAlex ID: W2087817903
cites work: The Least Weight Subsequence Problem
cites work: Optimum binary search trees
cites work: Breaking paragraphs into lines
cites work: Sequence comparison with concave weighting functions
cites work: General methods of sequence comparison
cites work: The concave least-weight subsequence problem revisited
cites work: Speed-Up in Dynamic Programming
DOI: 10.1016/0304-3975(89)90101-1
DOI: 10.7916/D8902BWC
description: scientific article; zbMATH DE number 4102840