1

3/17/2005 1

Ana Teresa FreitasAna Teresa Freitas

MM éétodostodos parapara alinhamentoalinhamento de de pares de pares de sequênciassequências

3/17/2005 2

Índice

�Alinhamento de sequências

• Introdução• Distância de edição• Alinhamento de cadeias de caracteres• Funções de mér ito• Matr izes de substituição• Alinhamento global• Alinhamento local• Heur isticas para alinhamento

2

3/17/2005 3

Introdução�Avançosnaáreadabiologiamolécular permitem

um rápido aumento do número de genomassequenciados

�Crescimento exponencialdo Genbank

�A comunidade científica passou a dar maior ênfase à transformação da grande quantidade de dados existentes em conhecimento

3/17/2005 4

Taxas de crescimento

3

3/17/2005 5

Quesentido dar a estesdados?

3/17/2005 6

� A análise de sequências de biomoléculas (DNA, RNA ou Amino Ácidos) mostra que normalmente uma elevada semelhança entre sequências implica uma elevada semelhança entre funcionalidades ou estruturas

� Citações como a profer ida por Er ic Wieschaus, um dos vencedores do prémio Nobel da medicina em 1995:

“ We didn´t know it at the time, but we found out everything in life is so similar , that the same genes that work in flies are the ones that work in humans.” [Associated Press, 9 October , 1995]

e a profer ida por Francois Jacob em 1977:

“ Nature is a tinkerer and not an inventor” [Evolution and tinker ing, science 196:1161-1166]

4

3/17/2005 7

�Após a sequênciação de uma molécula de DNA émuitas vezes possível reconhecer uma semelhança entre a nova sequência e uma sequência sobre a qual jáexiste alguma informação

�As sequências semelhantes são designadas de sequências homólogas e a informação entre elas étransferida por homologia

�A semelhançaentresequênciaspode ter outrasutilidades:• Pesquisas em base de dados

• Comparação de genomas

• …

3/17/2005 8

�Uma sequência biológica éuma cadeia de caracteres escrita com um alfabeto de quatro letras (A,C,T,G)

�Comparar duas sequências biológicas éequivalente a comparar duas cadeias de caracteres

�É possível utilizar muitos dos métodosexistentes paracomparar cadeias de caracteres

5

3/17/2005 9

Distância de edição� Medida de semelhança/diferença entre duas cadeias de

caracteres� Obtida através da determinação da distância entre as duas

cadeias de caracteres

Definição: A distância de edição entre duas cadeias de caracteres édefinida como o número mínimo de operações de edição necessárias para transformar a primeira cadeia de caracteres na segunda. Notar que o emparelhamento de caracteres iguais não écontabilizado como uma operação de edição.

3/17/2005 10

�Duas das mais típicas distâncias de ediçãoutilizadas:• distância de edição de Levenshtein

– considera três operações de edição: a inserção, o apagamento e a substituição de um caractere

• distância de edição de Damerau– considera quatro operações de edição: a inserção, o

apagamento, a substituição e a transposição entre dois caracteres adjacentes

6

3/17/2005 11

Alinhamento de cadeias de caracteres

�Um alinhamento éuma forma de descrever uma relação entre duas cadeias de caracteres

�Indicase duassequênciasbiológicasestãoevolutivamente relacionadas ou não

�Duassequênciasbiológicas semelhantes ⇔ Duascadeias de caracteressemelhantes

�As sequências acumulam inserções, apagamentose substituições

�O conceito de alinhamento écrucial

3/17/2005 12

Alinhamento de cadeias de caracteres

Definição: Um alinhamento global de duas cadeias de caracteres S1 e S2 éobtido colocando inicialmente espaços nas extremidades ou no interior de S1 e S2. Posteriormente coloca-se as duas cadeias resultantes uma por cima da outra, fazendo corresponder a cada caractere ou espaço de uma cadeia apenas um caractere ou espaço da outra cadeia.

7

3/17/2005 13

Alinhamento de pares de sequências

�Exemplo:

• Qual éo melhor?

• Terásignificado biológico?

S1 = WEAGAWGHEES2 = PAWHEAE

WEAGAWGHE-E

P-A--W-HEAE

WEAGAWGHE-E

--P-AW-HEAE

desigualdade igualdade espaçamento

3/17/2005 14

Funções de mér ito

�No contexto da Bioinformática o objectivo éobter o alinhamento com mais significado biológico

�São várias as funções de mérito que podem ser utilizadas para medir a relevância biológica de um determinado alinhamento

�A função de mérito normalmente utilizada éuma função aditiva• implica que estáa ser assumido que as mutações nas

diferentes posições da sequência ocorrem de uma forma independente

8

3/17/2005 15

Função de mér ito aditiva

�O valor atribuído a cada alinhamento écalculado utilizando a seguinte expressão:

• sendo s(s1(i),s2(i)) o valor associado ao alinhamento dos caracteres i das sequências s1 e s2, e sendo G(g) o valor associado aos espaçamentos existentes

)())(,)(( 21 gGisissSi

+=�

3/17/2005 16

Função de mér ito aditiva

�Matriz de mérito. Especifica os valores s(s1(i),s2(i)) entre caracteres iguais e diferentes• Matrizes PAM e BLOSUM

– Caracterizam preferência evolutiva

�Função G. Pode apresentar diferentes níveis de complexidade• Função linear no tamanho do espaçamento

– Considera que todos os espaçamentos introduzidos são independentes e têm o mesmo valor

– Atribui um valor diferente a cada extensão do espaçamento

9

3/17/2005 17

Examplo:

W

P

H

E

A

WHGEA

15-3-3-3-3

-4-2-2-1-1

-310-20-2

-30-36-1

-3-20-15� ���������� ��

� ������� ��

WEAGAWGHE-E

P-A--W-HEAE

WEAGAWGHE-E

--P-AW-HEAE

(-8) + (-8) + (-1) + (-8) + 5 + 15 + (-8) + 10 + 6 + (-8) + 6 = 1���������� �����������

(-4) + (-8) + 5 + (-8) + (-8) + 15 + (-8) + 10 + 6 + (-8) + 6 = -2

3/17/2005 18

Modelo de mér ito

� O valor do alinhamento éa soma dos valorescorrespondentes a todos os caracteres alinhados, mais osvalores correspondentes aos espaçamentos

� Correspondeao logar itmo do cocienteda probabilidadedas sequências estarem relacionadas, com a probabilidadedas sequências não estarem relacionadas

� Espera-se quezonas conservadas sejam mais prováveisnum alinhamento do queobtidas por acaso• Contribuem com termospositivos

� Zonas não conservadas são menos frequêntes emalinhamentos reais do quese fossem obtidas ao acaso• Contribuem com termosnegativos

10

3/17/2005 19

A R N D C Q E G H I L K M F P S T W Y VA R N D C Q E G H I L K M F P S T W Y VA 5 -2 -1 -2 -1 -1 -1 0 -2 -1 -2 -1 -1 -3 -1 1 0 -3 -2 0R -2 7 -1 -2 -4 1 0 -3 0 -4 -3 3 -2 -3 -3 -1 -1 -3 -1 -3N -1 -1 7 2 -2 0 0 0 1 -3 -4 0 -2 -4 -2 1 0 -4 -2 -3D -2 -2 2 8 -4 0 2 -1 -1 -4 -4 -1 -4 -5 -1 0 -1 -5 -3 -4C -1 -4 -2 -4 13 -3 -3 -3 -3 -2 -2 -3 -2 -2 -4 -1 -1 -5 -3 -1Q -1 1 0 0 -3 7 2 -2 1 -3 -2 2 0 -4 -1 0 -1 -1 -1 -3E -1 0 0 2 -3 2 6 -3 0 -4 -3 1 -2 -3 -1 -1 -1 -3 -2 -3G 0 -3 0 -1 -3 -2 -3 8 -2 -4 -4 -2 -3 -4 -2 0 -2 -3 -3 -4H -2 0 1 -1 -3 1 0 -2 10 -4 -3 0 -1 -1 -2 -1 -2 -3 2 -4I -1 -4 -3 -4 -2 -3 -4 -4 -4 5 2 -3 2 0 -3 -3 -1 -3 -1 4L -2 -3 -4 -4 -2 -2 -3 -4 -3 2 5 -3 3 1 -4 -3 -1 -2 -1 1K -1 3 0 -1 -3 2 1 -2 0 -3 -3 6 -2 -4 -1 0 -1 -3 -2 -3M -1 -2 -2 -4 -2 0 -2 -3 -1 2 3 -2 7 0 -3 -2 -1 -1 0 1F -3 -3 -4 -5 -2 -4 -3 -4 -1 0 1 -4 0 8 -4 -3 -2 1 4 -1P -1 -3 -2 -1 -4 -1 -1 -2 -2 -3 -4 -1 -3 -4 10 -1 -1 -4 -3 -3S 1 -1 1 0 -1 0 -1 0 -1 -3 -3 0 -2 -3 -1 5 2 -4 -2 -2T 0 -1 0 -1 -1 -1 -1 -2 -2 -1 -1 -1 -1 -2 -1 2 5 -3 -2 0W -3 -3 -4 -5 -5 -1 -3 -3 -3 -3 -2 -3 -1 1 -4 -4 -3 15 2 -3Y -2 -1 -2 -3 -3 -1 -2 -3 2 -1 -1 -2 0 4 -3 -2 -2 2 8 -1V 0 -3 -3 -4 -1 -3 -3 -4 -4 4 1 -3 1 -1 -3 -2 0 -3 -1 5

AminoAminoáácidoscidosMatr izMatr iz de de mméér itor ito ouou substituisubstituiççãoão

3/17/2005 20

� Um biólogo com uma grande intuição para proteínas poderia sugerir, com realismo, um conjunto de 210 valores, correspondentes a todos os possíveis alinhamentos entre pares de aminoácidos

Ile (I) Leu (L) Met (M) Val (V)Hydrophobic

Ala (A) Cys (C) Gly (G) Pro (P) Ser (S) Thr(T)Hydrophilic

Phe (F) Tyr (Y) Trp (W)Aromatic

His (H) Lys (K) Arg (R)Basic

Asp (D) Glu(E) Asn (N) Gln (Q)Acids and Amides

Amino AcidAmino AcidCategoryCategory

Mas ser ia Mas ser ia úútil ter alguma til ter alguma teor ia que justificasse os teor ia que justificasse os valores da matr izvalores da matr iz

11

3/17/2005 21

� A probabilidade do aminoácido Ser(S) sofrer uma mutação para Phe(F) é3X maior que a probabilidade de Trp(W) sofrer uma mutação para Phe(F)

� A probabilidade de Ser(S) sofrer uma mutação para Phe(F) em proteinas que divergiram há15 milhões de anos émenor do que a probabilidade desta mutação em proteinas que divergiram há80 milhões de anos

Ile (I) Leu (L) Met (M) Val (V)Hydrophobic

Ala (A) Cys (C) Gly (G) Pro (P) Ser (S) Thr(T)Hydrophilic

Phe (F) Tyr (Y) Trp (W)Aromatic

His (H) Lys (K) Arg (R)Basic

Asp (D) Glu(E) Asn (N) Gln (Q)Acids and Amides

Amino AcidAmino AcidCategoryCategory

3/17/2005 22

Modelo Probabilístico�Formalismo

• Sequências: x(n), y(m)– xi éo símbolo i de x– yj éo símbolo j de y

• Alfabeto A (símbolos idêntificados por a, b)– DNA, { A,G,C,T}– proteinas, os 20 aminoácidos

�Considere-se duas sequências de igualtamanho e totalmentealinhadas

12

3/17/2005 23

�Modelo aleatório, R :

• Assume queo símbolo a ocorrede uma forma independentecom umaprobabilidadeqa

• A probabilidadedas duassequências éapenas o produto das probabilidades de cadasímbolo

∏∏=j

yi

x jiqqRyxP )|,(

3/17/2005 24

�Modelo relacionado, M:• Assume queos pares de símbolos alinhados

ocorrem com uma probabilidade conjuntapab

• Esta probabilidade pode ser vista como a probabilidade dos símbolos a e b terem sido gerados de uma forma independente a partir do mesmo símbolo original c

∏=i

yx iipMyxP )|,(

13

3/17/2005 25

�Odds ratio:

�Modelo de custo aditivo, Log-odds ratio:

•O valor s(a,b) obido para cada par de símbolos dáuma indicação sobre a importância desse par ocorrer alinhado relativamente a ocorrer desalinhado•Estes valores são normalmente apresentados em forma de matriz, designada de matriz de mérito ou substituição

∏∏ ∏∏ ==

i yx

yx

i i yx

i yx

ii

ii

ii

ii

qq

p

qq

p

RyxP

MyxP

)|,(

)|,(

���

����

�==�

ba

abi

ii qq

pbaswhereyxsS log),(),(

3/17/2005 26

Espaçamentos�Os espaçamentos são normalmente penalizados�Custo associado a um espaçamento de tamanho g:

•Função linear simples

•Função mais sofisticada

sendo g o tamanho do espaçamento, d o valor de cada alinhamento com um espaçamento e eo valor atribuido a cada extensão do espaçamento

gdg −=)(γ

egdg )1()( −−−=γ

14

3/17/2005 27

Affine Gap Penalties

�Na natureza, muitas vezes os espaçamentossurgem em conjuntos e não apenas paraum nucleótido isolado

Com uma função de custosimples obtem-se o mesmo valor para estesalinhamentos

Na natureza estasituação é maisprovável

3/17/2005 28

Modelo Probabilístico

• A função f(g) éuma distribuição de probabilidade

• Este produto assume que o tamanho do espaçamento éindependente do seu conteúdo

Log-odds ratio:

∏=gapini

xiqgfgapP )()(

))((log)( gfg =γ

15

3/17/2005 29

Como estimar estas probabilidades?

�Abordagem simples (maximum likelihood):• Conta a frequência dos pares alinhados e dos

espaçamentos em alinhamentos confirmados

• As probabilidades pab, qa e f(g) são normalizadas

Dificuldades• Obter uma boa amostra aleatória de alinhamentos

confirmados

• Obter valores a partir de alinhamentos que correspondam àdivergência esperada para as sequências que vão ser alinhadas

3/17/2005 30

Matr izes de mér ito paraproteínas

�Família de matrizes quecontêm a probabilidadede uma sequênciase tertransormado noutraduranteo processoevolutivo

�As duas famílias mais conhecidas são as matrizes PAM (Point Accepted Mutation) e as matrizes BLOSUM (BLOcks Substitution Matrix)

16

3/17/2005 31

Matr izes PAM(Dayhoff, 1978)

�Primeiras matrizes de substituição de aminoácidos, utilizadas nos alinhamentos efectuados na pesquisa de sequências homologas em base de dados biológicas

�A escolha da matriz de substituição influência fortemente o resultado dos alinhamentos

�A matriz de substituição deve reflectir o fenómeno biológico que um alinhamento procura mostrar

3/17/2005 32

Matr izes PAM

�A construção destasmatrizes baseou-se naobtenção de dados sobreas substituiçõesocorridasem alinhamentos de proteínas muito semelhantes

�Permiteobter relações evolutivas paraproteínas damesma famíliae permiteaindaa extrapolaçãodesta informação paraoutrasdistânciasevolutivas

�Iniciou-se com a construção de árvoresfilogenéticashipotéticas, relacionando sequênciasde 71 familias, ondecadapar de sequênciasdiferiam em não mais de 15%

17

3/17/2005 33

Matr izes PAM�O termo PAM tem 2 utilizações distintas mas

relacionadas:• Unidadede medidade distânciaevolutiva• Referência de uma determinada matriz de substituição de

aminoácidos

Definição: Duas sequências S1 e S2 dizem-se a uma distância evolutiva de 1PAM se uma série de mutações pontuais “aceites” ( não são consideradas inserções nem apagamentos) levaram àconversão de S1 em S2 com uma média de uma mutação “aceite”em cada 100 aminoácidos

3/17/2005 34

Matr izes PAM�A matriz PAM 1 édefinidaa partir de muitos

alinhamentosde proteinas extremamentesemelhantes.

�A partir de um conjunto de alinhamentos:• f(i,j) – número de vezes queo aminoácido i estáalinhado

com o aminoácido j, dividindo pelo número de posiçõesalinhadas

• g(i,j) = f(i,j)/f(i) , f(i) é a frequência do aminoácido i emtodas as proteinas do conjunto de dados

• g(i,j) define a probabilidadedo aminoácido i se transformar no aminoácido j dentro de umadistânciaevolutivade 1 PAM

18

3/17/2005 35

Matr izes PAM

�Matriz PAM 1:• Cadaposição (i,j) damatriz édefinidapor

– (i,j) = log f(i,j)/f(i).f(j)= log g(i,j)/f(j)

• f(i).f(j), correspondeà frequênciacom queo aminoácido i éalinhado com o aminoácido j apenaspor acaso (modelo aleatório)

�A matrix PAM n é obtidaa partir damultiplicação da matrix PAM 1 n vezes

3/17/2005 36

Matr izes PAM

�Duas sequências de proteinas distanciadas de 1PAM podem apresentar uma diferença inferior a 1 % entre os aminoácidos que as constituem

�Duas sequências que estão distânciadas de 100PAM não são diferentes em todas as suas posições

�Normalmente sequências que divergentes de 200PAM ainda são idênticas em 25% das suas posições

� Duas sequências distânciadas de 250PAM ainda são distinguíveis de um par de sequências geradas aleatóriamente.

19

3/17/2005 37

PAM matr ices

8025070159601205080405630382023101111

Diferençasobservadas (%)

Distânciaevolutiva(PAM)

250 80

MaisMais utilizadautilizadaPAM 250PAM 250

3/17/2005 38

20

3/17/2005 39

BLOSUM(Henikoff, 1992)

�Estas matrizes foram obtidas utilizando, nasuaessência, o modelo probabilístico descritoanteriormente

�Foram obtidas a partir de um enormevolume de dados pertencentes àbase de dados, BLOCKS, de famílias de proteínas

�As sequências foram agrupadas semprequea percentagem de caracteres idênticos excedesseum determinado nível L

�BLOSUM50 e BLOSUM62 são as mais utilizadas

3/17/2005 40

A R N D C Q E G H I L K M F P S T W Y VA 5 - 2 - 1 - 2 - 1 - 1 - 1 0 - 2 - 1 - 2 - 1 - 1 - 3 - 1 1 0 - 3 - 2 0R - 2 7 - 1 - 2 - 4 1 0 - 3 0 - 4 - 3 3 - 2 - 3 - 3 - 1 - 1 - 3 - 1 - 3N - 1 - 1 7 2 - 2 0 0 0 1 - 3 - 4 0 - 2 - 4 - 2 1 0 - 4 - 2 - 3D - 2 - 2 2 8 - 4 0 2 - 1 - 1 - 4 - 4 - 1 - 4 - 5 - 1 0 - 1 - 5 - 3 - 4C - 1 - 4 - 2 - 4 13 - 3 - 3 - 3 - 3 - 2 - 2 - 3 - 2 - 2 - 4 - 1 - 1 - 5 - 3 - 1Q - 1 1 0 0 - 3 7 2 - 2 1 - 3 - 2 2 0 - 4 - 1 0 - 1 - 1 - 1 - 3E - 1 0 0 2 - 3 2 6 - 3 0 - 4 - 3 1 - 2 - 3 - 1 - 1 - 1 - 3 - 2 - 3G 0 - 3 0 - 1 - 3 - 2 - 3 8 - 2 - 4 - 4 - 2 - 3 - 4 - 2 0 - 2 - 3 - 3 - 4H - 2 0 1 - 1 - 3 1 0 - 2 10 - 4 - 3 0 - 1 - 1 - 2 - 1 - 2 - 3 2 - 4I - 1 - 4 - 3 - 4 - 2 - 3 - 4 - 4 - 4 5 2 - 3 2 0 - 3 - 3 - 1 - 3 - 1 4L - 2 - 3 - 4 - 4 - 2 - 2 - 3 - 4 - 3 2 5 - 3 3 1 - 4 - 3 - 1 - 2 - 1 1K - 1 3 0 - 1 - 3 2 1 - 2 0 - 3 - 3 6 - 2 - 4 - 1 0 - 1 - 3 - 2 - 3M - 1 - 2 - 2 - 4 - 2 0 - 2 - 3 - 1 2 3 - 2 7 0 - 3 - 2 - 1 - 1 0 1F - 3 - 3 - 4 - 5 - 2 - 4 - 3 - 4 - 1 0 1 - 4 0 8 - 4 - 3 - 2 1 4 - 1P - 1 - 3 - 2 - 1 - 4 - 1 - 1 - 2 - 2 - 3 - 4 - 1 - 3 - 4 10 - 1 - 1 - 4 - 3 - 3S 1 - 1 1 0 - 1 0 - 1 0 - 1 - 3 - 3 0 - 2 - 3 - 1 5 2 - 4 - 2 - 2T 0 - 1 0 - 1 - 1 - 1 - 1 - 2 - 2 - 1 - 1 - 1 - 1 - 2 - 1 2 5 - 3 - 2 0W - 3 - 3 - 4 - 5 - 5 - 1 - 3 - 3 - 3 - 3 - 2 - 3 - 1 1 - 4 - 4 - 3 15 2 - 3Y - 2 - 1 - 2 - 3 - 3 - 1 - 2 - 3 2 - 1 - 1 - 2 0 4 - 3 - 2 - 2 2 8 - 1V 0 - 3 - 3 - 4 - 1 - 3 - 3 - 4 - 4 4 1 - 3 1 - 1 - 3 - 2 0 - 3 - 1 5

��������

21

3/17/2005 41

PAM vs. BLOSUM� O modelo PAM tem a capacidadede evidênciar a origem

evolutivade proteínas

� O modelo Blosum tem a capacidadede evidênciar domíniosconservados em proteínas

Regras práticas

• Baixas PAMs e elevadas Blosums encontram pequenosalinhamentos locais com elevadasemelhança

• Elevadas PAMs e baixas Blosums encontram alinhamentoslocais mais fracos mas longos

3/17/2005 42

22

3/17/2005 43

Algor itmos de alinhamentoQuais as dificuldades?

�Considereduas sequências de tamanho nPergunta:

• Quantos possíveis alinhamentos existem entre as duas cadeias de caracteres?

Resposta:• Se não for permitido espaçamentos, então existe apenas

um alinhamento possível• Se forem permitidos espaçamentos, énecessário

enumerar todos os alinhamentos entre todas as sub-sequências das duas cadeias de caracteres

3/17/2005 44

Algor itmos de alinhamentoQuais as dificuldades?

�Existem

possíveis alinhamentos globais

�Pretende-se obter o melhor de todos

nn

n

n

n n

π

2

2

2

)!(

)!2(2≈=��

�

����

�

23

3/17/2005 45

Então?

� Para n = 20, temos cercade 120 biliões de alinhamentos possíveis

� Na práticapretendemosalinhar sequências muito, mas muito mais longas• Algumasproteínas têm

maisde 1000 aminoácidos

• Os genes podem ter váriosmilharesde pares de bases

3/17/2005 46

Alinhamento Global vs. Local

24

3/17/2005 47

�� ALINHAMENTO GLOBALALINHAMENTO GLOBAL• Comparaduas sequências em todaa suaextensão• É apropriado paracomparar sequências cujas

semelhanças sejam esperadas em todaa suaextensão• O alinhamento maximizaas regiões de semelhançae

minimizaos espaçamentos

�� ALINHAMENTO LOCALALINHAMENTO LOCAL• Procura locais de semelhançaentre as sequências sem

ter de considerar todo o comprimento destas• É muito útil para fazer pesquisas em base de dados• É muito útil em situações ondenão existequalquer

conhecimento sobrea semelhançaentreas sequências a comparar

3/17/2005 48

ALINHAMENTO GLOBAL versus LOCALALINHAMENTO GLOBAL versus LOCAL

�Alinhamento Global

�Alinhamento Local

- - T—- CC- C- AGT—- TATGT- CAGGGGACACG—A- GCATGCAGA- GAC| | | | | | | | | | | | | | | | | | | | | | |

AATTGCCGCC- GTCGT- T- TTCAG- - - - CA- GTTATG—T- CAGAT- - C

t ccCAGTTATGTCAGgggacacgagcat gcagagac| | | | | | | | | | | |

aat t gccgccgt cgt t t t cagCAGTTATGTCAGat c

25

3/17/2005 49

Programação Dinâmica (DP): algor itmo quepermiteobter alinhamentosóptimos utilizando funções de mér itoaditivas

�Estes algoritmos garantem como solução o melhor alinhamento ou melhor conjunto de alinhamentos

�Os algoritmos mais simples são os algoritmosparaalinhamento de pares de sequências

3/17/2005 50

Programação Dinâmica

SequênciaB

SequênciaAMelhor alinhamento anterior

Novo melhor alinhamento = melhor anterior + melhor local

... ... ... ...

26

3/17/2005 51

Descr ição Formal

�Problema: Alinhamento_par_sequencia�Entrada: Duas sequências x,y

Matriz de mérito s(x,y)

Valor do espaçamento d

�Saída: O melhor alinhamento

3/17/2005 52

EXEMPLO: Duas sequências de aminoácidosx: HEAGAWGHEEy: PAWHEAEd = 8s(xi,yj) = BLOSUM50

-3-3-160E

-3-2-2010H

15-3-3-3-3W

-305-1-2A

-4-2-1-1-2P

WGAEH

27

3/17/2005 53

Alinhamento Global: Algor itmoNeedleman-Wunsh (1970)

�Ideia: Construir um alinhamento óptimo utilizandosoluções óptimas obtidas anteriormenteparasub-sequências mais pequenas

• Constroi umamatriz F com indices i e j , um paracadasequência

• O valor F(i,j ) representa o melhor obtido pela funçãode mérito parao alinhamento de x1...i com y1...j

• Constroi F(i,j ) de uma forma recursiva

3/17/2005 54

E

A

E

H

XW

A

P

EEHGWAGAEHF matrix

i

j

Three ways to obtain the best score F(i,j)

• xi is aligned to yj

• xi is aligned to a gap• yj is aligned to a gap

HEA xHEA xii--PA PA yyjj

),()1,1(),( ji yxsjiFjiF +−−=

HEA xHEA xii--PA PA --

djiFjiF −−= ),1(),(

HEA HEA ----PA PA yyjj

djiFjiF −−= )1,(),(

28

3/17/2005 55

F(i,j)F(i-1,j)

F(i,j-1)F(i-1,j-1)

s(xi,yj)

-d

-d

� While building the table, keep track of where optimal score came from

� Initialize: F(0,0) = 0, F(i,0) = -id, F(0,j)=-jd� Fill from top left to bottom right using the recursive relation

�

�

�

−−−−

+−−=

djiF

djiF

yxsjiF

jiFji

)1,(

),1(

),()1,1(

max),(

3/17/2005 56

Example:

-56EE

-48AA

-40EE

-32HH

-24WW

-16AA

-73-65-57-49-42-33-25-17-9-2-8PP

-80-72-64-56-48-40-32-24-16-80

EEEEHHGGWWAAGGAAEEHH

29

3/17/2005 57

Example:

1-9-12-15-14-12-6-11-24-38-56EE

2-5-15-12-12-11-11-3-16-30-48AA

-53-7-15-12-9-16-16-8-22-40EE

-19-11-3-7-13-9-8-13-18-14-32HH

-37-29-21-13-5-15-7-6-11-18-24WW

-60-52-44-36-28-20-12-4-3-10-16AA

-73-65-57-49-42-33-25-17-9-2-8PP

-80-72-64-56-48-40-32-24-16-80

EEEEHHGGWWAAGGAAEEHH

F(n,m) is the bestscore for the alignment

3/17/2005 58

1-9-12-15-14-12-6-11-24-38-56EE

2-5-15-12-12-11-11-3-16-30-48AA

-53-7-15-12-9-16-16-8-22-40EE

-19-11-3-7-13-9-8-13-18-14-32HH

-37-29-21-13-5-15-7-6-11-18-24WW

-60-52-44-36-28-20-12-4-3-10-16AA

-73-65-57-49-42-33-25-17-9-2-8PP

-80-72-64-56-48-40-32-24-16-80

EEEEHHGGWWAAGGAAEEHH

Trace arrows back from the lower right to top left• Diagonal – both• Up – upper gap • Left – lower gap

HEAGAWGHEHEAGAWGHE--EE----PP--AWAW--HEAEHEAE

30

3/17/2005 59

Algor ithm complexity

�Stores (n+1) x (m+1) numbers�Each number costs a constant number of

calculations: 3 sums and a max�Big-O notation:

• O(nm) time and memory, n and m are the length of the sequences

• O(n2) algorithm• feasible for moderate sized sequences, but not

for aligning whole genomes.

3/17/2005 60

Algor ithm complexity�Example 1:

• S1: size 103

• S2: size 103

• Algorithm O(nm)• Machine: 1GHz and 1Gb RAM (109 steps/second)• Time: 1ms

� Example 2:• S1: size 109

• S2: size 109

• Algorithm O(nm)• Machine: 1GHz and 1Gb RAM (109 steps/second)• Time: 109s => 30 anos

O(n logm)

9s108s => 3 anos

1010s/s

31

3/17/2005 61

Local alignment

Global alignment

Local alignment

Compute a “mini”Global Alignment to get Local

3/17/2005 62

Local alignment�Is closely related to global alignment�Two differences:

• F(i,j) takes the value 0 if all other options have value less than 0

– Corresponds to starting a new alignment– Top row and left column will be filled with 0s

• An alignment can end anywhere in the matrix– Look for the highest value of F(i,j) over the whole

matrix– Start the traceback from there

32

3/17/2005 63

�Another dynamic programming solution

���

���

�

−−−−

+−−=

djiF

djiFyxsjiF

jiFji

)1,(

),1(),()1,1(

0

max),(

Local alignment: Smith-Waterman algor ithm (1981)

3/17/2005 64

2616404121813600EE

2720104051321800AA

2028181040081620EE

6142218120002100HH

0041220020000WW

00000505000AA

00000000000PP

00000000000

EEEEHHGGWWAAGGAAEEHH

Start at highest score and traceback to first 0

AWGHEAWGHEAWAW--HEHE

33

3/17/2005 65

Notes

�For this algorithm to work, the expected score for a random match must be negative• behavior is like global alignment otherwise

�Similarly, there must be some s(a,b) greater than 0

�Care must be given to gap penalties to maintain O(nm) time complexity

3/17/2005 66

Repeated matches

�For long sequences it is possible that there are many different local alignments with a significant score• example: many copies of a repeated domain or motif in

a protein

�This asymmetric method finds one or more non-overlapping copies of sections of one sequence in the other

34

3/17/2005 67

Repeated matches

�Consider only matches with score higher than some threshold T

�In the final, x will be partitioned into regions that match parts of y in gapped alignments and regions that are unmatched

�The score of a completed match region is its standard gapped alignment score minus the threshold T

�All the match scores are positive

3/17/2005 68

Repeated matches

�Initial conditions: F(0,0) = 0

�

=−−−

=mjTjiF

iFiF

,...,1),1(

)0,1(max)0,(

���

���

�

−−−−

+−−=

djiF

djiFyxsjiF

iF

jiFji

)1,(

),1(),()1,1(

)0,(

max),(

35

3/17/2005 69

2717514121813600EE

2821115161321800AA

2129191151181620EE

9152319131102100HH

9351321120000WW

93111615000AA

93111110000PP

93111110000

EEEEHHGGWWAAGGAAEEHH

9

(n+1,0)

T = 20The optimal alignment with total score 9 = 29 – 20There are two separate match regions with scores 1 and 8

HEA.AWHEA.AW--HE.HE.

3/17/2005 70

�Matching when the two sequences overlap or one sequence contains the other• when comparing fragments of genomic DNA sequence

to each other or to larger chromosomal sequences

�Is a type of global alignment but it does not penalize overhanging ends

Over lap matches

�

�

�

�

�

�

�

�

36

3/17/2005 71

Heuristic alignment algorithms

�The dynamic programming algorithms described have been ‘correct’• they are guaranteed to find the optimal score

according to the specified scoring scheme

�They are not the fastest available sequence alignment methods• current protein database: 100 million residues• sequence of length 1000 => 1011 matrix cells• 106 matrix cells a second => 3 hours

3/17/2005 72

Heuristic algorithms

�Heuristic approaches sacrifice some sensitivity• they can miss the best scoring alignment• approximate local alignment

�Best-known algorithms:• BLAST (Basic Local Alignment Search Tool)• FASTA (FAST All) (read “fast_AY”)

37

3/17/2005 73

Heuristic algorithms�These programs are actually suites of programs

containing tuned variants for use in different problem domains:• Searching DNA• Searching protein• Searching database• Aligning two strings

�They do not permit precise analyses of their speed or accuracy

3/17/2005 74

FASTA(Pearson & Lipman 1988)

�Uses a multistep approach to find local high scoring alignments• First:

– The user selects a value for a parameter called ktup– Identifies ktup-length “hot-spots” in the dynamic

programming table» Finds pairs (i,j) such that the ktup-length substring (k-tuple)

starting at position i in the query string exactly matches the k-tuple starting at position j in the text (hash table)

» Such a pair is called a “hot-spot”

» ktup = 1 or 2 for proteins, 4 or 6 for DNA

38

3/17/2005 75

FASTA

• Second:– Each “hot-spot” (i,j) is a ktup-length interval in

diagonal (i-j) of the full dynamic programming table

– FASTA locates the ten best diagonal runs

– A diagonal run is a sequence of consecutive hot-spotsin a single diagonal

• Third:– Evaluation

» Each hot-spot has a positive score

» The space between consecutive hot-spotshas a negative score

» The score of a diagonal run is the sum

3/17/2005 76

Example:

EE

AA

EE

HH

WW

AA

PP

EEEEHHGGWWAAGGAAEEHH

39

3/17/2005 77

FASTA

�Each of the ten diagonal runs selected, specifies a pair of aligned substrings• Matches (from the hot-spots)

• Mismatches (from the interspot regions)

• Does not contain spaces

�Determine score using BLOSUM50

�Combine “good” subalignments allowing spaces

�Realignment using the Smith-Waterman algorithm• Compute the optimal local alignment

3/17/2005 78

BLAST(Altschul et al, 1990)

�Provides programs for finding high scoring local alignments between a query sequence and a target database (DNA or protein)

�Idea: True alignments will have a short stretch of identities (perfect match), or very high scoring matches• Look initially for such short stretches and use

them as ‘seeds’

40

3/17/2005 79

BLAST

�Became the dominant searching engine for biological sequences databases• Outputs a range of solutions

• Each match is accompanied by an estimate of statistical significance

�Fundamental objects• Segment pairs

• Locally maximal segment pairs

• Maximal segment pairs

3/17/2005 80

BLAST

�Definition: • Given two strings S1 e S2,

– a segment pair is a pair of equal-length substrings of S1 and S2, aligned without spaces

– a locally maximal segment pair is a segment pair whose alignmentscore (without spaces) would fall either by expanding or shortening the segments on either side

– a maximal segment pair (MSP) in S1, S2 is a segment pair with the maximum score over all segment pairs in S1, S2

�For a fixed query sequence P, find all those database sequences that, together with P, contain a MSP above some set cutoff score C

41

3/17/2005 81

BLAST

�Strategy:• With a fixed length w and a fixed threshold t, find all

length-w substrings of S that align to some length-wsubstring of P with an alignment score above t

• Each hit is extended to see if it is contained in a segment pair with score above C

• Does not use dynamic programming to extentions, because it disallows spaces in the alignments

�Length-W substrings• Proteins, 3 to 5

• DNA, around 12

3/17/2005 82

BLAST

Query: 22 VLRDNIQGITKPAIRRLARRGGVKRISGLIYEETRGVLK 60+++DN +G + IR L G+K I+ L+ E+ RG++K

Sbjct: 226 IIKDNGRGFSGKQIRNLNYGIGLKVIADLV-EKHRGIIK 263

Query: KRHRKVLRDNIQGITKPAIRRLARRGGVKRISGLIYEETRGVLKIFLENVIRD

Length-W

GVK 18GAK 16GIK 16GGK 14GLK 13GNK 12GRK 11GEK 11GDK 11

neighborhoodscore threshold

(T = 13)

Neighborhoodwords

High-scoring Pair (HSP)

extension

42

3/17/2005 83

• w = 4, T = 4• Exact keyword

match of ����������������

• Extend diagonals with mismatches until score is under T

• Output result������������������������������������

������������������������������������

Original BLAST: ExampleA C G A A G T A A G G T C C A G T

C

T

G

A

T

C C

T

G

G

A

T

T

G C

G

A

From lectures by Serafim Batzoglou(Stanford)

3/17/2005 84

Gapped BLAST: ExampleA C G A A G T A A G G T C C A G T

C

T

G

A

T

C C

T

G

G

A

T

T

G C

G

A� Original BLAST exact

keyword search, THEN:

� Extend with gaps in a zone around ends of exact match

� Output result

• GTAAGGTCCAGT

• GTTAGGTC-AGT

From lectures by Serafim Batzoglou(Stanford)

43

3/17/2005 85

BLAST

�The effectiveness of BLAST• In generally, BLAST is competitive with FASTA

• BLAST is less effective when the most biologically significant alignments contain spaces

• A Smith-Waterman alignment should always be used when BLASTP matches are displayed

�New version: PSI-BLAST

3/17/2005 86

Real Sequence Database Search�New protein sequence is determined

• First (search well-characterized sequence motifs):– Compare with the PROSITE database

– Compare with the BLOCKS database

• Second (search for sequences highly similar):

– Search the DNA and protein sequence databases

» Genbank

» Swiss-Prot …

– Usually a local similarity

– Approximate methods, BLAST and FASTA

• Last, if needed:– Compute optimal similarity based on dynamic programming

– Try some variant of a PAM matrix and of a BLOSUM matrix