Sequence alignment methods often use something called a 'dynamic programming' algorithm. What is dynamic programming and how does it work?
This is a preview of subscription content, access via your institution
Access options
Subscribe to this journal
Receive 12 print issues and online access
206,07 € per year
only 17,17 € per issue
Buy this article
- Purchase on SpringerLink
- Instant access to full article PDF
Prices may be subject to local taxes which are calculated during checkout
References
Bellman, R.E. Eye of the Hurricane: An Autobiography (World Scientific, Singapore, 1984).
Author information
Authors and Affiliations
Supplementary information
Supplementary Note
An example of global sequence alignment by dynamic programming. (C 7 kb)
The program is ANSI C and should compile on any machine that has a C compiler, with a command line like: gcc -o global global.c
To run the program: ./global
To change the sequences or the scoring system, you have to edit the appropriate #define's at the top of the program, and recompile. This is meant to be a simple working example of the mechanics of dynamic programming sequence alignment. The details of reading FASTA files and such are left as an exercise to the reader. Any questions about this program should be addressed directly to the author.
Further study
Further study
To study a working example, you can download a small, bare-bones C implementation of this algorithm (see Supplementary Note). I used this C program to generate Figure 1.
Rights and permissions
About this article
Cite this article
Eddy, S. What is dynamic programming?. Nat Biotechnol 22, 909–910 (2004). https://doi.org/10.1038/nbt0704-909
Issue Date:
DOI: https://doi.org/10.1038/nbt0704-909
