Sparse dynamic programming I: linear cost functions

David Eppstein, Zvi Galil, Raffaele Giancarlo, and Giuseppe F. Italiano
J. ACM 39(3):519–545, Jul 1992
Tech. report CUCS-471-89, Columbia Univ., Computer Science Dept., 1989
Mathematical Reviews 93i:90107a
http://www.acm.org/pubs/citations/journals/jacm/1992-39-3/p519-eppstein/

Cited by:

• On-line dynamic programming with applications to the prediction of RNA secondary structure
• Text Algorithms
• Fast sequential and parallel dynamic programming
• Dynamic programming with convexity, concavity and sparsity
• Chaining multiple-alignment fragments in sub-quadratic time
• New algorithms for the longest common subsequence problem
• Dynamic programming: special cases
• Linear space algorithms that build local alignments from fragments
• Guest editor's forword to special issue on computational molecular biology
• Longest common subsequences
• A local alignment tool for very long DNA-sequences
• Expected Length of Longest Common Subsequences
• Computational molecular biology
• Alignment requirements for NCBI's genomes division
• A new flexible algorithm for the longest common subsequence problem
• Local multiple alignment via subgraph enumeration
• Chaining multiple-alignment blocks
• Comparison algorithm of protein sequences by introducing a lookup table
• Dictionnaires et Lexiques: Methodes et Algorithmes
• Protein structure alignment using dynamic programming and iterative improvement
• Computing similarity between RNA strings
• Longest common subsequence from fragments via sparse dynamic programming
• All highest scoring paths in weighted grid graphs and their application to finding all approximate repeats in strings
• Efficient algorithms for approximate string matching with swaps
• Efficient computation of all longest common subsequences
• Approximation of staircases by staircases
• A space-efficient algorithm for aligning large genomic sequences
• Efficient large-scale sequence comparison by locality-sensitive hashing
• A heuristic algorithm for multiple sequence alignment based on blocks
• A sub-quadratic sequence alignment algorithm for unrestricted cost matrices
• A simple and space-efficient fragment-chaining algorithm for alignment of DNA and protein sequences
• Sparse dynamic programming for longest common subsequence from fragments
• Algorithms for transposition invariant string matching
• A hierarchical approach to aligning collinear regions of genomes
• Sparse LCS common substring alignment
• Sparse normalized local alignment
• Recent developments in linear-space alignment methods: a survey
• Efficient computation of gap-weighted string kernels on large alphabets
• L'espoir est cette chose avec des plumes — Algorithmes combinatoires et biologie moléculaire
• A local chaining algorithm and its applications in comparative genomics
• Multiple genome aligment: chaining algorithms revisited
• Glocal alignment: finding rearrangements during alignment
• Finding anchors for genomic sequence comparison
• Functional Sequence Comparison