Checkpoint method for choice recovery in dynamic programming
Tóm tắt
Many dynamic programming algorithms consist of a ‘forward pass’ computation to optimize a cost function, followed by a ‘choice recovery’ computation to construct a configuration that optimizes the cost function. ‘Checkpointing’ is a method to perform choice recovery using limited storage. During a forward pass, checkpoints in an optimal configuration are identified. Then recursion is used to fill in the portions of an optimal configuration between successive checkpoints. Choosing the number of checkpoints to use mediates a tradeoff between storage and speed.
Tài liệu tham khảo
Chao, K.-M., Hardison, R.C., Miller, W., 1993. Constrained sequence alignment. Bull. Math. Biol. 55, 503–524.
Chao, K.-M., Hardison, R.C., Miller, W., 1994. Recent developments in linear-space alignment methods: a survey. J. Comput. Biol. 1, 271–291.
Chao, K.-M., Pearson, W.R., Miller, W., 1992. Aligning two sequences within a specified diagonal band. CABIOS 8, 481–487.
Cormen, T.H., Leiserson, C.E., Rivest, R.L., 1997. Introduction to Algorithms. MIT Press.
Gusfield, D., 1999. Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press.
Hirschberg, D.S., 1975. A linear space algorithm for computing longest common subsequences. Commun. Assoc. Comput. Mach. 18, 341–343.
Huang, X., Hardison, R.C., Miller, W., 1990. A space-efficient algorithm for local similarities. CABIOS 6, 373–381.
Myers, E.W., Miller, W., 1988. Optimal alignments in linear space. CABIOS 4, 11–17.