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
$209.00 per year
only $17.42 per issue
Rent or buy this article
Prices vary by article type
from$1.95
to$39.95
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
This article is cited by
-
Mechanisms underlying pathological cortical bursts during metabolic depletion
Nature Communications (2023)
-
Circular mitochondrial-encoded mRNAs are a distinct subpopulation of mitochondrial mRNA in Trypanosoma brucei
Scientific Reports (2023)
-
Non-myopic multipoint multifidelity Bayesian framework for multidisciplinary design
Scientific Reports (2023)
-
A Review of Parallel Implementations for the Smith–Waterman Algorithm
Interdisciplinary Sciences: Computational Life Sciences (2022)
-
DP-TABU: an algorithm to solve single-depot multi-line vehicle scheduling problem
Complex & Intelligent Systems (2022)