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

sequence alignmentsparse dynamic programmingrecurrence equations

Mathematics Subject Classification ID

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

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

(18)

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

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)