Alignment length in dynamic programming grid

[Kwok Him S]

In the lecture video (Module 6-Class-Overview 5-07:55), an alignment path was shown through dynamic programming.

Isn’t the possible path (like the one provided below) invalid since the alignment length is greater than the max length of (exemplar/unknown)?

Do the two sequences of feature vector always have to be of the same length?

Attachments:

You must be logged in to view attached files.

[Simon]

The path you show is perfectly valid, although of course it seems a rather unlikely one and will probably result in a large global distance (indicating that the template and unknown are probably not very similar). The number of local distances summed up to make the global distance can indeed vary depending on the path taken through the grid.

The two sequences of feature vectors can be of differing lengths – this will generally be the case, in fact.

[Kwok Him S]

The confusion was: When talking about ‘alignment’, the length of either the exemplar or the unknown candidate should be rigid.

The concept is clear now. Thank you.

[Simon]

The lengths of both the exemplar (template) and unknown can vary. The dynamic programming algorithm works in all cases.

But, during the process of alignment, for a particular pair of exemplar+unknown, the lengths of both are known and are constant.

[Author]

Posts