Skip to content

index.md

Latest commit

 

History

History
120 lines (78 loc) · 5.67 KB

index.md

File metadata and controls

120 lines (78 loc) · 5.67 KB
Raw

Alinhamento de Sequencias de DNA

Em Bioinformática, o problema de alinhamento de sequências de DNA consiste no processo de comparar duas ou mais sequências de bases de forma a se observar seu nível de similaridade. Trata-se de um problema extremamente importante no contexto atual, pois permite comparar sequencias virais de SARS-COV2 em bancos de dados genômicos para detecção de novas mutações.

O nível de similaridade pode ser calculado com base em acertos (match) e erros (gap e mismatch). Os acertos contribuem com sinal positivo (+) para o nível de similaridade e, os erros, com sinal negativo (-). Abaixo temos um exemplo de cálculo do nível similaridade:

image

Vamos associar a pontuação +1 (match) e as penalidades -1 (gap) e -4 (mismatch). Assim, teremos o seguinte nível de similaridade:

23 matches x (+1) + 4 gaps x (-1) + 3 mismatches x (-4) = 23-4-12 = 7

Neste contexto, o problema de alinhamento de sequencias de DNA pode ser colocado da seguinte forma:

Dadas duas sequencias de DNA, com as bases A,T,G,C e - para indicar gap, 
encontrar o alinhamento que maximize o nível de similaridade.

Neste projeto, seu objetivo será construir programas para encontrar este alinhamento de nível máximo de similaridade, utilizando várias estratégias.

Cada um dos seus programas tomará como entrada a seguinte estrutura: a primeira linha contém dois números n e m, onde n é o tamanho da primeira sequencia e, m, o tamanho da segunda. Assuma n ≤ 200 e m ≤ 200. A segunda linha contém as bases da primeira sequencia e, a terceira linha, as bases da segunda.

5 7
AT-CC
TTTCCAA

A saída deve ser uma linha com um número inteiro indicando o nível máximo de similaridade.

2

Neste caso, este nível máximo de similaridade pode ser associado ao alinhamento T-CC/TTCC (1-1+1+1=2) ou a CC/CC(1+1=2). Você pode usar o notebook SequenceGenerator.ipynb para gerar instâncias aleatórias para seus testes.

Estratégias a serem estudadas e correção automática

Para cada estratégia que vamos estudar, implementaremos um programa correspondente no projeto. Veja abaixo as datas de entrega e descrições de cada estratégia a ser implementada. Em geral, o enunciado de uma parte é liberado após a data de entrega da parte anterior.

  1. Solução Heurística (18/03)
  2. Busca Local(01/04)
  3. Busca Exaustiva(15/04)
  4. Relatório Preliminar (29/04)
  5. Paralelismo Multicore (13/05)
  6. Paralelismo GPU (27/05)
  7. Relatório Final (03/06)

Avaliação

O projeto será avaliado usando rubricas para as entregas básicas. As rubricas de avaliação dos relatórios estarão descritas em suas páginas de entrega.

Conceito D

Algum dos seguintes itens não foi entregue corretamente ou possui problemas sérios (no caso do relatório final).

  1. Solução heurística
  2. Busca local
  3. Busca exaustiva
  4. Busca local paralela (CPU)
  5. Busca local paralela (GPU)
  6. Relatório preliminar
  7. Relatório final

Conceito C

Todas as atividades abaixo foram validadas pelo corretor e (no caso do relatório final) alcançaram qualidade mínima exigida.

  1. Solução heurística
  2. Busca local
  3. Busca exaustiva
  4. Busca local paralela (CPU)
  5. Busca local paralela (GPU)
  6. Relatório preliminar
  7. Relatório final

Conceito C+

Além do já validado no conceito C, os relatórios entregues não tinham nenhum ponto em desenvolvimento ou insatisfatório na rubrica do relatório.

Conceitos avançados

A partir do conceito C+ cada atividade avançada vale meio conceito. Elas serão listadas aqui conforme o semestre avança e serão testadas pela checagem de resultados disponível no repositório de entregas.