Dynamic programming

Dynamic programming is a clever methodology used for solving very complex problems.

The basic idea is like construction works: you build a bigger wall by placing new bricks on existing ones. In dynamic programming, you identify a new solution by extending a previous one. Divide et impera to its best.

In the fields of bioinformatics and computational biology, two great examples of dynamic programming are used: alignment algorithms and Hidden Markov Models. I’m going to present some of them in the next posts, for now I would like to focus on the basic idea of dynamic programming, by using a very simple example.

At the basic of alignment and HMM algorithms you have a table. What you have to do is filling the table using some rules: you start from one side of the table, apply the rules to the next row or column and keep going on until the table is filled.

Let’s try the following: create a table of 5 rows and 10 columns.

As first step, you should always fill at leas a value into the table (initialization step). In our example, we put the numbers from 1 to 5 into the first column.

Now it is time to apply the iterative step: we have to repeat the same operation on all cells, starting from one side of the table and moving on.

In our example, the cell should contain the result of the following formula: value on the left times row number.

The first row should read as 1,1,1,1,1; the second 2,4,8,16,32 and so on. As you can see, each row contains the powers of the first number. What you needed to build it was just a local information: the previous value. So the 16 in the second row comes from the 8 in the third column, while the 16 in the fourth row is evaluated from the 4 on its left.

This is a very simple example, real dynamic programming algorithms may use the whole preceding column, complex mathematical functions on the previous values and so on. But the strategy is the same: if I change my function to “The maximum value on the preceding column times the minimum one, minus row number”, I would proceed in the same way: filling one column at the time, just using a different function.

 

Advertisements

4 comments on “Dynamic programming

  1. clodovendro says:

    The way you describe Hidden Markov Models they look a lot like cellular automata. Are they the same or there is some difference I did not spot from a quick reading?

    • Giuseppe says:

      I’m going to post about HMM in the next weeks, anyways the difference between HMM algorithms and cellular automata like Conway’s Game of Life is that in the latter you have a state (table) that changes over time, while in HMM you fill the table just once.

      • clodovendro says:

        Not fully convinced by your answer. If you take the “Rule 110” cellular automaton, you fill the table one row at the time, and each row is a function of the previous row only.

  2. […] the introduction on dynamic programming, I’m giving an example using Hidden Markov Models (HMM). Since I’m not here to teach […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s