dynamic programming

[sandhya]

hi!friends please explain me the full concept of dynamic programming

[hokie]

The basic idea is to break down a problem into smaller problems. This sounds like divide and conquer. The difference is the manner in which the problem is broken down. What is noticed is that the smaller problems share part of the solution. Instead of recomputing each of these subproblems many times, the solution is computed whenever needed and reused after that. Pattern matching, graph problems, alignemnt problems often can be solved using dynamic programming methods.

[NATHANALANPATRICKROGERS]

Originally Posted by sandhya

hi!friends please explain me the full concept of dynamic programming

In reference to bioinformatics, dynamic programming is not typically a discreet computation that arrives at an answer as per the following example:

INPUT X VALUE
IF X=3
RUN 3X-X= ANSWER
DISPLAY ANSWER (6)

On the contrary, dynamic programming is a strategy used in bioinformatics to compute (e.g. using algorithms), score and decide upon an answer(s). [Warning - there are few guarantees that the programmer's syntax is actually correct].

BLAST is a relatively simple algorithm that is worth studying (try to find the authors original papers too!).

From [Only registered users see links. ]



The BLAST algorithm. The BLAST algorithm is a heuristic search method that seeks words of length W (default = 3 in blastp) that score at least T when aligned with the query and scored with a substitution matrix. Words in the database that score T or greater are extended in both directions in an attempt to fina a locally optimal ungapped alignment or HSP (high scoring pair) with a score of at least S or an E value lower than the specified threshold. HSPs that meet these criteria will be reported by BLAST, provided they do not exceed the cutoff value specified for number of descriptions and/or alignments to report.

If you are feeling adventurous, browse [Only registered users see links. ].
I believe the whole-genome DNA sequence compiler used by Craig Venter's team is there...
[I found it once, but I couldn't this time around ]

[hokie]

BLAST is an example of a pattern matching algorithm. BLAST would be a ridiculously slow program if it attacked this problem in a brute force manner.

The goal of BLAST is to find a high scoring match. The manner in which BLAST completes the work may be an example of a dynamic programming algorithm. A dynamic programming algorithm would likely be a good choice here since matching patterns can be constructed from smaller matching problems.

[hokie]

BLAST is an example of a pattern matching algorithm. BLAST would be a ridiculously slow program if it attacked this problem in a brute force manner.

The goal of BLAST is to find a high scoring match. The manner in which BLAST completes the work may be an example of a dynamic programming algorithm. A dynamic programming algorithm would likely be a good choice here since matching patterns can be constructed from smaller matching problems.