Construa uma matrix de programação dinâmica \(c\) usada para computar o tamanho de uma subsequência comum mais longa entre as sequências a seguir, e explique o significado do valor em \(c[i,j]\).
CTACAG
GTCAC
Solução:
Usando o método visto em aula, temos:
\(c[i][j] =\) tamanho da subsequência comum mais longa entre
os sufixos \(X[7-j..6]\) e \(Y[6-i..5]\) das sequências de
entrada \(X =\) CTACAG e \(Y =
\) GTCAC.
| G | A | C | A | T | C | ||
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
| C | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| A | 0 | 0 | 1 | 1 | 2 | 2 | 2 |
| C | 0 | 0 | 1 | 2 | 2 | 2 | 3 |
| T | 0 | 0 | 1 | 2 | 2 | 3 | 3 |
| G | 0 | 1 | 1 | 2 | 2 | 3 | 3 |
Usando o método do livro de Cormen et al, Introduction to Algorithms, segunda edição, temos:
\(c[i][j] =\) tamanho da subsequência comum mais longa entre
os prefixos \(X[1..i]\) e \(Y[1..j]\) das sequências de
entrada \(X =\) CTACAG e \(Y =
\) GTCAC.
| G | T | C | A | C | ||
| 0 | 0 | 0 | 0 | 0 | 0 | |
| C | 0 | 0 | 0 | 1 | 1 | 1 |
| T | 0 | 0 | 1 | 1 | 1 | 1 |
| A | 0 | 0 | 1 | 1 | 2 | 2 |
| C | 0 | 0 | 1 | 2 | 2 | 3 |
| A | 0 | 0 | 1 | 2 | 3 | 3 |
| G | 0 | 1 | 1 | 2 | 3 | 3 |