MO417 - Questão para a prova oral

Número: 041

Enunciado:
Por serem sequências normalmente muito longas, um laboratório resolveu compactar as sequências de DNA de diversos organismos disponíveis em seu banco de dados utilizando codificação de Huffman. Um determinado organismo X possui uma cadeia de DNA D com N caracteres (onde cada caracter representa uma base possível{A p/ adenina, C p/ citosina, G p/ guanina e T p/ timina}). Ao final do processo de compactação da sequência D do organismo X, a seguinte árvore binária de Huffman foi produzida:

Com essa árvore em mãos, qual seria a sequência de bases do DNA do organismo X para o seguinte trecho da sequência binária correspondente: "...1110010110..."

1. "...ATTAG..."
2. "...GAACT..."
3. "...TGGAC..."
4. "...TTTGAC..."
5. NDA

Autor(a): Matheus Silva Mota