Número: 039
Enunciado:
A complexidade de tempo do algoritmo visto em aula para comparação de seqüências similares é dada por O(dn) onde n é o número de elementos das suas seqüências s e t, supostamente iguais no tamanho. Indique a alternativa que melhor descreve o significado do parâmetro d:
- a largura da banda onde se está preenchendo a matriz .
- a quantidade de gaps do alinhamento ótimo das seqüências s e t.
- a quantidade de mismatches do alinhamento ótimo das seqüências s e t.
- a diferença entre a similaridade entre duas seqüências iguais (de tamanho n) e a similaridade das seqüências s e t.
- NDA
A alternativa verdadeira é a d.
ResponderExcluirDuas sequências iguais, de tamanho n, possuem o maior score possível (Ms). Para duas sequências similares, também de tamanho n, há um score ótimo (Os). Para o algoritmo KBand, d é justamente a diferença entre esses dois scores:
d = Ms - Os
Isso significa que se a similaridade entre as duas sequências é grande, Os é grande. Como Ms é um valor fixo, d fica pequeno. Ou seja, quando maior a similaridade, menor é o tempo de execução.
Bom comentário!
ResponderExcluir