E05 Genes
Neste exercício, vamos definir gene como sendo palavras sobre o alfabeto \(\Sigma=\{A, C, T, G\}\) que satisfazem os critérios dados/implementados em PotentialGene.java em
https://www.ime.usp.br/~yoshi/2023ii/mac0122/sandbox/2023.10.11/
Assim, $s\in\Sigma^*$ é um gene se o programa PotentialGene.java executado com entrada $s$ imprime true. Será mais conveniente chamarmos de gene a palavra $s$ toda, incluindo o start codon e o stop codon.
Lembre que na página 43 de
https://www.ime.usp.br/~yoshi/Sedgewick/cos126.2017i/CS.08.ADTs.pdf
é sugerido, em linhas gerais, um algoritmo para encontrar genes em genomas. Uma implementação parcial da ideia lá esboçada é
https://introcs.cs.princeton.edu/java/31datatype/GeneFind.java.html
Note que GeneFind.java considera cada stop codon separadamente. Uma implementação que considera os três stop codons conjuntamente é dado em GeneFindImproved.java abaixo.
Exercício. Um primeiro exercício instrutivo é verificar que se uma palavra $s$ faz parte da saída de GeneFindImproved.java, então $s$ é um gene, isto é, PotentialGene.java executado com entrada $s$ tem saída true.
Algoritmo de força bruta e a não completude de GeneFindImproved.java. Podemos encontrar todos os genes em uma palavra $t\in\Sigma^*$ executando FindGeneBrute.java, dado abaixo.
Exercício. Dê um exemplo de entrada $t$ para GeneFindImproved.java que contém mais genes que GeneFindImproved.java encontra. Isto é, encontre $t$ tal que FindGeneBrute.java executado com entrada $t$ produz mais saída que GeneFindImproved.java produz quando executado com a mesma entrada $t$.
Um programa completo e mais eficiente. Neste exercício, você deve escrever um programa chamado FindGene.java que encontra todos os genes em uma palavra $t\in\Sigma^*$ dada como entrada. A menos da ordem das palavras na saída, seu programa deve ter a mesma saída que FindGeneBrute.java. A segunda exigência sobre FindGene.java é que ele deve ser bem mais eficiente que FindGeneBrute.java.
Eficiência de FindGene.java. Como os exemplos de execução abaixo ilustram, espera-se que FindGene.java tenha tempo de execução grosso modo proporcional ao comprimento da entrada.
O programa Generate.java é usado para gerar entradas aleatórias. O programa wc executado com opção -l conta o número de linhas que ele recebe na entrada padrão.
$ java-introcs Generate 500 122 | java-introcs FindGene
ATGAAACCCTTTTGA
ATGTACAAACCTACCGGTGGAACTGAGGTCTTTGTGCGTCCATGGGAAATTTTGTTTGGTTAA
ATGCACATTAGCTGCCTCAAGACAATCCCGCGTATTCGACGGAACTAA
ATGTGA
ATGGACGACCACCATCCAACGCCTATAATATGCACATTAGCTGCCTCAAGACAATCCCGCGTATTCGACGGAACTAAAATGGCTTATAGGCATTGTTCTCGCACTATGTTCCCCATGGGGTACGGGACTAACAGACAATTTGTCCATTCGTTTTAG
ATGGCTTATAGGCATTGTTCTCGCACTATGTTCCCCATGGGGTACGGGACTAACAGACAATTTGTCCATTCGTTTTAG
ATGTTCCCCATGGGGTACGGGACTAACAGACAATTTGTCCATTCGTTTTAG
ATGGGGTACGGGACTAACAGACAATTTGTCCATTCGTTTTAG
ATGGGAAATTTTGTTTGGTTAACATAA
$ java-introcs Generate 500 122 | java-introcs FindGene | wc -l
9
$ time java-introcs Generate 1000000 122 | java-introcs FindGene | wc -l
15854
real 0m1.238s
user 0m2.054s
sys 0m0.680s
$ time java-introcs Generate 2000000 122 | java-introcs FindGene | wc -l
31457
real 0m2.303s
user 0m3.819s
sys 0m1.249s
$ time java-introcs Generate 4000000 122 | java-introcs FindGene | wc -l
62878
real 0m4.357s
user 0m6.964s
sys 0m2.101s
$ time java-introcs Generate 8000000 122 | java-introcs FindGene | wc -l
125476
real 0m8.382s
user 0m13.501s
sys 0m3.466s
$
Note que FindGeneBrute.java comporta-se bem pior conforme o tamanho da entrada aumenta:
$ time java-introcs Generate 1000 122 | java-introcs FindGeneBrute | wc -l
16
real 0m0.182s
user 0m0.308s
sys 0m0.068s
$ time java-introcs Generate 2500 122 | java-introcs FindGeneBrute | wc -l
42
real 0m0.456s
user 0m0.555s
sys 0m0.140s
$ time java-introcs Generate 5000 122 | java-introcs FindGeneBrute | wc -l
78
real 0m1.588s
user 0m1.676s
sys 0m0.215s
$ time java-introcs Generate 10000 122 | java-introcs FindGeneBrute | wc -l
152
real 0m10.199s
user 0m10.553s
sys 0m0.405s
$ time java-introcs Generate 20000 122 | java-introcs FindGeneBrute | wc -l
330
real 1m30.753s
user 1m31.899s
sys 0m2.312s
$
Comparação das saídas de FindGene.java e FindGeneBrute.java. Para comparar as saídas de seu FindGene.java e FindGeneBrute.java, você pode ordenar as saídas usando o programa sort:
$ java-introcs Generate 400 122 | java-introcs FindGeneBrute | sort
ATGAAACCCTTTTGA
ATGCACATTAGCTGCCTCAAGACAATCCCGCGTATTCGACGGAACTAA
ATGGACGACCACCATCCAACGCCTATAATATGCACATTAGCTGCCTCAAGACAATCCCGCGTATTCGACGGAACTAAAATGGCTTATAGGCATTGTTCTCGCACTATGTTCCCCATGGGGTACGGGACTAACAGACAATTTGTCCATTCGTTTTAG
ATGGCTTATAGGCATTGTTCTCGCACTATGTTCCCCATGGGGTACGGGACTAACAGACAATTTGTCCATTCGTTTTAG
ATGGGGTACGGGACTAACAGACAATTTGTCCATTCGTTTTAG
ATGTGA
ATGTTCCCCATGGGGTACGGGACTAACAGACAATTTGTCCATTCGTTTTAG
$ java-introcs Generate 400 122 | java-introcs FindGene | sort
ATGAAACCCTTTTGA
ATGCACATTAGCTGCCTCAAGACAATCCCGCGTATTCGACGGAACTAA
ATGGACGACCACCATCCAACGCCTATAATATGCACATTAGCTGCCTCAAGACAATCCCGCGTATTCGACGGAACTAAAATGGCTTATAGGCATTGTTCTCGCACTATGTTCCCCATGGGGTACGGGACTAACAGACAATTTGTCCATTCGTTTTAG
ATGGCTTATAGGCATTGTTCTCGCACTATGTTCCCCATGGGGTACGGGACTAACAGACAATTTGTCCATTCGTTTTAG
ATGGGGTACGGGACTAACAGACAATTTGTCCATTCGTTTTAG
ATGTGA
ATGTTCCCCATGGGGTACGGGACTAACAGACAATTTGTCCATTCGTTTTAG
$
Você ainda pode usar o programa md5sum (ou md5 no macOS) para verificar se as saídas coincidem:
$ java-introcs Generate 400 122 | java-introcs FindGeneBrute | sort | md5
2680cad2595e448a6868216d27eeffc7
$ java-introcs Generate 400 122 | java-introcs FindGene | sort | md5
2680cad2595e448a6868216d27eeffc7
$
O fato que as saídas produzidas por md5 nas execuções acima coincidem significa que, muito provavelmente, as saídas produzidas por sort coincidem. Se as saídas de md5 fossem diferentes, teríamos certeza de que as saídas de sort foram diferentes.
Por exemplo, o seguinte mostra que GeneFindImproved.java produz uma saída diferente:
$ java-introcs Generate 400 122 | java-introcs GeneFindImproved | sort | md5
547ec4b519798bfccc5bfa46fd9c13f2
$
Mais exemplos de execução. Veja alguns exemplos de execução no arquivo experiments.txt abaixo. Os tempos de execução de seu programa devem ser, grosso modo, comparáveis aos tempos nesses exemplos.
O arquivo E05.tar.gz tem o mesmo conteúdo que E05.
Entrega. Entregue apenas seu programa FindGene.java.
- 15 octobre 2023, 20:58
- 15 octobre 2023, 20:58