ATA - 26 AUG 2008

1) No texto é dado um algoritmo recursivo para comparação global de duas seqüências que usa espaço linear. Escreva um algoritmo não recursivo para o mesmo problema, usando também espaço linear.

Resposta:
Foram apresentados dois algortimos em aula que resolvem o problema em tempo cúbico.
Um deles foi descrito da seguinte forma:

for ( i <- 1, n )
  BestScore(s[1..n], t[posmax..m], pref_sim)
  BestScoreRev(s[i+1..n], t[posmax..m], suff_sim)
  if ( posmax <= m )
    tipomax <- space
    vmax <- pref_sim[0] + g + suff_sim[0]
    for ( j <- posmax, m )
      if ( pref_sim[j-1] + p(i, j) + suff_sim[j] > vmax )
        posmax <- j
        typemax <- symbol
        vmax <- pref_sim[j-1] + p(i, j) + suff_sim[j]
      if ( pref_sim[j] + g + suff_sim[j] > vmax )
        posmax <- j
        typemax <- space
        vmax <- pref_sim[j] + g + suff_sim[j]
    if ( typemax == symbol )
      align_1[i] = s[i]
      align_2[i] = t[posmax]
    else
      align_1[i] = s[i]
      align_2[i] = espace
    posmax <- posmax + 1

A idéia do segundo algoritmo proposto é guardar sempre duas linhas da matriz de modo que se possa encontrar o alinhamento.
O código pode ser encontrado aqui. Para executar o programa:
Compilar: gcc lcompare.c -o lcompare
Executar: ./lcompare <sequência 1> <sequência 2>
Os valores usados na comparação são: m=+1, mm=+0, g=-2.

Concluímos então que, caso você não queria gastar mais tempo que O(n²) a solução seria usar uma pilha explícita para fazer a recursão.

2) O texto apresenta um algoritmo para comparar duas seqüências de tamanho n que roda em tempo O(dn), onde d é tanto menor quanto mais semelhantes são as seqüências. O algoritmo usa várias iterações de uma rotina, chamada de KBand no texto, que determina a melhor pontuação de um alinhamento entre as seqüências dadas que não utilize mais que k pares de espaços. O parâmetro k começa em 0 e vai dobrando a cada iteração. Verdadeiro ou falso: se KBand retorna a mesma pontuação em duas iterações consecutivas, podemos dizer que esta pontuação é a similaridade entre as seqüências dadas?

Resposta:
Erro: no enunciado consta que o valor inicial de k é 0 (zero) quando este valor é, na verdade, 1 (um).
Não se chegou a nenhuma conclusão quanto a essa questão sendo que a idéia é tentar achar um contra exemplo e, caso não se encontre um, provar a corretude da proposição.
Também ficou estabelecido que quem conseguir resolver esta questão ganharia um "BONUS".
Update: O colega João Paulo Pereira Zanetti chegou a uma solução para a questão.

Usando as sequências:
s1 = AGTCGTGACACCTGGGGACTGACTGACTGGGGGACTGACTGACTG
s2 = GTCCGTGATGCCAACTGACTGACTGAAACACTGACTGAAACGTCA
Pode-se chegar a um contra exemplo usando estas duas sequências. O programa usado pode ser encontrado aqui.
Podemos então concluir que a condição de parada é realmente aquela descrita no texto e não a proposta no enunciado.

Arquivo em anexo:
lcompare.c
compSim.rb

File translated from T_EX by T_TH, version 3.67.
On 28 Sep 2008, 13:06.