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 em scanf(" %c", &caractere). Após inserida a núcleo-base, deve-se mostrar uma mensagem como a do exemplo para a operação inserir 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ção transpor 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:

1. 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.

2. 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.

3. 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.

← Anterior Voltar Próximo →