MO640 - Prova I2

Enunciado distribuido na sala.

Gabarito:

1. 		T	A	G	G	C
   	0	-1	-2	-3	-4	-5
   A	-1	0	0	-1	-2	-3
   G	-2	-1	0	1	0	-1
   C	-3	-2	-1	0	1	1
   C	-4	-3	-2	-1	0	2
   T	-5	-3	-3	-2	-1	1

   Pontuação ótima (última célula): 1; alinhamentos ótimos (só um):

   -AGCCT
TAGGC-

   Para os prefixos AGCC e TAGG, a pontuação ótima (casa [4,4] da matriz) é 0; alinhamentos ótimos (três):

   AGCCT -AGCC -AGCC
TAGGC TAGG- TAG-G

2. As características que impõem splits não triviais são apenas c₁ e c₃. A primeira impõe AC-BDE; a segunda, CD-ABE. Não há como compatibilizar esses splits. Logo, não há filogenia perfeita, e as filogenias com 5 trocas serão ótimas, se houver.

   Para conseguir topologias com 5 trocas, precisamos favorecer c₁ ou c₃, porque, se não tivermos subárvore AC nem subárvore CD, acabaremos com 6 trocas. Há três topologias que deixam AC numa subárvore:

   

   Todas elas permitem associar 5 trocas de características às arestas de modo a explicar a matriz de entrada. A segunda topologia permite duas associações, que diferem no posicionamento de c₃:

   

   Algo semelhante ocorre com topologias que mantêm CD juntos. Há três delas:

   

   Novamente, todas permitem associar 5 trocas de características às arestas de modo a explicar a matriz de entrada. E novamente a topologia que deixa BE juntos permite duas associações que diferem no posicionamento de c₁:

   

3. Será que existe uma solução com 2 haplótipos? Não, pois cada genótipo precisa de 2 haplótipos para ser resolvido; se houvesse apenas 2 no total, os 3 genótipos seriam iguais.

   Será que existe uma solução com 3 haplótipos? Bem, nesse caso, teríamos 3 haplótipos que, combinados 2 a 2, deveriam resolver os três genótipos. Algum haplótipo deveria resolver simultaneamente 02022 e 21220. Teria que ser 01000 ou 01010. Seus pares na resolução de 02022 seriam 00011 e 00001, respectivamente. Mas nenhum deles pode ser usado para resolver o terceiro genótipo. Logo, não há solução com 3 haplótipos.

   Para resolver 02022, temos 4 possibilidades: (00000,01011); (00001,01010); (00010,01001); (00011,01000).

   Para resolver 21220, também temos 4 possibilidades: (01000,11110); (01010,11100); (01100,11010); (01110,11000).

   Para resolver 21202, temos, igualmente, 4 possibilidades: (01000,11101); (01001,11100); (01100,11001); (01101,11000).

   Vendo agora que haplótipos aparecem 2 ou mais vezes, temos:

   01010: 2 vezes
   01001: 2 vezes
   01000: 3 vezes
   11100: 2 vezes
   01100: 2 vezes
   11000: 2 vezes
   

   Usando 01010 duas vezes, temos uma solução com 4 haplótipos:

   (00001,01010), (01010,11100), (01001,11100)

   Usando 01001 duas vezes, temos uma outra solução com 4 haplótipos:

   (00010,01001), (01010,11100), (01001,11100)

   Usando 01000 três vezes, temos uma terceira solução com 4 haplótipos:

   (00011,01000), (01000,11110), (01000,11101)

   Usando 01000 apenas duas vezes, não há solução, pois seus pares não aparecem duas vezes. Usando 11100 duas vezes, reproduzimos as duas primeiras soluções acima. E, usando os outros que se repetem duas vezes, não temos soluções.

   Sendo assim, temos apenas 3 soluções diferentes com 4 haplótipos.

4. A matriz não é aditiva, como nos mostra o método tradicional. Mas, mudando para 4 a distância entre C e D, conseguimos a seguinte árvore para a nova matriz:

   

Critérios de avaliação:

1. As matrizes são o mais importante, pois dão justificativa para o resto. Assim, cada linha errada de matriz reduz 0,5. Se a matriz estiver toda certa, cada alinhamento errado reduz 0,5.

2. Esta questão foi difícil; por isso, o critério de correção foi ameno. O certo seria dizer que são necessárias 5 trocas, e há um total de 6 topologias e 8 soluções para o problema. Porém, o critério adotado foi:

   3 soluções com 5 trocas: 2,5
   2 soluções com 5 trocas: 2,0
   1 solução com 5 trocas: 1,5
   soluções com 6 trocas: 1,0
   erros na associação de caraterísticas a arestas: -0,5

3. A resposta era que são necessários 4 haplótipos no mínimo, e havia 3 soluções. Critério:

   3 soluções: 2,5
   2 soluções: 2,0
   1 solução : 1,5
   apenas achou resoluções e contou repetidos: 1,0
   achou resoluções, mas não contou repetidos: 0,5
   achou resoluções, mas errou algumas delas: 0,5

4. Com relação à matriz:

   não aditiva, com justificativa: 1,5
   não aditiva, sem justificativa: 1,0
   

   Com relação às mudanças para torná-la aditiva:

   1 mudança: 1,0
   2 mudanças: 0,5
   3 ou mais mudanças: 0,0

MO640 Home

© 2011 João Meidanis