O sequenciamento genético corresponde a identificar a ordem em que os nucleotídeos ou, mais precisamente, suas bases nitrogenadas, aparecem em um DNA. Uma sequência de três bases codifica um aminoácido e, assim, sequências maiores codificam proteínas. Nesta tarefa, cada base será representada por um caractere correspondente, como A, T, C e G, e o sequenciamento genético será representado por uma string com esses caracteres, como a seguinte:

CACGTTACGAATAAATGGAGTGCGGCC

Cientistas trabalham no sequenciamento genético da mandioca. Imagem: Neil Palmer / CIAT.

Para resolver os vários problemas relacionados ao sequenciamento genético, recorrentemente é necessário resolver subproblemas comuns, como medir a “distância” entre duas strings, etc. Você deverá implementar um conjunto de funções, especificadas e documentadas no arquivo sequencias.py disponível no seu repositório. Esse arquivo contém apenas os stubs das funções e você deverá completar com a implementação que cumpra o comportamento desejado. Você usará essas funções para auxiliar na escrita dos programas ruido.py e diferencas.py, que resolverão os problemas abaixo.

1. Ruído

Ruído é um um conceito fundamental estudado no processamento de sinal, na análise de dados e em várias outras áreas da Computação e afins. Nessas disciplinas, a informação é transmitida na forma de um sinal e o ruído refere-se a modificações ou adições indesejadas nos dados do sinal com que desejamos trabalhar. Por exemplo, em comunicação por rádio, a interferência eletromagnética pode se sobrepor ao sinal real. Em dados de sensores, como o de temperatura, problemas físicos podem provocar leituras incorretas em meio a uma sequência de leituras corretas. Em processos que dependem de seres humanos, como análises laboratoriais, pode haver a entrada de dados inválidos.

A distância de Hamming

Uma técnica básica para lidar com certos tipos de ruído é o cálculo da distância de Hamming. Dadas duas sequências de mesmo tamanho $x$ e $y$, a distância de Hamming entre $x$ e $y$, denotada por $d(x,y)$, é o número de posições em que as sequências são diferentes. Por exemplo, para duas sequências de bits $x = 0100$ e $y = 1101$, a distância de Hamming é $d(x,y) = 2$, pois essas sequências têm bits diferentes nas posições 0 e 3.

Uma maneira de usarmos essa medida para lidar com ruído está descrita em seguida. Consideramos como válidas para nossa aplicação apenas algumas sequências acordadas previamente. Caso recebamos uma sequência desconhecida durante o processo de transmissão de dados, substituímos essa sequência pela sequência pré-acordada mais parecida. Para decidir qual sequência é mais parecida, escolhemos aquela com a menor distância de Hamming.

Por exemplo, dois amigos músicos resolvem conversar por sequências melódicas. Assim, uma nota curta representa um bit $0$ e uma nota longa representa um bit $1$. Como não é possível identificar a duração de notas individualmente, eles combinam que uma sequência $111$ significa sim e uma sequência $000$ significa não. Se um deles escuta uma sequência de notas correspondente a $010$, concluirá que na verdade a sequência deveria ser $000$ e interpretará a resposta como não. A razão é que $d(010,000) = 1$, enquanto $d(010,111) = 2$.

Nosso problema

Em um laboratório, você precisa identificar qual espécie de bactéria foi encontrada em um processo infeccioso. Feita uma cultura da bactéria e o sequenciamento de parte de seu genoma, sua tarefa é determinar a espécie correspondente dentre um conjunto de bactérias conhecidas.

Para isso, você deverá escrever um programa ruido.py que receberá a sequência da amostra a ser identificada, bem como vários trechos dos sequenciamentos genéticos das espécies candidatas. Suponha que todas as sequências têm o mesmo comprimento e que a espécie mais provável é aquela que cujo trecho tem a menor distância de Hamming.

Entrada

A primeira linha contém a sequência a ser identificada. Na segunda linha, há um número $n$ de sequências candidatas. Em seguida, há $n$ linhas, cada uma com o trecho de uma espécie candidata.

ACATT
3
GCGAT
ACAGT
ACGTT

Saída

Sequência mais próxima: ACAGT
Distância de Hamming: 1

2. Diferenças

Uma nova variante de uma bactéria foi identificada. Infelizmente, ela parece ser mais resistente ao antibiótico usado normalmente. Por esse motivo, é importante identificar as diferenças genéticas entre a nova variante e o genoma de referência.

Nesta tarefa, vamos considerar que um gene é uma subsequência de tamanho fixo do genoma, chamada de janela. Por exemplo, se a janela tem tamanho 3, então a sequência CTTAGCACC representa três genes: CTT, AGC e ACC, indexados nas posições 0, 3 e 6.

Sua tarefa é construir um programa diferencas.py que identifica os genes como maior diferença. Iremos supor que as sequências correspondentes à nova variante e ao genoma de referência têm o mesmo comprimento.

Entrada

A primeira linha contém o tamanho de uma janela, a segunda linha a sequência do genoma de referência e a terceira, o genoma da variante.

4
AAAATTTTGGGGCCCC
AGGATTATGGGGAAAC

Saída

Para cada gene da variante cuja distância de Hamming ao gene correspondente de referência seja pelo menos um terço do tamanho da janela, deve ser listada a diferença. Se houver vários genes diferentes, então os genes devem ser listados em ordem de posição em que aparecem.

Diferença 1:
   Posição: 0
Referência: AAAA
  Variante: AGGA
 Distância: 2

Diferença 2:
   Posição: 12
Referência: CCCC
  Variante: AAAC
 Distância: 3

Critérios

Nesta e nas próximas tarefas, é obrigatório organizar seus programas usando funções adequadamente: é proibido executar instruções fora de funções. Construa uma função principal main e certifique-se de que cada função criada tenha uma uma única responsabilidade. Separe funções responsáveis pela entrada e saída dos dados das funções que resolvem o problema.

Nos seus algoritmos, você deve exercitar as funções definidas no módulo sequencias.py, mesmo que você conheça algoritmos mais simples.

Dicas e observações

Funções que devolvem mais de um item

A linguagem Python dá suporte a funções que devolvem mais do que um item. Veja o exemplo abaixo:

def soma_e_diferenca(a, b):
    return a + b, a - b

soma, diferenca = soma_e_diferenca(7, 4)
print(soma)         # mostra 11
print(diferenca)    # mostra 3

Usando funções de um módulo

Relembre que quando definimos uma função func() e a utilizamos no mesmo arquivo, basta escrever

func(parametros)

para chamá-la, passando os parâmetros adequados. No entanto, se a função está definida em um arquivo nome_do_modulo.py, precisamos importar o módulo antes. Uma maneira de fazer isso é:

import nome_do_modulo

nome_do_modulo.func(parametros)

Existem outras formas de importar componentes (funções e outros) de um módulo, que você irá aprender com o tempo.

Testes de unidade

Nas tarefas anteriores, usamos apenas testes que comparavam a saída do programa com a saída de referência. Isso testa o comportamento do programa como um todo.

Quando organizamos nosso programa em funções, é essencial testar cada função individualmente. Assim, os testes podem ser mais simples e potencialmente identificar erros de programação antes mesmo que eles afetem o programa em si.

Além disso, é muito comum que o comportamento de um programa esteja errado por motivos difíceis de atribuir a uma linha ou parte específica do código. Em geral, é bem mais simples depurar erros de uma função.

Um teste que verifica uma função é chamado de teste de unidade. Geralmente, um teste de unidade é um código escrito na mesma linguagem do elemento em teste e faz uso direto do código a ser testado.

import modulo

# testa função soma, presente no módulo
def teste_soma():
    assert modulo.soma(7, 4) == 11, "Falha na função soma"

É importante testar combinações diferentes de parâmetros para uma mesma função, a fim de cobrir mais casos. Você pode testar suas próprias funções desta maneira, isto é, fazendo chamadas a uma função específica que deseja testar.

Nesta tarefa, além de testar a saída de seus programas, serão testadas também as funções do módulo sequencias.py que você implementará. É para isso que serve o arquivo testa_funcoes.py.

Correção

Esta tarefa será corrigida automaticamente sempre que você realizar um git push. Depois de terminada a tarefa, deve-se utilizar o botão na interface de notas para solicitar a correção de um monitor.

← Anterior Voltar Próximo →