Dynamic Programming:

Dynamic Programming:
It is method for solving complex problems by breaking then down in to simpler problems

Dynamic programming is of two types
1. Top-down D.P: simply means storing the results of certain calculations, which are later used again since the completed calculation is a sub problem of a larger calculation.
2. Bottom-up D.P: it involves formulating a complex calculation as a recursive series of simpler calculations.

History:
The term D.P was originally used in the 1940’s by Richard bellman to describe the process of solving problem where one needs to find the best decisions on after another.
The word dynamic was bellman because it sounded impressive, not because it described how the method worked
The word programming referred to the use of the method to find an optimal program.

Overview:

Finding the shortest path in a graph using optimal structure

• A straight line indicates a single edge
• A wavy line indicates the shortest path
• A bold line is the overall shortest path from start to goal.

Dynamic Programming is both

• Mathematical optimization method
• Computer programming method

In both contexts it refers to simplifying a complicated problem by breaking it down into simpler sub problem in a recursive manner.

Principle of optimality:
Some decision problems cannot be taken apart in a recursive manner, decisions that span several points in time do often break apart recursively, Bellman called this the principle of optimality.

Mathematical optimization method:
If sub problems can be nested recursively inside larger problems, so that dynamic programming methods are applicable then there is a relation b/wn the values of larger problem and the values of the sub problems.

In the optimization literature this relationship is called the bellman equation

This is done by a defined a sequence of value functions v1,v2,…Vn with an argument y representating the state of the system at times i from 1 to n .
Vn(Y) is the values obtain in state y at the last time n.

Computer programming method:

They are two key attributes that a problem must have a order for D.P to be applicable
They are optimal substructure and overlapping sub problems.

Optimal structure: It means that the solution to a given optimization problem can be occupied by the combination of optimal solution to its sub problems.

Sub problems graph for the Fibonacci sequence that fact that is not a tree indicates overlapping sub problems.

Computer programming can be achieved in either of two ways
• Top-down approach
• Bottom-up approach

Sequence Alignment:
It is the way of arranging the sequence of DNA, RNA or Proteins to identify the regions of similarity that may be a consequence of functional, structural or evolutionary relationships b/wn the sequences

Aligned sequences of nucleotides or amino acid residues are typically represented as rows within a matrix

Gaps are inserted b/wn the residues so that identical or similar characters are aligned in successive columns

Sequence alignment based on position:
Local alignment: It is confined to a particular region of a limited region of a sequence
* A general local alignment technique is the Smith and Watermann

Global Alignment:
*It is used to identify a sequence of a total given genome
* A general global alignment technique is the Needleman and Wunsch.
* In D.P, global and local alignment are used
*In typical usage, protein alignment use a substitution matrix to assign scores to amino acid
• Matches or Mis-matches
• And a gap penalty

For gap penalty score:-4
Mis-match score:-3
Match: 5

Needleman and Wunsch for matrix filling, the formula is
[S (i-1) (j-1) + (Saibj), Si (j-1) +w, S (i-1) j+w]
Gap penalty=w,
Saibj=Match or mis-match.

Dynamic Programming is more than two sequences; it is prohibitively slow for large numbers or extremely long sequences.