Prazo de entrega:
Segunda chance:
Esta tarefa tem peso 1.
Armazene uma sequência de DNA e simule diversas mutações que podem ocorrer nessa sequência. Para poder realizar operações arbitrárias sobre a sequência, você deverá representá-la como uma lista ligada.
Para expandir o nosso entendimento sobre a evolução, cientistas estudam e comparam as diferenças dos genomas de diversas espécies. A distância evolucionária entre duas espécies pode ser dada através da distância de rearranjo de genomas. Uma mutação em grande escala pode ser representada através de um rearranjo do genoma. Assim, é útil que possamos representar computacionalmente sequências de DNA para simular certas mutações e medir o nível de semelhança entre diferentes espécies da mesma família. Você foi escolhido para colaborar com um grupo de cientistas da Unicamp em um estudo deste tipo. Sua parte no projeto é criar uma estrutura de dados que represente uma sequência de DNA e que suporte algumas operações de rearranjo.
Uma sequência de DNA deverá ser representada como uma lista ligada de
núcleo-bases. Cada núcleo-base é representada por um caractere que pode assumir
valor g
, c
, a
out
. Ao início de uma simulação, tem-se uma sequência
vazia. A partir deste ponto, deve ser possível adicionar uma núcleo-base à
sequência. Operações de inserção devem ter um parâmetro posicional, que indica o
índice que será ocupado pela nova núcleo-base na sequência atual. Também deve
ser possível remover uma núcleo-base de uma certa posição da sequência. Por fim,
a simulação deve suportar operações de rearranjo como inversão de prefixo ou
sufixo, que inverte a ordem da subsequência, e transposição, que move uma
subsequência de posição para outra.
Operações
Crie um programa sequencia
que realiza uma série de operações sobre sequências
de DNA. Cada linha da entrada corresponde ao nome de uma operação, que pode ser
seguido por um ou mais parâmetros, separados por espaços. As operações
suportadas pela simulação são detalhadas abaixo:
-
Inserção de uma núcleo-base:
inserir <caractere> <posição>
Insere um caractere representando uma núcleo-base na posição determinada. Dica: para ler um caractere diferente de espaço em branco, utilize um espaço antes da especificação
%c
, como emscanf(" %c", &caractere)
. Após inserida a núcleo-base, deve-se mostrar uma mensagem como a do exemplo para a operaçãoinserir g 2
:g inserido em 2
-
Remoção de uma núcleo-base
remover <posição>
Remove a núcleo-base da posição determinada. Após removida a núcleo-base, deve-se mostrar uma mensagem. Por exemplo, se a sequência atual for cgtaagctt e a operação for
remover 2
, a saída será:t removido de 2
-
Inversão de prefixo
inverter-prefixo <tamanho-prefixo>
Inverte as posições do prefixo do tamanho especificado. Por exemplo, se a sequência atual for cgaagctt, então a operação
inverter-prefixo 5
resultará na sequência gaagcctt. A saída deverá mostrar o prefixo antes e após a inversão, conforme o modelo para o exemplo:prefixo c g a a g -> g a a g c
-
Inversão de sufixo
inverter-sufixo <tamanho-sufixo>
Inverte as posições do sufixo do tamanho especificado. Por exemplo, se a sequência atual for gaagcctt, então a operação
inverter-sufixo 3
resultará na sequência gaagcttc. A saída deverá mostrar o sufixo antes e após a inversão, conforme o modelo para o exemplo:sufixo c t t -> t t c
-
Transposição de subsequência
transpor <p> <q> <r>
Transpõe a subsequência que começa em
<p>
e termina em<q>
em<r>
posições. A transposição tem o efeito de deslocar os caracteres representando núcleo-bases à direita, quando<r>
for positivo, ou à esquerda, quando for negativo. Por exemplo, se a sequência atual for gaagcttc, então a operaçãotranspor 2 3 3
resultará na sequência gacttagc. A saída deverá mostrar a subsequência e a direção do deslocamento, conforme o modelo para o exemplo anterior:subsequencia a g >> 3
Se logo em seguida executarmos a operação
transpor 4 7 -2
, a sequência resultante será gatagcct e a saída deverá ser:subsequencia t a g c << 2
-
Impressão da sequência atual
imprimir
Imprime a sequência de DNA atual com um espaço em branco separando cada núcleo-base, conforme exemplo:
sequencia g a t a g c c t
-
Finalização
sair
Saia do programa, liberando corretamente toda a memória utilizada. Não mostra nenhuma mensagem.
Exemplo de entrada
inserir t 0
inserir c 0
inserir g 0
inserir t 0
inserir g 0
inserir a 2
inserir c 0
inserir a 4
inserir t 7
remover 2
inverter-prefixo 5
inverter-sufixo 3
transpor 2 3 3
transpor 4 7 -2
imprimir
sair
Exemplo de saída
t inserido em 0
c inserido em 0
g inserido em 0
t inserido em 0
g inserido em 0
a inserido em 2
c inserido em 0
a inserido em 4
t inserido em 7
t removido de 2
prefixo c g a a g -> g a a g c
sufixo c t t -> t t c
subsequencia a g >> 3
subsequencia t a g c << 2
sequencia g a t a g c c t
Critérios
É obrigatório utilizar uma estrutura de lista ligada para a representação da sequência de DNA.
Submissão
Você pode fazer esta tarefa individualmente ou em dupla! O objetivo é que vocês tenham a oportunidade de projetar algoritmos e escrever programas em pares. Assim vocês podem trocar ideias e se ajudar mutuamente. Caso queira fazer esta tarefa em dupla, então siga algumas regrinhas:
-
Antes de começar a tarefa, converse e combine com um@ colega. Amb@s devem colaborar ativamente em todos os momentos da elaboração desta tarefa, incluindo ideias, projeto do algoritmo e escrita do código. Não é permitido dividir as atividades para cada um fazer uma parte separadamente.
-
Apenas um estudante deve submeter a tarefa e solicitar a correção aos monitores, mas ambos devem editar o arquivo de configuração
duplas.txt
fornecido no repositório para indicar o RA da dupla. O monitor corrigirá o código apenas do repositório do RA indicado nesse arquivo e registrará a nota para os dois estudantes no sistema. -
Tome cuidado para que sua dupla tenha acesso apenas aos arquivos desta tarefa. É proibido compartilhar ou mostrar arquivos de outras tarefas com a dupla, ou quaisquer arquivos das tarefas com terceiros. Vocês sempre podem pedir ajuda a monitor@s!
Se você preferir fazer esta tarefa individualmente, então edite o arquivo
duplas.txt
para que ele contenha apenas seu RA.