086-2008

MO640 - Questão para a prova oral
Número: 086
Enunciado:
Encontramos fórmulas diferentes na literatura para a distância de seqüências por reversão:

1. d(α) = n + 1 - c(α) + h(α) + f
2. d(α) = b(α) - c(α) + h(α) + f

onde n é o comprimento da seqüencia, b(α) é o número de breakpoints, h(α) é o número de obstáculos (hurdles) e f é um fator de correção para fortalezas (fortresses).

Por que há esta diferença?

1. Na 1ª fórmula c(α) é o total de ciclos menos os ciclos de tamanho 2. Na segunda c(α) é simplesmente o total de ciclos.
2. Na 2ª fórmula c(α) é o total de ciclos menos os ciclos de tamanho 2. Na primeira c(α) é simplesmente o total de ciclos.
3. Na 2ª fórmula c(α) é o total de ciclos bons. Na primeira c(α) é o total de ciclos ruins.
4. Na 1ª fórmula c(α) é o total de ciclos bons. Na segunda c(α) é o total de ciclos ruins.
5. NDA

Autor(a): Pedro Henrique Del Bianco Hokama