MO417 - QUESTÃO PARA A PROVA ORAL

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-045

Enunciado: Suponha que um algoritmo de Huffman tenha sido projetado para codificar sequências de DNA em arquivos binários. A figura abaixo contém a árvore binária que representa a montagem de códigos livres de prefixos para os nucleotídeos A, T, G e C. Nesta árvore, cada nó interno é rotulado com a soma das frequências das folhas de suas sub-árvores.

Selecione a alternativa cujo conteúdo preenche corretamente as folhas w, x, y e z, nesta ordem, com o nucleotídeo e sua respectiva frequência, bem como contém o código correspondente à sequência AATGGC:

1. w = C : 40; x = T : 35, y = G : 10; z = A : 15; 1011011001000
2. w = G : 40; x = C : 35, y = A : 15; z = T : 10; 100100101001
3. w = A : 40; x = G : 35, y = T : 10; z = C : 15; 0010011110101
4. w = C : 40; x = A : 35, y = G : 15; z = T : 10; 11111011001000
5. N.D.A.

Ideia original de: Daniel Henriques Moreira