Abstract
Dynamic programming is one method of solving a very well known and can be applied in all fields. Dynamic programming can be applied within the scope of sequence alignment. Sequence alignment is the basis of meode sequence analysis, which is used to study the evolution of sequences from the same ancestors (common ancestor). Therefore in this paper will be presented on dynamic programming.
Keywords: dynamic programming, sequence alignment, global alignment, Nedleman-Wunsch
1. Introduction
The term dynamic programming (dynamic programming) of course we've heard in the literature, this term we find a lot of books on computer algorithms, operational research, or books related to applied mathematics. Some people are also familiar with dynamic programming as a method associated with the principle of optimization and can be applied in industry, banking, until the network planning and space travel applications. Application makes extensive discussion of dynamic programming becomes a common topic and interest. To try to find out more about the dynamic programming, in this article will discuss about the basics of dynamic programming theory briefly, also with a brief history of the origin of the term dynamic programming.
Bioinformatics, as one of a growing multidisciplinary field and many computational methods, would be a fairly open field for such a method of dynamic programming methods, further in this paper applies dynamic programming applications as optimization methods in solving problems, and exemplified the problem of numbers Fibonacci and multistage graph, in the end, as the emphasis in this paper, the dynamic programming application in the field of bioinformatics, particularly in the Needleman-Wunsch algorithm for global sequence alignment.
2. Dynamic Programming
Dynamic Programming term, first introduced in the 1950s by Richard Bellman was a professor at Princeton University and also worked at the RAND corporation, please note that the RAND corporation in that era is a company formed to offer research and analysis for the United States armed forces . At that time, Bellman worked in the field of multi-stage decision-making (Desicion multistage process) and doing some mathematical methods, several years later after Bellman at RAND, was born the term dynamic programming. This term is not directly related to programming, but is used as the title of the project which proposed the RAND Corporation in the United States Air Force. Furthermore, the dynamic programming penerapanya widely used in process optimization problems.
Dynamic programming is an algorithm solving the problem described by a set of solution steps or stages such that the solution of the problem can be viewed from a series of interrelated decisions. On completion of this method we use optimization requirements and constraints to limit the number of options that should be considered at some stage. Dynamic Program algorithm has the following characteristics:
1. Form the problem can be divided into several stages, which at each stage is taken only one optimal decision.
2. Each stage consists of a number of status associated with these stages.
3. The results of the decisions taken at the stage transformed from a status corresponding to the next status at a later stage.
4. Costs at a stage depends on the cost of the previous stages and increases regularly with increasing number of stages
5. The best decision at an independent stage of the decision made earlier stage.
6. The existence of a recursive relationship that identifies the best decision for each state at stage k gives the best decision for the previous stage.
7. Optimality principle applies to the issue.
The main characteristics of the Dynamic Program is the principle of optimality, which reads "if the optimal total solution, then the solution to the phase-k is optimal".
From the characteristics of the 4 points above, we can conclude that the algorithm can be applied to the Dynamic program improvement costs if the linear and discrete so that the partial optimization can be done. In solving problems with dynamic program, we can use 2 different approaches, namely:
a. Forward (forward or up-down): to move from stage 1, move forward to stage 2.3, .., n. The order of the decision variables are x1, x2, ..., xn
b. Backward (backward or bottom-up): to move from stage n, and hold back to stage n-1, n-2, .., 2.1. The order is the decision variable xn xn-1, x2, x1. The time complexity of this algorithm is O (| s1 | * | s2 |), if the length of the string is 'n'. Space complexity is also the same if the entire matrix is stored for reverse-engineer to find the optimal alignment. If the value of the edit distance is required, only two rows of the matrix is allocated, the matrix can experience 'recycling', and so the space complexity O (n).
The Dynamic programming is a strategy to build a multilevel optimal problem, ie problems that can be described as a series of stages daalam (stage) affect each other. Generally, each stage has 4 (four) variables that have an influence, either directly or indirectly to the other phases of the system
The four variables are as follows:
1. Input to stage n, Xn, which depends on the decisions made at earlier stages or depending on the origin of the fixed inputs in the system
2. Set the decision to stage n, Dn which determine the operating conditions or requirements of the stage.
3. The output from stage n, Xn-1 are used depending on the input to the decision stage n and Dn.
4. Results from stage n, Rn which is the measure of contribution to stage n the overall system objective function (cost, profit, benefit or other measures). Usually this result is a picture of a stage n and the output at stage n.
Graphically, the image of a stage can be shown as follows:
gbr11
In the dynamic programming are three basic elements namely, the alternative decision variable, the corresponding profit function, and the state (state) in each phase. Variable that provides the optimal solution obtained by tracing the state of stage n to stage 1.
Dynamic programming is one method of solving a very well known and can be applied in all fields. Dynamic programming can be applied within the scope of sequence alignment. Sequence alignment is the basis of meode sequence analysis, which is used to study the evolution of sequences from the same ancestors (common ancestor). Therefore in this paper will be presented on dynamic programming.
Keywords: dynamic programming, sequence alignment, global alignment, Nedleman-Wunsch
1. Introduction
The term dynamic programming (dynamic programming) of course we've heard in the literature, this term we find a lot of books on computer algorithms, operational research, or books related to applied mathematics. Some people are also familiar with dynamic programming as a method associated with the principle of optimization and can be applied in industry, banking, until the network planning and space travel applications. Application makes extensive discussion of dynamic programming becomes a common topic and interest. To try to find out more about the dynamic programming, in this article will discuss about the basics of dynamic programming theory briefly, also with a brief history of the origin of the term dynamic programming.
Bioinformatics, as one of a growing multidisciplinary field and many computational methods, would be a fairly open field for such a method of dynamic programming methods, further in this paper applies dynamic programming applications as optimization methods in solving problems, and exemplified the problem of numbers Fibonacci and multistage graph, in the end, as the emphasis in this paper, the dynamic programming application in the field of bioinformatics, particularly in the Needleman-Wunsch algorithm for global sequence alignment.
2. Dynamic Programming
Dynamic Programming term, first introduced in the 1950s by Richard Bellman was a professor at Princeton University and also worked at the RAND corporation, please note that the RAND corporation in that era is a company formed to offer research and analysis for the United States armed forces . At that time, Bellman worked in the field of multi-stage decision-making (Desicion multistage process) and doing some mathematical methods, several years later after Bellman at RAND, was born the term dynamic programming. This term is not directly related to programming, but is used as the title of the project which proposed the RAND Corporation in the United States Air Force. Furthermore, the dynamic programming penerapanya widely used in process optimization problems.
Dynamic programming is an algorithm solving the problem described by a set of solution steps or stages such that the solution of the problem can be viewed from a series of interrelated decisions. On completion of this method we use optimization requirements and constraints to limit the number of options that should be considered at some stage. Dynamic Program algorithm has the following characteristics:
1. Form the problem can be divided into several stages, which at each stage is taken only one optimal decision.
2. Each stage consists of a number of status associated with these stages.
3. The results of the decisions taken at the stage transformed from a status corresponding to the next status at a later stage.
4. Costs at a stage depends on the cost of the previous stages and increases regularly with increasing number of stages
5. The best decision at an independent stage of the decision made earlier stage.
6. The existence of a recursive relationship that identifies the best decision for each state at stage k gives the best decision for the previous stage.
7. Optimality principle applies to the issue.
The main characteristics of the Dynamic Program is the principle of optimality, which reads "if the optimal total solution, then the solution to the phase-k is optimal".
From the characteristics of the 4 points above, we can conclude that the algorithm can be applied to the Dynamic program improvement costs if the linear and discrete so that the partial optimization can be done. In solving problems with dynamic program, we can use 2 different approaches, namely:
a. Forward (forward or up-down): to move from stage 1, move forward to stage 2.3, .., n. The order of the decision variables are x1, x2, ..., xn
b. Backward (backward or bottom-up): to move from stage n, and hold back to stage n-1, n-2, .., 2.1. The order is the decision variable xn xn-1, x2, x1. The time complexity of this algorithm is O (| s1 | * | s2 |), if the length of the string is 'n'. Space complexity is also the same if the entire matrix is stored for reverse-engineer to find the optimal alignment. If the value of the edit distance is required, only two rows of the matrix is allocated, the matrix can experience 'recycling', and so the space complexity O (n).
The Dynamic programming is a strategy to build a multilevel optimal problem, ie problems that can be described as a series of stages daalam (stage) affect each other. Generally, each stage has 4 (four) variables that have an influence, either directly or indirectly to the other phases of the system
The four variables are as follows:
1. Input to stage n, Xn, which depends on the decisions made at earlier stages or depending on the origin of the fixed inputs in the system
2. Set the decision to stage n, Dn which determine the operating conditions or requirements of the stage.
3. The output from stage n, Xn-1 are used depending on the input to the decision stage n and Dn.
4. Results from stage n, Rn which is the measure of contribution to stage n the overall system objective function (cost, profit, benefit or other measures). Usually this result is a picture of a stage n and the output at stage n.
Graphically, the image of a stage can be shown as follows:
gbr11
In the dynamic programming are three basic elements namely, the alternative decision variable, the corresponding profit function, and the state (state) in each phase. Variable that provides the optimal solution obtained by tracing the state of stage n to stage 1.
1 Komentar untuk "Dynamic programming"
a good idea. but you have to study more..