Sparse dynamic programming II

DOI10.1145/146637.146656MaRDI QIDQ4302803zbMATH OpenOpenAlexDBLPWikidataFDO

Authors David Eppstein, Giuseppe F. Italiano, Zvi Galil, R. Giancarlo

Publication date 13 July 1995

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/146637.146656

zbMATH Keywords

recurrence equationssequence alignmentsparse dynamic programming

Mathematics Subject Classification ID

Dynamic programming (90C39) Applications of mathematical programming (90C90) Protein sequences, DNA sequences (92D20)

Recommendations

• Sparse dynamic programming I
• scientific article; zbMATH DE number 432798
• Speeding up dynamic programming with applications to molecular biology
• On-line dynamic programming with applications to the prediction of RNA secondary structure

Cited in

(21)

• Speeding up dynamic programming with applications to molecular biology
• Dynamic programming with convexity, concavity and sparsity
• An improved algorithm for the longest common subsequence problem
• Approximate regular expression pattern matching with concave gap penalties
• Linear-space algorithms that build local alignments from fragments
• Co-linear chaining with overlaps and gap costs
• An almost quadratic time algorithm for sparse spliced alignment
• Chaining algorithms for multiple genome comparison
• Two algorithms for LCS consecutive suffix alignment
• scientific article; zbMATH DE number 432797 (Why is no real title available?)
• scientific article; zbMATH DE number 432798 (Why is no real title available?)
• scientific article; zbMATH DE number 4126696 (Why is no real title available?)
• Sparse dynamic programming I
• A hyper-heuristic for the longest common subsequence problem
• Speeding Up Dynamic Programming without Omitting any Optimal Solution and Some Applications in Molecular Biology
• A sparse dynamic programming algorithm for alignment with non-overlapping inversions
• scientific article; zbMATH DE number 826057 (Why is no real title available?)
• On-line dynamic programming with applications to the prediction of RNA secondary structure
• Local multiple alignment via subgraph enumeration
• Sequence to graph alignment using gap-sensitive co-linear chaining
• A large neighborhood search heuristic for the longest common subsequence problem

This page was built for publication: Sparse dynamic programming II

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4302803)