CS50-MCZ

Uma introdução aos empreendimentos intelectuais da Ciência da Computação e da arte da programação.


DNA

Implemente um programa que identifique uma pessoa com base em seu DNA, conforme abaixo.

$ python dna.py databases/large.csv sequences/5.txt
Lavender

Começando

Abra o VS Code.

Comece clicando dentro da sua janela de terminal e, em seguida, execute cd por si só. Você deve encontrar que seu "prompt" se parece com o abaixo.

$

Clique dentro daquela janela de terminal e, em seguida, execute

wget https://cdn.cs50.net/2022/fall/psets/6/dna.zip

seguido de Enter para baixar um ZIP chamado dna.zip no seu espaço de código. Certifique-se de não ignorar o espaço entre wget e a URL a seguir, ou qualquer outro caractere!

Agora execute

unzip dna.zip

para criar uma pasta chamada dna. Você não precisa mais do arquivo ZIP, portanto, pode executar

rm dna.zip

e responda com "y" seguido de Enter no prompt para remover o arquivo ZIP que você baixou.

Agora digite

cd dna

seguido de Enter para se mover para dentro desse diretório. Seu prompt deve agora se parecer com o abaixo.

dna/ $

Execute ls sozinho e você deverá ver alguns arquivos e pastas:

databases/ dna.py sequences/

Se você tiver algum problema, siga esses mesmos passos novamente e veja se consegue determinar onde errou!

Contexto

O DNA, portador de informações genéticas em seres vivos, tem sido utilizado na justiça criminal por décadas. Mas como exatamente funciona o perfil de DNA? Dada uma sequência de DNA, como os investigadores forenses podem identificar a quem ele pertence?

Bem, o DNA é realmente apenas uma sequência de moléculas chamadas nucleotídeos, dispostas em uma forma específica (uma dupla hélice). Cada célula humana tem bilhões de nucleotídeos dispostos em sequência. Cada nucleotídeo do DNA contém uma das quatro bases diferentes: adenina (A), citosina (C), guanina (G) ou timina (T). Algumas partes dessa sequência (ou seja, genoma) são as mesmas, ou pelo menos muito semelhantes, em quase todos os seres humanos, mas outras partes da sequência apresentam uma diversidade genética maior e, portanto, variam mais na população.

Um local onde o DNA tende a ter alta diversidade genética é em Repetições em Tandem Curtas (STRs). Um STR é uma sequência curta de bases de DNA que tende a se repetir consecutivamente numerosas vezes em locais específicos dentro do DNA de uma pessoa. O número de vezes que um determinado STR se repete varia muito entre os indivíduos. Nas amostras de DNA abaixo, por exemplo, Alice tem o STR AGAT repetido quatro vezes em seu DNA, enquanto Bob tem o mesmo STR repetido cinco vezes.

Exemplo de STRs

O uso de vários STRs, em vez de apenas um, pode melhorar a precisão do perfil de DNA. Se a probabilidade de duas pessoas terem o mesmo número de repetições para um único STR é de 5%, e o analista olha para 10 STRs diferentes, então a probabilidade de duas amostras de DNA coincidirem puramente por acaso é de cerca de 1 em 1 quatrilhão (assumindo que todos os STRs são independentes entre si). Portanto, se duas amostras de DNA coincidirem no número de repetições de cada um dos STRs, o analista pode ter bastante confiança de que elas vieram da mesma pessoa. O CODIS, o banco de dados de DNA do FBI, usa 20 STRs diferentes como parte de seu processo de perfil de DNA.

Como seria um banco de dados de DNA desse tipo? Bem, em sua forma mais simples, você pode imaginar a formatação de um banco de dados de DNA como um arquivo CSV, em que cada linha corresponde a um indivíduo e cada coluna corresponde a um STR específico.

name,AGAT,AATG,TATC
Alice,28,42,14
Bob,17,22,19
Charlie,36,18,25

Os dados no arquivo acima sugerem que Alice tem a sequência AGAT repetida 28 vezes consecutivamente em algum lugar do seu DNA, a sequência AATG repetida 42 vezes, e TATC repetida 14 vezes. Enquanto isso, Bob tem esses mesmos três STRs repetidos 17 vezes, 22 vezes e 19 vezes, respectivamente. E Charlie tem esses mesmos três STRs repetidos 36, 18 e 25 vezes, respectivamente.

Então, dada uma sequência de DNA, como você pode identificar a quem ela pertence? Bem, imagine que você procurou na sequência de DNA a sequência consecutiva mais longa de AGATs repetidas e descobriu que a sequência mais longa era de 17 repetições. Se você então descobrisse que a sequência mais longa de AATG é de 22 repetições e a sequência mais longa de TATC é de 19 repetições, isso forneceria uma evidência bastante boa de que o DNA era de Bob. Claro, também é possível que, uma vez que você tenha as contagens para cada um dos STRs, isso não corresponda a ninguém em seu banco de dados de DNA, nesse caso, você não tem uma correspondência.

Na prática, como os analistas sabem em qual cromossomo e em qual localização do DNA um STR será encontrado, eles podem localizar sua pesquisa apenas em uma seção estreita do DNA. Mas vamos ignorar esse detalhe para este problema.

Sua tarefa é escrever um programa que receberá uma sequência de DNA e um arquivo CSV contendo contagens de STRs para uma lista de indivíduos e, em seguida, indicar a quem o DNA (provavelmente) pertence.

Especificação

Em um arquivo chamado dna.py, implemente um programa que identifique a quem pertence uma sequência de DNA.

Uso

Seu programa deve se comportar conforme o exemplo abaixo:

$ python dna.py databases/large.csv sequences/5.txt
Lavender
  
$ python dna.py
Usage: python dna.py data.csv sequence.txt
  
$ python dna.py data.csv
Usage: python dna.py data.csv sequence.txt

Dicas

Testando

Embora o check50 esteja disponível para este problema, você é incentivado a testar seu código primeiro por conta própria para cada um dos seguintes testes.

Execute o código abaixo para avaliar a correção do seu código usando o check50. Mas certifique-se de compilá-lo e testá-lo por conta própria também!

check50 cs50/problems/2023/x/dna

Execute o código abaixo para avaliar o estilo do seu código usando style50.

style50 dna.py

Como Enviar

No seu terminal, execute o seguinte comando para enviar o seu trabalho.

submit50 cs50/problems/2023/x/dna