Sparse dynamic programming I

DOI10.1145/146637.146650zbMath0807.90120OpenAlexW1987042978WikidataQ61609659 ScholiaQ61609659MaRDI QIDQ4302802

David Eppstein, Giuseppe F. Italiano, Raffaele Giancarlo, Zvi Galil

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

time complexityrecurrence equationssparsitysequence alignmentsequence comparisonRNA secondary structure prediction

Mathematics Subject Classification ID

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

Related Items (22)

Using Minimum Path Cover to Boost Dynamic Programming on DAGs: Co-linear Chaining Extended ⋮ New tabulation and sparse dynamic programming based techniques for sequence similarity problems ⋮ Fast algorithms for finding disjoint subsequences with extremal densities ⋮ Linear-space algorithms that build local alignments from fragments ⋮ Longest common subsequence between run-length-encoded strings: a new algorithm with improved parallelism ⋮ Co-linear chaining with overlaps and gap costs ⋮ Longest common subsequences ⋮ Sequence to graph alignment using gap-sensitive co-linear chaining ⋮ A Linear-Time n ^0.4 -Approximation for Longest Common Subsequence ⋮ Fast Algorithms for Computing Tree LCS ⋮ An efficient algorithm for LCS problem between two arbitrary sequences ⋮ Dynamic programming with convexity, concavity and sparsity ⋮ Efficient algorithms for the longest common subsequence in \(k\)-length substrings ⋮ Finding a longest common subsequence between a run-length-encoded string and an uncompressed string ⋮ Constrained sequence alignment ⋮ Finding common structured patterns in linear graphs ⋮ A sparse dynamic programming algorithm for alignment with non-overlapping inversions ⋮ Unnamed Item ⋮ Fast algorithms for computing tree LCS ⋮ Sparse LCS common substring alignment ⋮ Efficient algorithms for approximate string matching with swaps ⋮ A simple and space-efficient fragment-chaining algorithm for alignment of DNA and protein sequences

This page was built for publication: Sparse dynamic programming I