Algoritmos e Heurísticas para Seqüenciamento de DNA Geraldo FERREIRA & Tiago MACAMBIRA DCC-UFMG Objetivos • • • • • Apresentação do Ambiente Biológico Alinhamento Global Alinhamento Local Alinhamento Múltiplo Ferramenta BLAST Agosto de 2003 Geraldo FERREIRA Tiago MACAMBIRA 2 Mundo Biológico • • • • • • Corpo Célula Cromossomo Genoma/Gene DNA Bases Agosto de 2003 Geraldo FERREIRA Tiago MACAMBIRA 3 Alinhamento Global • 2 seq. basicamente similares durante todo comprimento • Tenta casar fim-a-fim uma sequência sobre a outra A A A G C G G A A G T C A C A G | | . | | . | | | | | | . | | A A G G C T G A A G T - A T A G Agosto de 2003 Geraldo FERREIRA Tiago MACAMBIRA 4 Alinhamento Local • Segmentos das 2 sequências com bons casamentos • Não existe a tentativa de forçar o alinhamento A A A G C G G A A G T C A C A G . . . . . . | | | | | . . . . A A G G C T G A A G T - A T A G Agosto de 2003 Geraldo FERREIRA Tiago MACAMBIRA 5 Pontuação de Similaridade • A Similaridade tenta inferir quão forte é a homologia • Atribuições: Match=1 , Mismatch=-1, Gap=-2 G A | | G A - T C G G A T T A G | | | | . | | | C G G A A T A G S= [9 x 1] + [1 x (-1)] +[1 x (-2)] = 6 Agosto de 2003 Geraldo FERREIRA Tiago MACAMBIRA 6 Alinhamento Global 1/3 • Calcula a similaridade dos prefixos curtos • Usa os resultados para o cálculo dos prefixos longos Agosto de 2003 Geraldo FERREIRA Tiago MACAMBIRA 7 Alinhamento Global 2/3 • Exemplo (Match=5, Mismatch= - 4, Gap w= -7 ) G C T G GAA G G C AT GCAGAGCACT Agosto de 2003 Geraldo FERREIRA Tiago MACAMBIRA 8 Alinhamento Global 3/3 • Caminho c/ mais altas pontuações = Caminho Ótimo • Custo para obtenção S[m,n] = O(m.n) • Custo para construção do caminho = O(m+n) Agosto de 2003 Geraldo FERREIRA Tiago MACAMBIRA 9 Alinhamento Local • Decidir quando um alinhamento local deve ser abandonado. • Modificar a recorrência para evitar pontuações abaixo de zero. • Pesquisar pelo S com maior pontuação. Caminhar de volta. Agosto de 2003 Geraldo FERREIRA Tiago MACAMBIRA 10 Alinhamento Múltiplo • Generalização do problema de alinhamento de duplas de seqüências • Geralmente usado com proteínas • Insere-se espaços em várias seqüencias para torná-las de mesmo tamanho • Como definir a qualidade de um alinhamento? – Métricas Agosto de 2003 Geraldo FERREIRA Tiago MACAMBIRA 11 Alinhamento Múltiplo • Intuição: – Estender os algoritmos de alinhamento de duplas • Como? – Função de Pontuação – Algoritmo de Programação dinâmica Agosto de 2003 Geraldo FERREIRA Tiago MACAMBIRA 12 Métrica SP • Função de Pontuação deve – Independente da ordem dos Argumentos – Premiar resíduos iguais ou relacionados – Penalisar espaços • Sum-of-Parts SP(a,b,c,d,) = p(a,b) + p(a,c) + p(a,d) + p(b,c) + p(b,d) + p(c,d) Agosto de 2003 Geraldo FERREIRA Tiago MACAMBIRA 13 Métrica SP e Programação Dinâmica • Extensão da matriz – Complexidade de espaço O(nk) – Complexidade de Tempo: O(k22knk) • Alinhamento Múltiplo com a métrica SP é NP-Completo • Heurísticas Agosto de 2003 Geraldo FERREIRA Tiago MACAMBIRA 14 Alinhamento Estrela • Heurística para alinhamento múltiplo – Construir o múltiplo usando apenas alinhamento de duplas – Sem garantias, mas bom na prática • Escolhe-se uma seqüência como centro da estrela • Alinhamento múltiplo é construído em torno da estrela • Complexidade tempo: O(kn2+k2l) Agosto de 2003 Geraldo FERREIRA Tiago MACAMBIRA 15 Busca em Banco de Dados • Vastos bancos de de seqüências • Algoritmos tradicionais muito lentos com as instâncias dadas • Heurísticas • BLAST (Basic Local Aligment Search Tool) Agosto de 2003 Geraldo FERREIRA Tiago MACAMBIRA 16 BLAST • Sementes • MSP (Maximal Segment Pair) • Funcionamento – Compila lista de palavras com alta pontuação – Busca casamentos entre essas palavras e seqüências no banco de dados – Estende casamentos para formar MSP Agosto de 2003 Geraldo FERREIRA Tiago MACAMBIRA 17 FIM Agosto de 2003 Geraldo FERREIRA Tiago MACAMBIRA 18