Sparse dynamic programming I
David Eppstein, Zvi Galil, Raffaele Giancarlo et al. · Journal of the ACM · 1992
Dynamic programming solutions to a number of different recurrence equations for sequence comparison and for RNA secondary structure prediction are considered. These recurrences are defined over a number of points that is quadratic in the input size; however only a sparse set matters for the result. Efficient algorithms for these problems are given, when the weight functions used in the recurrences are taken to be linear. The time complexity of the algorithms depends almost linearly on the number of points that need to be considered; when the problems are sparse this results in a substantial speed-up over known algorithms.
Cited by 153 works. doi:10.1145/146637.146650 Open-access PDF
Authors
References
- The Design and Analysis of Computer Algorithms
- A general method applicable to the search for similarities in the amino acid sequence of two proteins
- Rapid and Sensitive Protein Similarity Searches
- The Art of Computer Programming: Volume 3: Sorting and Searching
- Rapid similarity searches of nucleic acid and protein data banks.
- Some biological sequence metrics
- Data Structures and Network Algorithms
- Linear pattern matching algorithms
- Data Structures and Algorithms
- A Space-Economical Suffix Tree Construction Algorithm