Difference between revisions of "Dynamic Programming"

From Biowiki
Jump to: navigation, search
(Imported from TWiki)
 
m (Move page script moved page DynamicProgramming to Dynamic Programming: Rename from TWiki to MediaWiki style)
 
(No difference)

Latest revision as of 23:42, 1 January 2017

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