I would like to ask why when we initialize 0 as the starting point, there are 3 gray boxes that are not used as shown (highlighted in the red box) in the pic?
Are these boxes to show that they are gaps or just to align them properly?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ I would also like to ask how dynamic programming plays a part in filling up the rows and columns in the matrix. (I'm new to bioinformatics) $\endgroup$– Heeh wei chengCommented Dec 6, 2018 at 2:20
-
2$\begingroup$ Welcome to the site Heeh. You can edit your question to add things to the question like more information. Could you clarify what do you mean by "how dynamic programming plays a part"? Do you want to know what is dynamic programming? Or perhaps why it is needed for this algorithm? $\endgroup$– llrsCommented Dec 6, 2018 at 11:37
-
$\begingroup$ Hi I would like to know both about dynamic programming and why it is needed for this algorithm. I searched the meaning of dynamic programming but I do not understand the meaning behind recursive. $\endgroup$– Heeh wei chengCommented Dec 7, 2018 at 1:58
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
The first column is added in order to be able to align the sequences. They might be gaps if the alignment ends up beginning in different positions than the first. Without the first empty row and column it wouldn't be possible to have gaps at the beginning of the alignment
The dynamic programming is useful because you need first to calculate the score for each position, and then once you have the score, you can calculate the optimum path. So you solve your problem by first calculating what would happen if (there was a gap, there was a mismatch...) and then you find the optimum alignment.
-
2$\begingroup$ Dynamic programming isn't strictly needed, it's just convenient to use recursion to handle the rows (depending on the implementation, you can also save memory by not storing the full matrix then). $\endgroup$ Commented Dec 6, 2018 at 17:30