Dynamic Programming

Abstract

Dynamic programming is an optimization technique used in mathematics and computer science. It solves problems by recursively solving the subproblems that have overlapping substructures and then combining the solutions to these subproblems.

Keywords: optimization algorithm; sequence alignment; RNA secondary structure; gene‐finding; hidden Markov model

References

Altschul SF, Madden TL, Schaffer AA, et al. (1997) Gapped BLAST and PSI‐BLAST: a new generation of protein database search programs. Nucleic Acids Research 25: 3389–3402.

Durbin R, Eddy S, Krogh A and Mitchison G (1998) Biological Sequence Analysis. Cambridge, UK: Cambridge University Press.

Waterman MS (1995) Introduction to Computational Biology. London, UK: Chapman & Hall.

Further Reading

Cormen TH, Leiserson CE and Rivest RL (1993) Introduction to Algorithms. Cambridge, MA: MIT Press.

Gusfield D (1997) Algorithms on Strings, Trees, and Sequences. Cambridge, UK: Cambridge University Press.

Pearson WR and Lipman DJ (1988) Improved tools for biological sequence comparison. Proceedings of the National Academy of Sciences of the United States of America 85: 2444–2448.

Pevzner P (2000) Computational Molecular Biology. Cambridge, MA: MIT Press.

Web Links

GenBank ncbi.nlm.nih.gov/Genbank

Protein Data Bank rcsb.org/pdb

Contact Editor close
Submit a note to the editor about this article by filling in the form below.

* Required Field

How to Cite close
Chen, Ting, and Waterman, Michael(Sep 2005) Dynamic Programming. In: eLS. John Wiley & Sons Ltd, Chichester. http://www.els.net [doi: 10.1038/npg.els.0005254]