# Dynamic Programming

From Biowiki

Revision as of 23:42, 1 January 2017 by Move page script (talk | contribs) (Move page script moved page DynamicProgramming to Dynamic Programming: Rename from TWiki to MediaWiki style)

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