Baixe o app para aproveitar ainda mais
Prévia do material em texto
1 IBM1029 Introdução à Bioinformática Aula 4 Profª Drª Silvana Giuliatti Departamento de Genética – Bloco G Ramal: 4503 silvana@rge.fmrp.usp.br Faculdade de Medicina Departamento de Genética Alinhamentos de Sequências Alinhamentos de Sequências • Objetivo: Descobrir informações evolucionárias, estruturais e funcionais em sequências de proteínas ou DNA. Alinhamentos: • pares de sequências • múltiplas sequências Similaridade: possuem regiões similares Homologia: possuem mesmo ancestral Alinhamentos de Sequências Gene (duplicação do gene) gene cadeia - α gene cadeia - β sapo α galinha α camundongo α camundongo β galinha β sapo β ortólogos parálogos ortólogos homólogos Alinhamento de Pares de Sequências Compara duas sequências e procura por similaridades Alinhamentos: • Local: regiões similares constituem uma parte das sequências • Global: similaridade é considerada ao longo de toda extensão das sequências. Alinhamentos de Pares de Sequências LGPSSKQTGKGS-SRIWDN | | ||| | | LN-ITKSAGKGAIMRLGDA ----TGKG------ ||| ----AGKG------ Global Local 2 Pode haver mais de um alinhamento possível. Considere: ACGGACT e ATCGGATCT Dois possíveis alinhamentosDois possíveis alinhamentos Alinhamentos de Pares de Sequências A - C - G G - A C T | | | | | A T C G G A T - C T A - C G G - A C T | | | | | | A T C G G A T C T Métodos de Alinhamentos: 9Matrizes de Pontos: todas as possíveis combinações entre as sequencias são encontradas. 9Programação Dinâmica: matematicamente garantida para encontrar um alinhamento ótimo (global ou local) entre pares de sequênciais. • Matrizes de Substituição 9Método de palavras ou k- tuplas: • Alinhamento heurístico: mais rápido que a programação dinâmica, mas não garante o alinhamento ótimo. É ideal para pesquisa em banco de dados. Alinhamentos de Pares de Sequências Matrizes de Pontos Matrizes de Pontos • Descrito pela primeira vez por Gibbs e McIntyre (1970). • Usado para comparar duas sequências através de um possível alinhamento de caracteres entre elas. • Todos os possíveis alinhamentos são encontrados. • A detecção de regiões pode ser melhorada através de filtros. Matrizes de Pontos 1 - Uma sequência é disposta em uma linha e a outra listada em uma coluna, uma ao lado da outra. 2 - Um ponto deve ser colocado em cada local onde os caracteres são iguais. 3 - A diagonal principal revela a similaridade entra as sequências. H C G E T F G R W F T P E W H • C • G • E • T • F • G • R • W • F • T • P • E • W • Matrizes de Pontos 4 - Pode também apresentar regiões de repeats e repeats invertidos fora da diagonal principal. Qualquer região similar entre as sequências é revelada por uma diagonal. 5 - Pontos isolados representam similaridades aleatórias não relacionadas ao alinhamento. 3 Matrizes de Pontos Programas para Matrizes de Pontos Dotlet (www.isrec.isb-sib.ch/java/dotlet/Dotlet.html) • Disponível pela Internet • Sequências curtas: até 10.000 caracteres • Todas as plataformas Dotter (www.cgr.ki.se/cgr/groups/sonnhammer/Dotter.html) • Sequências até 100.000 caracteres • Linux, Windows, Unix EMBOSS (Dottup, Dotmatcher) (www.emboss.org) • Sequências maiores de 100.000 caracteres • Unix, Linux Matrizes de Pontos Dotlet Matrizes de Pontos Dotlet Matrizes de Pontos Dotter Matrizes de Pontos Dotmatcher Programação Dinâmica 4 Qual o melhor caminho de Ribeirão Preto a São Paulo? Os algoritmos de programação dinâmica solucionam os problemas de otimização: há várias soluções possíveis, mas encontra-se uma solução ótima dividindo o problema original em subproblemas e solucionando-os (“problema do caixeiro viajante”). Programação Dinâmica • É um método de alinhamento de pares de seqüências (proteínas ou DNA) que pode levar em conta lacunas (gaps), mas com um número de comparação aceitável. •Proporciona um ótimo alinhamento (mais alta pontuação (score) ). • Limitação: pode ser lento. O número de etapas necessárias depende do comprimento das sequências. Programação Dinâmica • Conceito de Score (escore, pontuação): medida pela qual os alinhamentos são quantificados. Considere: ACGGACT e ATCGGATCT Dois possíveis alinhamentos. Qual é o melhor? A - C - G G - A C T | | | | | A T C G G A T - C T A - C G G - A C T | | | | | | A T C G G A T C T Alinhamento 1 Alinhamento 2 Programação Dinâmica Considere o seguinte esquema simples de score: + 2 para igualdade (match) - 1 para desigualdade (mismatch) - 2 para penalidade (gaps) Programação Dinâmica Para o alinhamento 1: Para o alinhamento 2: A - C - G G - A C T | | | | | A T C G G A T - C T +2-2+2-2+2-1-2-2+2+2 = 1 A - C G G - A C T | | | | | | A T C G G A T C T +2-2+2+2+2-2-1+2+2 = 7 Programação Dinâmica As etapas da Programação Dinâmica a) Escolher um modelo de pontuação b) Gerar a matriz (determinar os scores) c) Determinar o alinhamento ótimo (traçar o alinhamento a partir do melhor score). 5 Programação Dinâmica ALINHAMENTO GLOBAL Algoritmo de Needleman-Wunsch (1970). Alinhamento permite gaps e ocorre em toda a extensão das sequências. • Programação Dinâmica ALINHAMENTO GLOBAL A matriz de pontuação F(i,j) é construída recursivamente. ¾ Inicia com F(0,0) = 0 ( gaps) ¾ Constrói um alinhamento ótimo usando soluções prévias de subsequências menores. ¾ Preenche a matriz do canto esquerdo superior até o canto direito inferior. Programação Dinâmica ALINHAMENTO GLOBAL a) Considere duas sequências: X: C T T A G A Y: G T A A onde o modelo de pontuação é: s (a, a) = 1 (match) s (a, b) = -1 (mismatch) s (a, - ) = s (- , b) = -2 (gap) Programação Dinâmica ALINHAMENTO GLOBAL Condições Iniciais: F (i, 0) = w x i F (0, j) = w x j b) Para cada posição, F (i, j) será determinado pelo score máximo na posição (i, j), calculado como segue: F (i - 1, j -1) + s(xi , yj) F (i - 1, j) + w (x alinhado a gap) F (i, j - 1) + w (y alinhado a gap) F (i, j) = max Onde w = -2 (gap) Programação Dinâmica F(i, j) F(i-1, j-1) F(i, j-1) F(i-1, j) -2±1 -2 0 1 2 3 4 - G T A A 0 - 1 C 2 T 3 T 4 A 5 G 6 A 0 - 4-2 - 2 -4 -6 - 8 - 10 - 12 - 8- 6 - 5 - 7 -7 - 9 - 3 - 1 - 3 - 5 - 7 0 - 2 - 4 - 2 - 1 - 3 - 4 - 1 0 - 6 - 3 - 2 - 2- 5- 8
Compartilhar