About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Journal of Algorithms
Paper
On-line dynamic programming with applications to the prediction of RNA secondary structure
Abstract
An on-line problem is a problem where each input is available only after certain outputs have been calculated. The usual kind of problem, where all inputs are available at all times, is referred to as an off-line problem. We present an efficient algorithm for Waterman's problem, an on-line two-dimensional dynamic programming problem that is used for the prediction of RNA secondary structure. Our algorithm uses as a module an algorithm for solving a certain on-line one-dimensional dynamic programming problem. The time complexity of our algorithm is n times the complexity of the on-line one-dimensional dynamic programming problem. For the concave case, we present a linear time algorithm for on-line searching in totally monotone matrices which is a generalization of the on-line one-dimensional problem. This yields an optimal O(n2) time algorithm for the on-line two-dimensional concave problem. The constants in the time complexity of this algorithm are fairly small, which make it practical. For the convex case, we use an O(nα(n)) time algorithm for the on-line one-dimensional problem, where α(·) is the functional inverse of Ackermann's function. This yields an O(n2α(n)) time algorithm for the on-line two-dimensional convex problem. Our techniques can be extended to solve the sparse version of Waterman's problem. We obtain an O(n + h log min{h, n2 h}) time algorithm for the sparse concave case, and an O(n + hα(h))log min{h, n2 h}) time algorithm for the sparse convex case, where h is the number of possible base pairs in the RNA structure. All our algorithms improve on previously known algorithms. © 1991.