Parque Jurássico

O DNA é uma molécula envolvida na transmissão de caracteres hereditários e na produção de proteínas, que são os principais constituintes de seres vivos. O DNA é formado pelas bases nitrogenadas adenina (A), guanina (G), citosina (C) e timina (T). A identificação da seqüência de bases que constitui uma determinada parte do DNA pode ajudar a descoberta da cura de doenças que atacam seres vivos. Teoricamente, a identificação do DNA pode também permitir a recriação de espécies extintas, como na estória do escritor americano Michael Crichton. O professor de Biologia de sua escola, prof. Estevão Espilbergo, conseguiu amostras de células de uma espécie de mosquito extinto a milhares de anos, e pretende, ambiciosamente, recriar o animal a partir de seu DNA. Para isso, conseguiu que um laboratório de genômica fizesse a identificação das bases das células. No entanto, pelo estado precário das células obtidas, o resultado não foi dos melhores. O professor Estevão recebeu do laboratório duas seqüências, com a informação de que essas seqüências contêm, provavelmente, muitos “buracos”, ou seja, entre uma base e outra corretamente detectadas podem existir bases não detectadas. O prof. Estevão então decidiu combinar as duas seqüências para formar uma seqüência única, e precisa de sua ajuda.

Sua tarefa é escrever um programa que determine a menor seqüência que contenha, como subseqüências, as duas seqüências obtidas pelo laboratório. Dizemos que uma seqüência S₁ é subseqüência de uma outra seqüência S₁ se acrescentando-se alguns elementos a S₂obtém-se S₂ . Por exemplo, ACGT é uma subseqüência de ATCGAAT, pois basta inserir um T após o A e dois A’s após o G.(1≥número de caracteres de S ≥ 100)