MO640 - Questão para a prova oral

Número: 021

Enunciado:

Sobre o algoritmo baseado em programação dinâmica para alinhamento entre duas seqüências, pode-se afirmar que:

I – A estratégia do algoritmo é obter uma solução ótima a partir de soluções ótimas de instâncias menores do problema
(alinhamento de substrings) obtidas previamente.
II - a variante para alinhamento global encontra o alinhamento de melhor score entre o prefixo s[1..i] e o
prefixo t[1..j], 1 <= i <= m, 1 <= j <= n.
III – a variante para alinhamento local encontra o alinhamento de melhor score entre um sufixo do prefixo s[1..i] e
um sufixo do prefixo t[1..j], 1 <= i <=m, 1 <= j <= n.
IV – as mesmas variantes do algoritmo também podem ser utilizadas para alinhar duas seqüências de proteínas.
Neste caso, pode-se utilizar uma matriz 20x20 para armazenar o grau de similaridade entre cada par de aminoácidos.

Escolha a alternativa correta:

1. apenas I, II e III estão corretas.
2. Todas estão corretas.
3. Apenas II e III estão corretas.
4. Apenas I está correta.
5. NDA

Autor(a): Roberto Hiroshi Higa.