Technical reports:
Speeding up Dynamic Programming with Application to the Computation of RNA Structure
David Eppstein; Zvi Galil; Raffaele Giancarlo
Downloads:
- Title:
- Speeding up Dynamic Programming with Application to the Computation of RNA Structure
- Author(s):
-
Eppstein, David
Galil, Zvi
Giancarlo, Raffaele - Date:
- 1988
- Type:
- Technical reports
- Department:
- Computer Science
- Permanent URL:
- http://hdl.handle.net/10022/AC:P:11945
- Series:
- Columbia University Computer Science Technical Reports
- Part Number:
- CUCS-327-88
- Publisher:
- Department of Computer Science, Columbia University
- Publisher Location:
- New York
- Abstract:
- 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.
- Subject(s):
- Computer science
- Item views:
- 250