Dynamic Programming
Dynamic programming is a mathematical way of looking at a problem by considering the problem in reverse order. The word programming in the term does not refer to writing computer programs. Rather, dynamic programming is a mathematical term to describe a set of rules used to solve a problem. These rules do not necessarily have to be written in a computer language
Computerized dynamic programming is, nonetheless, a powerful problem-solving tool. It has found a useful niche in the biological sciences as a means of deciphering order in biological systems.
Dynamic programming was first described over forty years ago by the American mathematician Richard Bellman. In the years since its inception, dynamic programming has been applied to problems ranging from the analysis of biological systems to the game of darts.
In biological computing, also called bioinformatics, dynamic programming has been a powerful technique. Genomic analysis probably would not have been possible without the power of dynamic programming. Only a few percent of the three gigabases of the human genome sequence code for proteins. For each of these proteins, the DNA template is typically not in one contiguous piece. Rather, it is typically broken up into many subsequences that are separated by physically large non-coding regions. Predicting protein sequences from genomic sequences requires the identification of all the protein-coding sequences, and the knowledge of how they are joined together to form genes. This subject is called gene-structure prediction. An important part of this process is the use of so-called optimization algorithms based on dynamic programming. The approach uses sequence alignment to reveal the function of regions of deoxyribonucleic acid and the shape and function of proteins. Comparison of the nucleic acid or protein in question with existing counterparts is helpful. Sequence comparison, involving sequence alignment, is a useful tool in the analyses.
Sequence alignment is a scheme of writing one sequence on top of another where the residues in one position are thought to have a common evolutionary origin. The occurrence of the same sequence may indicate the conservation of an important functional region during evolution. Sequences are not always exact, due to insertions or deletions of component parts over time. A letter or a stretch of letters in a sequence may be paired up with dashes in the other sequence to signify such an insertion or deletion. Because an insertion in one sequence can always be seen as a deletion in the other sequence, the term index is used
Dynamic programming examines the region under consideration and scores the patterns of homology found. Because even regions that are unrelated can display some random sequence similarities, a progressive mean of scoring similarity is necessary. In dynamic programming this is accomplished by assigning 0 to a match, some negative number to a mismatch and a larger negative number to an index. By adding these values along an alignment a score can be obtained for the alignment. The alignment with the minimum score is considered to be the true alignment of the sequences. Dynamic programming utilizes an algorithm to arrive at the minimum score without having to examine and score all the possible alignment combinations of the two sequences.
There are a number of characteristics that are common to all dynamic programming problems. The problem can be divided into a number of stages with a decision required at each stage. A stage often can itself contain a number of components, called states. So, there can end up being a number of decisions in each stage, corresponding to decisions that must be made at the various states. Dynamic programming, in effect, sorts out the order of the various stages and states in order to make the decision making process logical so that a conclusion can be reached. The sorting out of this information in a non-biological problem somewhat mirrors the examination and prioritizing of sequence information in a biological setting.
In general, the proper application of dynamic programming can speed up the solving of problems that require computational searches on an exponential space of solutions. The increased speed comes with a cost--the memory requirement can be large. In some cases, the memory grows at the same rate as the running time to solve the problem. For large scale sequence analyses, considerable computing power is required.
This is the complete article, containing 705 words
(approx. 2 pages at 300 words per page).
