MO640/ MC668 - Ata de exercícios

Aula: 2007-05-14
Autor: Wagner Rogério de Andrade RA: 036546

1. Considere um ciclo genérico α que contém dois elementos a e b. Sabemos que a e b estarão em ciclos distintos no produto (a b) α, e também no produto α (a b). Diga quais dos pares de elementos abaixo estão no mesmo ciclo nos produtos indicados:

   1. a e α(a) em (a b)α.
   2. a e α(a) em α(a b).
   3. b e α(b) em (a b)α.
   4. b e α(b) em α(a b).
   5. a e α^-1(a) em (a b)α.
   6. a e α^-1(a) em α(a b).
   7. b e α^-1(b) em (a b)α.
   8. b e α^-1(b) em α(a b).

   Suponha que α(a) ≠ b e α(b) ≠ a.

Respostas:
Seja:
α = (...α⁻¹(a) a α(a)...α⁻¹(b) b α(b)...)
Teremos:
α(a b) = (...α⁻¹(a) a α(a)...α⁻¹(b) b α(b)...)(a b) = (a α(b)...α⁻¹(a))(b α(a)...α⁻¹(b))
(a b)α = (a b)(...α⁻¹(a) a α(a)...α⁻¹(b) b α(b)...) = (a α(a)...α⁻¹(b))(b α(b)...α⁻¹(a))
E portanto podemos concluir que:
1. a e α(a) estão no mesmo ciclo em (a b)α.
2. a e α(a) não estão no mesmo ciclo em α(a b).
3. b e α(b) estão no mesmo ciclo em (a b)α.
4. b e α(b) não estão no mesmo ciclo em α(a b).
5. a e α^-1(a) não estão no mesmo ciclo em (a b)α.
6. a e α^-1(a) estão no mesmo ciclo em α(a b).
7. b e α^-1(b) não estão no mesmo ciclo em (a b)α.
8. b e α^-1(b) estão no mesmo ciclo em α(a b).

2. Considere um genoma linear onde os genes aparecem numa das fitas na seguinte ordem: +1, -2, -3 +4, e um outro genoma também linear em que os genes aparecem numa das fitas na seguinte ordem: -3, -4, -2 +1. Qual é o número mínimo de reversões que explica as diferenças entre estes dois genomas?

   Resposta:
   Sabendo que a distância de reversão entre dois genomas lineares com extremos livres é calculada com a fórmula abaixo:
   
   d_free = min(d_fixed(α,β),d_fixed(γ . α^-1,β))
   Onde:
   
   α = um dos genomas
   β = o outro genoma
   d_fixed(α,β): distância de reversão entre α e β calculada como se ambas possuissem extremos fixos.
   d_fixed(γ . α^-1,β): distância de reversão entre a fita complementar de α e β calculada como se ambas possuissem extremos fixos.
   
   Para usar o algoritmo publicado por Anne Bergeron em "A very elementary presentation of the Hannenhalli and Pevzner Theory - 2002", capaz de encontrar a distância por reversões entre dois genomas α e β, precisamos renomear os genes de β para que ela (a permutação destino) seja igual a permutação identidade, assim β teria +1, +2, +3, +4, nesta ordem, portanto, com os genes renomeados teremos α com +4, +3, +1, -2, nesta ordem.
   Aplicando o algoritmo citado foram encontrados os seguintes resultados:
   
   Ordenando α:
   (0 +4 +3 +1 -2 5)
   (0 +4 -1 -3 -2 5)
   (0 +1 -4 -3 -2 5)
   (0 +1 +2 +3 +4 5)
   

   E portanto d_fixed(α,β) = 3

   Ordenando γ . α^-1: (0 +2 -1 -3 -4 5)
   (0 +2 -1 -3 +4 5)
   (0 +2 -1 +3 +4 5)
   (0 +1 -2 +3 +4 5)
   (0 +1 +2 +3 +4 5)
   

   E portanto d_fixed(γ . α^-1,β) = 4

   Logo: d_free = min(d_fixed(α,β),d_fixed(γ . α^-1,β)) = min(3,4) = 3.
   E podemos portanto afirmar que o número mínimo de reversões que explica as diferenças entre os genomas α e β é 3.