Difference between revisions of "Dynamic Programming"

From Biowiki
Jump to: navigation, search
(Imported from TWiki)
(No difference)

Revision as of 09:57, 3 October 2007

Dynamic programming (DP) is the name for a class of problems that can be solved by recursively breaking them into subproblems.

In bioinformatics, DP is most commonly encountered in the context of sequence alignment (Smith Waterman, Needleman Wunsch etc.), Stochastic Grammar algorithms (the Viterbi, Forward Backward, Posterior Decoding and Pairwise Posterior Decoding algorithms in Hidden Markov Models, the Inside Outside algorithm in Stochastic Context Free Grammars, etc.) and in likelihood phylogeny (e.g. the Felsenstein Pruning algorithm).

-- Ian Holmes - 03 Oct 2007