Question 1

Why is it called “dynamic programming”?

Accepted Answer

You may be surprised, but sixty years ago, the word "programming" had nothing to do with computer programming, but instead referred to finding optimal programs, in the sense of finding a military schedule for logistics. In the 1950s, the inventor of dynamic programming, Richard Bellman, joined the RAND Corporation, which at the time was working on various contracts for the US Defense Department. At that time, the Secretary of Defense, Charles Wilson, was under pressure to reduce the military budget, including the research budget. Here is how Bellman described his interactions with Wilson and the birth of the term “dynamic programming”:
 
"[Wilson's] face would suffuse, he would turn red, and he would get violent if people used the term research in his presence. You can imagine how he felt, then, about the term mathematical… Hence, I felt I had to do something to shield Wilson and the Air Force from the fact that I was really doing mathematics inside the RAND Corporation. What title, what name, could I choose? In the first place I was interested in planning, in decision making, in thinking. But planning, is not a good word for various reasons. I decided therefore to use the word “programming”. I wanted to get across the idea that this was dynamic, this was multistage, this was time-varying I thought, lets kill two birds with one stone. Lets take a word that has an absolutely precise meaning, namely dynamic, in the classical physical sense. It also has a very interesting property as an adjective, and that is it's impossible to use the word dynamic in a pejorative sense. Try thinking of some combination that will possibly give it a pejorative meaning. It's impossible. Thus, I thought dynamic programming was a good name. It was something not even a Congressman could object to. So I used it as an umbrella for my activities."

Question 2

Is it possible to develop an iterative rather than recursive algorithm for OutputLCS?

Accepted Answer

Yes, and below is some pseudocode.  Instead of making recursive calls, we simply embed the algorithm's iterations within a while loop.

IterativeOutputLCS(Backtrack, v, w)
LCS ← an empty string
i ← length of string
j ← length of string w
while i > 0 and j > 0   
if Backtrack(i, j) = "↓"      
i ← i-1     else if Backtrack(i,j) = "→"      
j ← j-1     else if Backtrack(i,j) = "↘"      
LCS ← concatenate vi with LCS
i ← i-1      
j  ← j-1
return LCS

Question 3

Why do we favor vertical backtracking edges (over horizontal and diagonal) in OutputLCS?

Accepted Answer

All three types of backtracking edges (horizontal, vertical, and diagonal) are equally important; OutputLCS simply starts the analysis with vertical edges because it has to start somewhere! This will indeed bias the solutions if there are multiple longest common subsequences, in which case you may want to vary backtracking over multiple runs.

Question 4

If dynamic programming is so powerful, then why don’t we transform all recursive algorithms into dynamic programming algorithms?

Accepted Answer

Each recursive algorithm can be transformed into dynamic programming using a memoization technique that stores all results ever calculated by the recursive procedure in a table.
 
When the recursive procedure calls an input which was already used, the results are just fetched from the table instead of launching a recursive call. However, memoization is only useful if your recursive algorithm arrives to the same situations many times, like in the case of RecursiveChange. For example, memoization becomes not very useful for algorithms like HanoiTowers since it is rarely called on the same input. Despite the fact that memoization does not immediately lead to an efficient non-recursive  algorithm for the Towers of Hanoi, such algorithms do exist (see https://www.geeksforgeeks.org/iterative-tower-of-hanoi/).

Question 5

If there are many topological orders, which one should I use for computing alignments?

Accepted Answer

All topological orderings result in the same running time of your alignment algorithm, so you can choose any one you like.

Bioinformatics

Algorithms

Why is it called “dynamic programming”?

Is it possible to develop an iterative rather than recursive algorithm for OutputLCS?

Why do we favor vertical backtracking edges (over horizontal and diagonal) in OutputLCS?

If dynamic programming is so powerful, then why don’t we transform all recursive algorithms into dynamic programming algorithms?

If there are many topological orders, which one should I use for computing alignments?

FAQ Chapter 5

How Do We Compare Biological Sequences?