Academic Commons

Reports

Speeding up Dynamic Programming with Application to the Computation of RNA Structure

Eppstein, David; Galil, Zvi; Giancarlo, Raffaele

We describe the solution of a two dimensional recurrence used to compute the secondary structure of RNA. A naive dynamic programming solution to this recurrence takes time O (n4); this time had previously been improved to O (n3). Our new algorithm makes use of the convexity of the energy functions for RNA secondary structure to reduce the time to O(n2 1og2 n). When the energy function is modeled by logarithms or other simple functions we solve the recurrence in time O(n2Iognloglogn). Our algorithms are simple and practical.

Subjects

Files

More About This Work

Academic Units
Computer Science
Publisher
Department of Computer Science, Columbia University
Series
Columbia University Computer Science Technical Reports, CUCS-327-88
Published Here
December 7, 2011
Academic Commons provides global access to research and scholarship produced at Columbia University, Barnard College, Teachers College, Union Theological Seminary and Jewish Theological Seminary. Academic Commons is managed by the Columbia University Libraries.