Dynamic Programming

From Biowiki
Jump to: navigation, search

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