Sparse dynamic programming I

DOI10.1145/146637.146650MaRDI QIDQ4302802zbMATH OpenOpenAlexWikidataFDO

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

zbMATH Keywords

sparsitytime complexitysequence alignmentRNA secondary structure predictionsequence comparisonrecurrence equations

Mathematics Subject Classification ID

Applications of mathematical programming (90C90) Protein sequences, DNA sequences (92D20) Dynamic programming (90C39) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Sparse dynamic programming II
• scientific article; zbMATH DE number 432798
• scientific article; zbMATH DE number 826057
• Speeding up dynamic programming with applications to molecular biology

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
• scientific article; zbMATH DE number 7561345 (Why is no real title available?)
• Sparse LCS common substring alignment
• scientific article; zbMATH DE number 826057 (Why is no real title available?)
• 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
• scientific article; zbMATH DE number 432798 (Why is no real title available?)
• Co-linear chaining with overlaps and gap costs
• An efficient algorithm for LCS problem between two arbitrary sequences
• A discipline of dynamic programming over sequence data
• Finding a longest common subsequence between a run-length-encoded string and an uncompressed string
• A sparse dynamic programming algorithm for alignment with non-overlapping inversions
• Rapid dynamic programming algorithms for RNA secondary structure
• Constrained sequence alignment
• Cache efficient simple dynamic programming
• Using Minimum Path Cover to Boost Dynamic Programming on DAGs: Co-linear Chaining Extended
• 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)