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 |