TY - GEN

T1 - On-line dynamic programming with applications to the prediction of RNA secondary structure

AU - Larmore, Lawrence L.

AU - Schieber, Baruch

N1 - Copyright:
Copyright 2018 Elsevier B.V., All rights reserved.

PY - 1990/1/1

Y1 - 1990/1/1

N2 - We define an on-line problem to be 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 the 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 the on-line one dimensional dynamic programming problem. The time complexity of our algorithm is n times the complexity of the online one dimensional dynamic programming problem. For the concave case, we present a linear time algorithm for 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. Both algorithms improve on previously known algorithms.

AB - We define an on-line problem to be 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 the 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 the on-line one dimensional dynamic programming problem. The time complexity of our algorithm is n times the complexity of the online one dimensional dynamic programming problem. For the concave case, we present a linear time algorithm for 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. Both algorithms improve on previously known algorithms.

UR - http://www.scopus.com/inward/record.url?scp=23044464355&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=23044464355&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:23044464355

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 503

EP - 512

BT - Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1990

PB - Association for Computing Machinery

T2 - 1st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1990

Y2 - 22 January 1990 through 24 January 1990

ER -