Describe an algorithm that computes the fitting alignment between two strings S1 and S2. Specifically, we are trying to identify a substring of S1 , such that the alignment between the entirety of S2 and this substring has the largest score over all possible choices of substrings from S1. Please describe your algorithm in terms of how you would modify the local or global alignment algorithms. Specifically, please address the following 4 questions: 1. What values will you initialize in the first row and column of the matrix? 2. Will you use the local or global variant of the recurrence function (i.e., will you allow free rides or not)? 3. Where does backtracking start? 4. Where does backtracking end?

Q&A Education