Sparse dynamic programming I
DOI10.1145/146637.146650zbMATH Open0807.90120OpenAlexW1987042978WikidataQ61609659 ScholiaQ61609659MaRDI QIDQ4302802FDOQ4302802
Authors: David Eppstein, Giuseppe F. Italiano, Zvi Galil, R. Giancarlo 
Publication date: 21 August 1994
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/146637.146650
Recommendations
sparsitytime complexitysequence alignmentRNA secondary structure predictionsequence comparisonrecurrence equations
Applications of mathematical programming (90C90) Protein sequences, DNA sequences (92D20) Dynamic programming (90C39) Abstract computational complexity for mathematical programming problems (90C60)
Cited In (29)
- Efficient algorithms for approximate string matching with swaps
- Finding common structured patterns in linear graphs
- Fast algorithms for finding disjoint subsequences with extremal densities
- Speeding up dynamic programming with applications to molecular biology
- Longest common subsequences
- Title not available (Why is that?)
- Title not available (Why is that?)
- Sparse LCS common substring alignment
- Sequence to graph alignment using gap-sensitive co-linear chaining
- Fast algorithms for computing tree LCS
- A simple and space-efficient fragment-chaining algorithm for alignment of DNA and protein sequences
- Dynamic programming with convexity, concavity and sparsity
- Fast Algorithms for Computing Tree LCS
- New tabulation and sparse dynamic programming based techniques for sequence similarity problems
- Longest common subsequence between run-length-encoded strings: a new algorithm with improved parallelism
- Efficient algorithms for the longest common subsequence in \(k\)-length substrings
- Linear-space algorithms that build local alignments from fragments
- A Linear-Time n 0.4 -Approximation for Longest Common Subsequence
- Title not available (Why is that?)
- Co-linear chaining with overlaps and gap costs
- An efficient algorithm for LCS problem between two arbitrary sequences
- Finding a longest common subsequence between a run-length-encoded string and an uncompressed string
- A discipline of dynamic programming over sequence data
- A sparse dynamic programming algorithm for alignment with non-overlapping inversions
- Rapid dynamic programming algorithms for RNA secondary structure
- Using Minimum Path Cover to Boost Dynamic Programming on DAGs: Co-linear Chaining Extended
- Cache efficient simple dynamic programming
- Constrained sequence alignment
- Polynomial-delay enumeration of maximal common subsequences
This page was built for publication: Sparse dynamic programming I
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4302802)
