Ata de Aula (01/12/2004)

Disciplina de Biologia Computacional

Professor: Dr. João Meidanis

Assunto: Rearranjo de Genomas - distância por reversão

Artigo texto: A Very Elementary Presentation of the Hannenhalli-Pevzner Theory,  by Anne Bergeron.

Autor: Roberto Hiroshi Higa - RA: 876131

Esta ata cobre os seguintes tópicos:

- Seções 1 e 2 do artigo.

Os assuntos foram desenvolvidos por meio de uma dinâmica de perguntas e respostas. Ao longo do processo, os tópicos da aula foram desenvolvidos e as dúvidas sanadas.

Discussão:

Trata de algoritmos para encontrar a distância por reversões entre duas permutações.
OBS: Hannenhalli & Pevzner apresentaram os primeiros algoritmos de complexidade polinomial para solução deste problema, com complexidades O(n4) e O(n5). Neste artigo, é apresentado um algoritmo de complexidade O(n2) operações sobre vetores de bits, o que resulta em uma complexidade final O(n3).
Está sendo seguido a abordagem posicional.
Nesta seção são apresentados 2 algoritmos que, em conjunto, ordenam uma permutação por reversões.
Mas por que a autora referre-se a "Basic Algorithms"? Eles conseguem ordenar qualquer permutação?
O primeiro algoritmo utiliza pares orientados para realizar as reversões. O algoritmo 2 trata de Hurdles (ou obstáculos), criando pares orientados. Juntando os dois algoritmos, eles conseguem ordenar qualquer permutação.
Sim, podem existir mais de uma maneira de ordenar uma permutação. Sobre o artigo, ele foca no problema de encontrar apenas uma maneira de ordenar uma permutação.
A vantagem é que o problema a ser tratado é simplificado.
A desvantagem pode ser ilustrada no seguinte exemplo: suponhamos que temos 3 permutações (genomas) e queremos estabelecer uma relação, evolucionariamente falando, entre as 3 no sentido que desejamos a seqüência de permutações da permutação 1 para a permutação 2, mas passando o mais próximo possível de 3. Neste caso, a disponibilidade de todos os caminhos seria desejável.
É um par de inteiros consecutivos π1 e π2 tais que |π1| - |π2| = +/- 1 e tem sinais opostos, ou seja, um é positivo e o outro negativo. Esta informação é utilizada para calcular os scores utilizados pelo algoritmo 1.
Eles indicam pontos em que, fazendo uma reversão, resulta em uma permutação mais próxima da identidade.
Mas qualquer par orientado pode ser usado? Após intensa discussão e análise de exemplos, não foi se chegou a uma resposta definitiva. Entretanto, em princípio, admitiu-se que não se pode utilizar qualquer par orientado. Se fosse este o caso, não haveria razão para a autora definir o conceito de score para pares orientados.
Aplicada a reversão, o score é o número de pares orientados contidos na permutação resultante.
Enquanto existir pares orientados na permutação, escolha a reversão de máximo score até que todos os elementos da permutação sejam positivos.
E quando houver empate? A autora não faz menção a esse detalhe. Certamente, porque a escolha é indiferente.
O algorimo 1 não trata os hurdles (obstáculos). Existe alguma vantagem nessa estratégia? Não é conhecido. De qualquer maneira, tanto a "parte boa" quanto os obstáculos devem ser tratados em algum momento. Existem diferentes estratégias que tratam os obstáculos e a "parte boa" em momentos diferentes. Entretanto, os obstáculos não podem ser deixados para o final, pois eles geram novas "partes boas".
Se a estratégia do algoritmo 1 aplicar k reversões para uma permutação π, resultando em uma permutação π' , então d(π) = d(&pi') + k.
A cada passo do algoritmo, com certeza, obtém-se uma permutação cuja distância para a identidade é menor comparada com a distância para a identidade da permutação no passo anterior.
Os elementos de uma permutação sem pares orientados são sempre positivos.
Sobre permutações reduzidas, diz-se que uma permutação é reduzida quando ela não contém elementos consecutivos.
Por exemplo, a permutação (0 2 5 4 3 6 1 7) é reduzida? Ou elementos consecutivos tem que aparecer em ordem crescente?
Sim, elementos consecutivos tem que aparecer em ordem crescente. Portanto, o exemplo é uma permutação reduzida.
Tradução: intervalo emoldurado.
Um framed interval em uma permutação π é um intervalo da forma:
i  πj+1  πj+2.......πj+k-1 i+k,
tal que todos os inteiros πj+1  πj+2.......πj+k-1 pertencem ao intervalo [i....i+k].
OBS: para definir um framed interval considera-se a ordem circular, ou seja, o sucessor do último elemento da permutação é o primeiro.
Exemplo: na permutação (0 2 5 4 3 6 1 7), a permutação inteira é um framed interval. Mas o intervalo 2 5 4 3 6 e, por circularidade, o intervalo 6 1 7 0 2 também são framed intervals.
Tradução: obstáculo.
Em uma permutação reduzida, um obstáculo é um framed interval que não contém framed intervals menores.
Fazer a reversão entre o primeiro elemento do hurdle, i, e o que seria o seu consecutivo, i+1, excluindo ambos, mas incluindo os elementos entre eles.
Tradução: fusão de obstáculos.
Esta operação atua sobre os pontos finais de 2 hurdles. Seja o primeiro hurdle i ..... i+k e o segundo i' ..... i'+k', a reversão vai ser aplicada de i+k a i'.
Hurdles tem circularidade? Sim.
Eles podem se sobrepor? Sim, mas só por um elemento. Caso fossem permitidos mais elementos, a condição de minimalidade do hurdle seria violada.
OBS: embora o texto não deixe claro, o hurdle é definido para K ≥ 3.
Um obstáculo simples é um obstáculo cujo corte reduz o número de obstáculos. Caso contrário, ele é um super obstáculo.
Se uma permutação tem 2k obstáculos, k ≥ 2, então
Funda quaisquer dois obstáculos não consecutivos.
Se uma permutação tem 2k+1 obstáculos, k ≥ 1, então
Se ela tem um obstáculo simples, então
Corte-o.
Se ele não tem nenhum, então
Se k ≠ 1
Funda dois obstáculos não consecutivos.
Se k = 1
Funda dois obstáculos consecutivos.

OBS: casos em que a permutação possui apenas 1 ou 2 obstáculos não são tratados pelo algoritmo 2. Nestes casos, a autora indica que apenas uma reversão é suficiente. No primeiro caso, faz-se um corte e no segundo uma fusão.

Referências:

[1] Anne Bergeron, A Very Elementary Presentation of the Hannenhalli-Pevzner Theory,  Proceedings of the 12th Annual Symposium on Combinatorial Pattern Matching, pp. 106-117, July 01-04-2001.