✦ LIBER ✦
Speeding Up Dynamic Programming without Omitting any Optimal Solution and Some Applications in Molecular Biology
✍ Scribed by Norbert Blum
- Publisher
- Elsevier Science
- Year
- 2000
- Tongue
- English
- Weight
- 317 KB
- Volume
- 35
- Category
- Article
- ISSN
- 0196-6774
No coin nor oath required. For personal study only.
✦ Synopsis
We extend the algorithm of Galil and Giancarlo, which speeds up dynamic programming in the case of concave cost functions, such that a compact representation of all optimal solutions is computed. Compared to the Galil᎐Giancarlo algorithm our time bound grows only by a small constant factor. With a compact representation, we develop efficient algorithms for the solution of problems in molecular biology concerning the computation of all optimal local alignments and all optimal subalignments in genetic sequences.