Exercises

1. Describe a dynamic programming algorithm that solves the longest common subsequence problem—find the largest number of letters that occur in the same order in two strings. For example, the longest common subsequence of ABCDGH and AEDFHR is ADH:

   ABCDGH
   A  D H
   AE DFHR

2. Describe a dynamic programming algorithm that solves a "global-local" (or "fitting") alignment: find the best alignment of a short string (query) inside a longer string (text), or more precisely the highest scoring alignment between a query string and a substring of a text string. Yet another way of saying it, the alignment must use the full query but can ignore characters at the beginning and end of the text. Describe how you would modify either the global or local alignment algorithm to solve this problem: How would you initialize the first row/column of the matrix? What recurrence equations would you use (local or global)? From which location in the matrix would you start the backtracking process?

3. Describe a dynamic programming algorithm that solves an "overlap" alignment: the highest scoring alignment of the suffix of S1 to the prefix of S2. Describe how you would modify either the global or local alignment algorithm to solve this problem: How would you initialize the first row/column of the matrix? What recurrence equations would you use (local or global)? From which location in the matrix would you start the backtracking process?

4. Describe a dynamic programming algorithm that solves a "suffix" alignment: the highest scoring alignment of the suffix of S1 to the suffix of S2.

   Describe how you would modify either the global or local alignment algorithm to solve this problem: How would you initialize the first row/column of the matrix? What recurrence equations would you use (local or global)? From which location in the matrix would you start the backtracking process?

5. Describe a dynamic programming algorithm that solves a partial "prefix" alignment: the highest scoring alignment of a prefix of S1 to the entirety of S2. Describe how you would modify either the global or local alignment algorithm to solve this problem: How would you initialize the first row/column of the matrix? What recurrence equations would you use (local or global)? From which location in the matrix would you start the backtracking process?

6. Describe a dynamic programming algorithm that solves a partial "suffix" alignment: the highest scoring alignment of a suffix of S1 to the entirety of S2. Describe how you would modify either the global or local alignment algorithm to solve this problem: How would you initialize the first row/column of the matrix? What recurrence equations would you use (local or global)? From which location in the matrix would you start the backtracking process?

7. We described how the Aho-Corasick algorithm can be used to compute an exact alignment with "don't care" symbols. Describe an algorithm that can perform inexact alignments using "don't care" symbols. (Note: a "don't" care symbol * is a character that can be matched to any other character without a penalty). Will your algorithm allow a * to be aligned to a gap?

8. Assume we want to compute high-quality ungapped local alignments of two strings. Do you still need a dynamic programming table? Describe an algorithm that finds the maximum scoring ungapped local alignment.