# 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.<br>

   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.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mpop.gitbook.io/bioinformatics-lecture-notes/inexact-alignment/exercises.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.