Question: SEQUENCE ALLIGNMENT y T A A G G T C A - x 0 1 2 3 4 5 6 7 8 A 0 7
SEQUENCE ALLIGNMENT
| y | T | A | A | G | G | T | C | A | - | |
| x | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| A | 0 | 7 | 8 | 10 | 12 | 13 | 15 | 16 | 18 | 20 |
| A | 1 | 6 | 6 | 8 | 10 | 11 | 13 | 14 | 16 | 18 |
| C | 2 | 6 | 5 | 6 | 8 | 9 | 11 | 12 | 14 | 16 |
| A | 3 | 7 | 5 | 4 | 6 | 7 | 9 | 11 | 12 | 14 |
| G | 4 | 9 | 7 | 5 | 4 | 5 | 7 | 9 | 10 | 12 |
| T | 5 | 8 | 8 | 6 | 4 | 4 | 5 | 7 | 8 | 10 |
| T | 6 | 9 | 8 | 7 | 5 | 3 | 3 | 5 | 6 | 8 |
| A | 7 | 11 | 9 | 7 | 6 | 4 | 2 | 3 | 4 | 6 |
| C | 8 | 13 | 11 | 9 | 7 | 5 | 3 | 1 | 3 | 4 |
| C | 9 | 14 | 12 | 10 | 8 | 6 | 4 | 2 | 1 | 2 |
| - | 10 | 16 | 14 | 12 | 10 | 8 | 6 | 4 | 2 | 0 |
Find strings x and y such that in the completed "opt" table (where opt[i][j] = optimum cost of aligning x0 x1 x2 ... x_{m-1} with y0 y1 y2 ... y_{n-1}), there exist (provide them) values i and j such that the following holds:
x_i == y_j and opt[ i ][ j ] = 2 + opt[ i+1][ j ] = 2 + opt[ i ][ j+1] = 0 + opt[ i + 1][ j + 1].
or
prove that this cannot happen for ANY strings x and y.
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
