daf

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Sejam as sequências de proteínas S₁= MVIVSMV e S₂= VSIMVM.
Com o objetivo de compará-las para averiguar as possíveis subcadeias comuns mais longas, construiu-se o algoritmo abaixo utilizando programação dinâmica para preencher as células das tabelas c e b, sendo que os possíveis preenchimentos da tabela b são os símbolos: "↖" (corresponde a s_1i = s_2j), "↑", "←" e "↑ ←" (significa que o caminho para encontrar o pareamento pode seguir para cima ou para esquerda).

Busca_Maiores_SubCadeias_Comuns(S1, S2)

m <- comprimento[S1]

n <- comprimento[S2]

for i<- 1 to m

  do c[i,0] <- 0

for j<- 1 to n

  do c[0,i] <- 0

for i<- 1 to m 

  do for j<- 1 to n

    do if  s1i =  s2j

      then c[i,j] <- c[i-1,j-1] + 1

         b[i,j] <- "↖"

      else if c[i-1,j] > c[i,j-1]

        then c[i,j] <- c[i-1,j]

           b[i,j] <- "↑"

        else if c[i-1,j] < c[i,j-1]

          then c[i,j] <- c[i,j-1]

             b[i,j] <- "←"

          else c[i,j] <- c[i,j-1]

             b[i,j] <- "↑ ←"

return b e c        

Dado que uma maior subsequência comum em ambas é reconstruída iniciando do canto inferior direito percorrendo a tabela seguindo as setas, assinale a alternativa correta.

a) Existe uma única subsequência comum mais longa entre S1 e S2
b) Existem duas subsequências comuns mais longas entre S1 e S2
c) Existem três subsequências comuns mais longas entre S1 e S2
d) Existem quatro subsequências comuns mais longas entre S1 e S2
e)N.D.A

Ideia original de: Danielle Furtado dos Santos Dias