Speeding up dynamic programming with applications to molecular biology

DOI10.7916/D8902BWC 10.1016/0304-3975(89)90101-1; 10.7916/D8902BWCzbMath0673.90090OpenAlexW2087817903MaRDI QIDQ1121182

Zvi Galil, Raffaele Giancarlo

Publication date: 1989

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(89)90101-1

zbMATH Keywords

weight functionDNA sequencesspeech recognitionlinear-time algorithmsgeologyclosest zero property

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Dynamic programming (90C39) Pattern recognition, speech recognition (68T10) Genetics and epigenetics (92D10)

Related Items

List partitions, Finding least-weight subsequences with fewer processors, Online dynamic programming speedups, Approximate regular expression pattern matching with concave gap penalties, Linear-space algorithms that build local alignments from fragments, Categories, relations and dynamic programming, Computing a Hamiltonian path of minimum Euclidean length inside a simple polygon, The undecidability of the unrestricted modified edit distance, A linear-time algorithm for concave one-dimensional dynamic programming, An optimal algorithm with unknown time complexity for convex matrix searching, On the space complexity of some algorithms for sequence comparison, An algorithm for the sequence alignment with gap penalty problem using multiway divide-and-conquer and matrix transposition, Dynamic programming with convexity, concavity and sparsity, Identifying periodic occurrences of a template with applications to protein structure, Constrained sequence alignment, Sparse LCS common substring alignment, Reconstructing a history of recombinations from a set of sequences, Tree edit distance with gaps

Cites Work

• General methods of sequence comparison
• Sequence comparison with concave weighting functions
• Optimum binary search trees
• The Least Weight Subsequence Problem
• The concave least-weight subsequence problem revisited
• Breaking paragraphs into lines
• Speed-Up in Dynamic Programming