In this week, we're going to complete our discussion of the read alignment problem,
by discussing dynamic programming algorithms for edit distance, and
then some variations on these algorithms,
that solve some very useful general sequence similarity problems.
Dynamic programming algorithms will also allow us to look for
approximate occurrences of a pattern in a text,
including occurrences with insertions and with deletions.
And they'll allow us to calculate flexible string similarities with penalties that
can be configured to suit the biological setting.
They'll also allow to find similar substrings between strings, and
that's a crucial problem solved by many biosequence analysis tools,
including popular tools like Blast.