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? pic of matrix Are these boxes to show that they are gaps or just to align them properly?

New contributor
Heeh wei cheng is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
  • 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) – Heeh wei cheng Dec 6 at 2:20
  • 2
    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? – llrs Dec 6 at 11:37
  • 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. – Heeh wei cheng Dec 7 at 1:58
up vote 6 down vote accepted

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
    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). – Devon Ryan Dec 6 at 17:30

Your Answer

Heeh wei cheng is a new contributor. Be nice, and check out our Code of Conduct.

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.