Alinhamento Simples

Métodos para alinhamento de
pares de sequências
Ana Teresa Freitas
3/17/2005
1
Índice
Alinhamento de sequências
•
•
•
•
•
•
•
•
3/17/2005
Introdução
Distância de edição
Alinhamento de cadeias de caracteres
Funções de mérito
Matrizes de substituição
Alinhamento global
Alinhamento local
Heuristicas para alinhamento
2
1
Introdução
Avanços na área da biologia molécular permitem
um rápido aumento do número de genomas
sequenciados
Crescimento exponencial
do Genbank
A comunidade científica
passou a dar maior ênfase
à transformação da
grande quantidade de
dados existentes em
conhecimento
3/17/2005
3
Taxas de crescimento
3/17/2005
4
2
Que sentido dar a estes dados?
3/17/2005
5
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 proferida por Eric 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 proferida por Francois Jacob em 1977:
“Nature is a tinkerer and not an inventor”[Evolution and tinkering, science
196:1161-1166]
3/17/2005
6
3
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ça entre sequências pode ter outras
utilidades:
• Pesquisas em base de dados
• Comparação de genomas
• …
3/17/2005
7
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étodos
existentes para comparar cadeias de caracteres
3/17/2005
8
4
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
9
Duas das mais típicas distâncias de edição
utilizadas:
• 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
3/17/2005
10
5
Alinhamento de cadeias de caracteres
Um alinhamento é uma forma de descrever uma
relação entre duas cadeias de caracteres
Indica se duas sequências biológicas estão
evolutivamente relacionadas ou não
Duas sequências biológicas semelhantes ⇔ Duas
cadeias de caracteres semelhantes
As sequências acumulam inserções, apagamentos
e substituições
O conceito de alinhamento é crucial
3/17/2005
11
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.
3/17/2005
12
6
Alinhamento de pares de sequências
Exemplo:
S1 = WEAGAWGHEE
S2 = PAWHEAE
WEAGAWGHE-E
WEAGAWGHE-E
P-A--W-HEAE
--P-AW-HEAE
desigualdade
igualdade
espaçamento
• Qual é o melhor?
• Terá significado biológico?
3/17/2005
13
Funções de mérito
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
3/17/2005
14
7
Função de mérito aditiva
O valor atribuído a cada alinhamento é
calculado utilizando a seguinte expressão:
S=
s ( s1 (i ), s2 (i )) + G ( g )
i
• 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
3/17/2005
15
Função de mérito 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
3/17/2005
16
8
Examplo:
A
E
G
H
W
5
-1
0
-2
-3
E
-1
6
-3
0
-3
H
-2
0
-2
10
-3
P
-1
-1
-2
-2
-4
W
-3
-3
-3
-3
15
A
WEAGAWGHE-E
--P-AW-HEAE
(-8) + (-8) + (-1) + (-8) + 5 + 15
+ (-8) + 10 + 6 + (-8) + 6 = 1
WEAGAWGHE-E
P-A--W-HEAE
(-4) + (-8) + 5 + (-8) + (-8) + 15
+ (-8) + 10 + 6 + (-8) + 6 = -2
3/17/2005
17
Modelo de mérito
O valor do alinhamento é a soma dos valores
correspondentes a todos os caracteres alinhados, mais os
valores correspondentes aos espaçamentos
Corresponde ao logaritmo do cociente da probabilidade
das sequências estarem relacionadas, com a
probabilidade das sequências não estarem relacionadas
Espera-se que zonas conservadas sejam mais prováveis
num alinhamento do que obtidas por acaso
• Contribuem com termos positivos
Zonas não conservadas são menos frequêntes em
alinhamentos reais do que se fossem obtidas ao acaso
• Contribuem com termos negativos
3/17/2005
18
9
Matriz de mérito ou substituiç
substituição
A
R
N
D
C
Q
E
G
H
I
L
K
M
F
P
S
T
W
Y
V
A
5
-2
-1
-2
-1
-1
-1
0
-2
-1
-2
-1
-1
-3
-1
1
0
-3
-2
0
R
-2
7
-1
-2
-4
1
0
-3
0
-4
-3
3
-2
-3
-3
-1
-1
-3
-1
-3
N
-1
-1
7
2
-2
0
0
0
1
-3
-4
0
-2
-4
-2
1
0
-4
-2
-3
D
-2
-2
2
8
-4
0
2
-1
-1
-4
-4
-1
-4
-5
-1
0
-1
-5
-3
-4
C
-1
-4
-2
-4
13
-3
-3
-3
-3
-2
-2
-3
-2
-2
-4
-1
-1
-5
-3
-1
Q
-1
1
0
0
-3
7
2
-2
1
-3
-2
2
0
-4
-1
0
-1
-1
-1
-3
E
-1
0
0
2
-3
2
6
-3
0
-4
-3
1
-2
-3
-1
-1
-1
-3
-2
-3
G
0
-3
0
-1
-3
-2
-3
8
-2
-4
-4
-2
-3
-4
-2
0
-2
-3
-3
-4
H
-2
0
1
-1
-3
1
0
-2
10
-4
-3
0
-1
-1
-2
-1
-2
-3
2
-4
I
-1
-4
-3
-4
-2
-3
-4
-4
-4
5
2
-3
2
0
-3
-3
-1
-3
-1
4
Aminoá
Aminoácidos
L
-2
-3
-4
-4
-2
-2
-3
-4
-3
2
5
-3
3
1
-4
-3
-1
-2
-1
1
K
-1
3
0
-1
-3
2
1
-2
0
-3
-3
6
-2
-4
-1
0
-1
-3
-2
-3
M
-1
-2
-2
-4
-2
0
-2
-3
-1
2
3
-2
7
0
-3
-2
-1
-1
0
1
F
-3
-3
-4
-5
-2
-4
-3
-4
-1
0
1
-4
0
8
-4
-3
-2
1
4
-1
P
-1
-3
-2
-1
-4
-1
-1
-2
-2
-3
-4
-1
-3
-4
10
-1
-1
-4
-3
-3
S
1
-1
1
0
-1
0
-1
0
-1
-3
-3
0
-2
-3
-1
5
2
-4
-2
-2
3/17/2005
T
0
-1
0
-1
-1
-1
-1
-2
-2
-1
-1
-1
-1
-2
-1
2
5
-3
-2
0
W
-3
-3
-4
-5
-5
-1
-3
-3
-3
-3
-2
-3
-1
1
-4
-4
-3
15
2
-3
Y
-2
-1
-2
-3
-3
-1
-2
-3
2
-1
-1
-2
0
4
-3
-2
-2
2
8
-1
V
0
-3
-3
-4
-1
-3
-3
-4
-4
4
1
-3
1
-1
-3
-2
0
-3
-1
5
19
Category
Acids and Amides
Basic
Aromatic
Hydrophilic
Amino Acid
Asp (D) Glu(E) Asn (N) Gln (Q)
His (H) Lys (K) Arg (R)
Phe (F) Tyr (Y) Trp (W)
Ala (A) Cys (C) Gly (G) Pro (P) Ser (S) Thr(T)
Hydrophobic
Ile (I) Leu (L) Met (M) Val (V)
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
3/17/2005
Mas seria útil ter alguma
teoria que justificasse os
valores da matriz
20
10
Category
Acids and Amides
Basic
Aromatic
Hydrophilic
Amino Acid
Asp (D) Glu(E) Asn (N) Gln (Q)
His (H) Lys (K) Arg (R)
Phe (F) Tyr (Y) Trp (W)
Ala (A) Cys (C) Gly (G) Pro (P) Ser (S) Thr(T)
Hydrophobic
Ile (I) Leu (L) Met (M) Val (V)
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
3/17/2005
21
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 igual
tamanho e totalmente alinhadas
3/17/2005
22
11
Modelo aleatório, R :
• Assume que o símbolo a ocorre de uma forma
independente com uma probabilidade qa
• A probabilidade das duas sequências é apenas o
produto das probabilidades de cada símbolo
P ( x, y | R ) =
∏q ∏q
xi
i
yj
j
3/17/2005
23
Modelo relacionado, M:
• Assume que os pares de símbolos alinhados
ocorrem com uma probabilidade conjunta pab
• 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
P( x, y | M ) =
∏p
xi yi
i
3/17/2005
24
12
Odds ratio:
P ( x, y | M )
=
P ( x, y | R )
∏p
∏q ∏q
i
i
xi yi
xi
i
=
yi
∏q
p xi yi
i
xi q yi
Modelo de custo aditivo, Log-odds ratio:
S=
s ( xi , yi ) where s (a, b) = log
i
pab
qa qb
•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
3/17/2005
25
Espaçamentos
Os espaçamentos são normalmente penalizados
Custo associado a um espaçamento de tamanho g:
•Função linear simples
γ ( g ) = − gd
•Função mais sofisticada
γ ( g ) = −d − ( g − 1)e
sendo g o tamanho do espaçamento, d o valor de cada
alinhamento com um espaçamento e e o valor atribuido a
cada extensão do espaçamento
3/17/2005
26
13
Affine Gap Penalties
Na natureza, muitas vezes os espaçamentos
surgem em conjuntos e não apenas para um
nucleótido isolado
3/17/2005
Na natureza esta
situação é mais
provável
Com uma função de custo
simples obtem-se o
mesmo valor para estes
alinhamentos
27
Modelo Probabilístico
P( gap ) = f ( g )
∏q
xi
i in gap
• 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:
γ ( g ) = log ( f ( g ))
3/17/2005
28
14
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
29
Matrizes de mérito para
proteínas
Família de matrizes que contêm a
probabilidade de uma sequência se ter
transormado noutra durante o processo
evolutivo
As duas famílias mais conhecidas são as
matrizes PAM (Point Accepted Mutation) e
as matrizes BLOSUM (BLOcks
Substitution Matrix)
3/17/2005
30
15
Matrizes 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
31
Matrizes PAM
A construção destas matrizes baseou-se na
obtenção de dados sobre as substituições ocorridas
em alinhamentos de proteínas muito semelhantes
Permite obter relações evolutivas para proteínas da
mesma família e permite ainda a extrapolação
desta informação para outras distâncias evolutivas
Iniciou-se com a construção de árvores
filogenéticas hipotéticas, relacionando sequências
de 71 familias, onde cada par de sequências
diferiam em não mais de 15%
3/17/2005
32
16
Matrizes PAM
O termo PAM tem 2 utilizações distintas mas
relacionadas:
• Unidade de medida de distância evolutiva
• 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
33
Matrizes PAM
A matriz PAM 1 é definida a partir de muitos
alinhamentos de proteinas extremamente
semelhantes.
A partir de um conjunto de alinhamentos:
• f(i,j) – número de vezes que o aminoácido i está alinhado
com o aminoácido j, dividindo pelo número de posições
alinhadas
• g(i,j) = f(i,j)/f(i) , f(i) é a frequência do aminoácido i em
todas as proteinas do conjunto de dados
• g(i,j) define a probabilidade do aminoácido i se
transformar no aminoácido j dentro de uma distância
evolutiva de 1 PAM
3/17/2005
34
17
Matrizes PAM
Matriz PAM 1:
• Cada posição (i,j) da matriz é definida por
– (i,j) = log f(i,j)/f(i).f(j)
= log g(i,j)/f(j)
• f(i).f(j), corresponde à frequência com que o
aminoácido i é alinhado com o aminoácido j
apenas por acaso (modelo aleatório)
A matrix PAM n é obtida a partir da
multiplicação da matrix PAM 1 n vezes
3/17/2005
35
Matrizes 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.
3/17/2005
36
18
PAM matrices
Distância evolutiva
(PAM)
1
11
23
38
56
80
120
159
250
Diferenças
observadas (%)
1
10
20
30
40
50
Mais utilizada
60
PAM 250
70
80
80
3/17/2005
37
3/17/2005
38
19
BLOSUM
(Henikoff, 1992)
Estas matrizes foram obtidas utilizando, na sua
essência, o modelo probabilístico descrito
anteriormente
Foram obtidas a partir de um enorme volume de
dados pertencentes à base de dados, BLOCKS, de
famílias de proteínas
As sequências foram agrupadas sempre que a
percentagem de caracteres idênticos excedesse um
determinado nível L
BLOSUM50 e BLOSUM62 são as mais utilizadas
3/17/2005
A
R
N
D
C
Q
E
G
H
I
L
K
M
F
P
S
T
W
Y
V
A
5
-2
-1
-2
-1
-1
-1
0
-2
-1
-2
-1
-1
-3
-1
1
0
-3
-2
0
3/17/2005
39
R
-2
7
-1
-2
-4
1
0
-3
0
-4
-3
3
-2
-3
-3
-1
-1
-3
-1
-3
N
-1
-1
7
2
-2
0
0
0
1
-3
-4
0
-2
-4
-2
1
0
-4
-2
-3
D
-2
-2
2
8
-4
0
2
-1
-1
-4
-4
-1
-4
-5
-1
0
-1
-5
-3
-4
C
-1
-4
-2
-4
13
-3
-3
-3
-3
-2
-2
-3
-2
-2
-4
-1
-1
-5
-3
-1
Q
-1
1
0
0
-3
7
2
-2
1
-3
-2
2
0
-4
-1
0
-1
-1
-1
-3
E
-1
0
0
2
-3
2
6
-3
0
-4
-3
1
-2
-3
-1
-1
-1
-3
-2
-3
G
0
-3
0
-1
-3
-2
-3
8
-2
-4
-4
-2
-3
-4
-2
0
-2
-3
-3
-4
H
-2
0
1
-1
-3
1
0
-2
10
-4
-3
0
-1
-1
-2
-1
-2
-3
2
-4
I
-1
-4
-3
-4
-2
-3
-4
-4
-4
5
2
-3
2
0
-3
-3
-1
-3
-1
4
L
-2
-3
-4
-4
-2
-2
-3
-4
-3
2
5
-3
3
1
-4
-3
-1
-2
-1
1
K
-1
3
0
-1
-3
2
1
-2
0
-3
-3
6
-2
-4
-1
0
-1
-3
-2
-3
M
-1
-2
-2
-4
-2
0
-2
-3
-1
2
3
-2
7
0
-3
-2
-1
-1
0
1
F
-3
-3
-4
-5
-2
-4
-3
-4
-1
0
1
-4
0
8
-4
-3
-2
1
4
-1
P
-1
-3
-2
-1
-4
-1
-1
-2
-2
-3
-4
-1
-3
-4
10
-1
-1
-4
-3
-3
S
1
-1
1
0
-1
0
-1
0
-1
-3
-3
0
-2
-3
-1
5
2
-4
-2
-2
T
0
-1
0
-1
-1
-1
-1
-2
-2
-1
-1
-1
-1
-2
-1
2
5
-3
-2
0
W
-3
-3
-4
-5
-5
-1
-3
-3
-3
-3
-2
-3
-1
1
-4
-4
-3
15
2
-3
Y
-2
-1
-2
-3
-3
-1
-2
-3
2
-1
-1
-2
0
4
-3
-2
-2
2
8
-1
V
0
-3
-3
-4
-1
-3
-3
-4
-4
4
1
-3
1
-1
-3
-2
0
-3
-1
5
40
20
PAM vs. BLOSUM
O modelo PAM tem a capacidade de evidênciar a origem
evolutiva de proteínas
O modelo Blosum tem a capacidade de evidênciar domínios
conservados em proteínas
Regras práticas
• Baixas PAMs e elevadas Blosums encontram pequenos
alinhamentos locais com elevada semelhança
• Elevadas PAMs e baixas Blosums encontram alinhamentos
locais mais fracos mas longos
3/17/2005
41
3/17/2005
42
21
Algoritmos de alinhamento
Quais as dificuldades?
Considere duas sequências de tamanho n
Pergunta:
• 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 subsequências das duas cadeias de caracteres
3/17/2005
43
Algoritmos de alinhamento
Quais as dificuldades?
Existem
(2n)! 2 2 n
=
≈
n
(n!) 2
πn
2n
possíveis alinhamentos globais
Pretende-se obter o melhor de todos
3/17/2005
44
22
Então?
Para n = 20, temos cerca
de 120 biliões de
alinhamentos possíveis
Na prática pretendemos
alinhar sequências muito,
mas muito mais longas
• Algumas proteínas têm
mais de 1000 aminoácidos
• Os genes podem ter vários
milhares de pares de bases
3/17/2005
45
Alinhamento Global vs. Local
3/17/2005
46
23
ALINHAMENTO GLOBAL
• Compara duas sequências em toda a sua extensão
• É apropriado para comparar sequências cujas
semelhanças sejam esperadas em toda a sua extensão
• O alinhamento maximiza as regiões de semelhança e
minimiza os espaçamentos
ALINHAMENTO LOCAL
• Procura locais de semelhança entre 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 onde não existe qualquer
conhecimento sobre a semelhança entre as sequências a
comparar
3/17/2005
47
ALINHAMENTO GLOBAL versus LOCAL
Alinhamento Global
--T—-CC-C-AGT—-TATGT-CAGGGGACACG—A-GCATGCAGA-GAC
| || | || | | | |||
|| | | | | ||||
|
AATTGCCGCC-GTCGT-T-TTCAG----CA-GTTATG—T-CAGAT--C
Alinhamento Local
tccCAGTTATGTCAGgggacacgagcatgcagagac
||||||||||||
aattgccgccgtcgttttcagCAGTTATGTCAGatc
3/17/2005
48
24
Programação Dinâmica (DP):
algoritmo que permite obter alinhamentos
óptimos utilizando funções de mérito
aditivas
Estes algoritmos garantem como solução o
melhor alinhamento ou melhor conjunto de
alinhamentos
Os algoritmos mais simples são os algoritmos
para alinhamento de pares de sequências
3/17/2005
49
Programação Dinâmica
Novo melhor alinhamento = melhor anterior + melhor local
Sequência A
Melhor alinhamento anterior
...
...
...
...
Sequência B
3/17/2005
50
25
Descriçã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
51
EXEMPLO: Duas sequências de aminoácidos
x: HEAGAWGHEE
y: PAWHEAE
d=8
s(xi,yj) = BLOSUM50
3/17/2005
H
E
A
G
W
P
-2
-1
-1
-2
-4
A
-2
-1
5
0
-3
W
-3
-3
-3
-3
15
H
10
0
-2
-2
-3
E
0
6
-1
-3
-3
52
26
Alinhamento Global: Algoritmo
Needleman-Wunsh (1970)
Ideia: Construir um alinhamento óptimo utilizando
soluções óptimas obtidas anteriormente para subsequências mais pequenas
• Constroi uma matriz F com indices i e j, um para cada
sequência
• O valor F(i,j) representa o melhor obtido pela função
de mérito para o alinhamento de x1...i com y1...j
• Constroi F(i,j) de uma forma recursiva
3/17/2005
53
F matrix
H
E
A
G
A
W
G
H
E
E
i
P
j
A
X
W
H
E
A
E
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
3/17/2005
HEA
HEA
HEA -xxii
---PA
PA
PA y-yjj
j1−1, )1j +
) −s (dxi , y j )
F (i, Fj )(i=, jF) (=i −F1(,i,j−−
54
27
F(i-1,j-1)
F(i,j-1)
-d
s(xi,yj)
F(i-1,j)
F(i,j)
-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
F (i − 1, j − 1) + s ( xi , y j )
F (i, j ) = max
F (i − 1, j ) − d
F (i, j − 1) − d
3/17/2005
55
Example:
H
E
A
G
A
W
G
H
E
E
0
-8
-16
-24
-32
-40
-48
-56
-64
-72
-80
P
-8
-2
-9
-17
-25
-33
-42
-49
-57
-65
-73
A
-16
W -24
3/17/2005
H
-32
E
-40
A
-48
E
-56
56
28
Example:
H
E
A
G
A
W
G
H
E
E
0
-8
-16
-24
-32
-40
-48
-56
-64
-72
-80
P
-8
-2
-9
-17
-25
-33
-42
-49
-57
-65
-73
A
-16
-10
-3
-4
-12
-20
-28
-36
-44
-52
-60
W
-24
-18
-11
-6
-7
-15
-5
-13
-21
-29
-37
H
-32
-14
-18
-13
-8
-9
-13
-7
-3
-11
-19
E
-40
-22
-8
-16
-16
-9
-12
-15
-7
3
-5
A
-48
-30
-16
-3
-11
-11
-12
-12
-15
-5
2
E
-56
-38
-24
-11
-6
-12
-14
-15
-12
-9
1
F(n,m) is the best
score for the
alignment
3/17/2005
57
H
E
A
G
A
W
G
H
E
E
0
-8
-16
-24
-32
-40
-48
-56
-64
-72
-80
P
-8
-2
-9
-17
-25
-33
-42
-49
-57
-65
-73
A
-16
-10
-3
-4
-12
-20
-28
-36
-44
-52
-60
W
-24
-18
-11
-6
-7
-15
-5
-13
-21
-29
-37
H
-32
-14
-18
-13
-8
-9
-13
-7
-3
-11
-19
E
-40
-22
-8
-16
-16
-9
-12
-15
-7
3
-5
A
-48
-30
-16
-3
-11
-11
-12
-12
-15
-5
2
E
-56
-38
-24
-11
-6
-12
-14
-15
-12
-9
1
Trace arrows back from the lower right to top left
• Diagonal – both
HEAGAWGHEHEAGAWGHE-E
• Up – upper gap
--P
--P-AWAW-HEAE
• Left – lower gap
3/17/2005
58
29
Algorithm 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
59
Algorithm complexity
Example 1:
•
•
•
•
•
S1: size 103
S2: size 103
Algorithm O(nm)
Machine: 1GHz and 1Gb RAM (109 steps/second)
Time: 1ms
Example 2:
•
•
•
•
•
3/17/2005
S1: size 109
S2: size 109
Algorithm O(nm) O(n logm)
Machine: 1GHz and 1Gb RAM (109 steps/second) 1010s/s
Time: 109s => 30 anos 108s => 3 anos 9s
60
30
Local alignment
Local alignment
Compute a “mini”
Global Alignment to
get Local
Global alignment
3/17/2005
61
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
3/17/2005
62
31
Local alignment: Smith-Waterman
algorithm (1981)
0
F (i − 1, j − 1) + s ( xi , y j )
F (i, j ) = max
F (i − 1, j ) − d
F (i, j − 1) − d
Another dynamic programming solution
3/17/2005
63
H
E
A
G
A
W
G
H
E
E
0
0
0
0
0
0
0
0
0
0
0
P
0
0
0
0
0
0
0
0
0
0
0
A
0
0
0
5
0
5
0
0
0
0
0
W
0
0
0
0
2
0
20
12
4
0
0
H
0
10
2
0
0
0
12
18
22
14
6
E
0
2
16
8
0
0
4
10
18
28
20
A
0
0
8
21
13
5
0
4
10
20
27
E
0
0
6
13
18
12
4
0
4
16
26
Start at highest score and traceback to first 0
AWGHE
AWAW-HE
3/17/2005
64
32
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
65
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 nonoverlapping copies of sections of one sequence in
the other
3/17/2005
66
33
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
67
Repeated matches
Initial conditions: F(0,0) = 0
F (i,0) = max
F (i − 1,0)
F (i − 1, j ) − T
j = 1,..., m
F (i,0)
F (i − 1, j − 1) + s ( xi , y j )
F (i, j ) = max
F (i − 1, j ) − d
F (i, j − 1) − d
3/17/2005
68
34
H
E
A
G
A
W
G
H
E
E
0
0
0
0
1
1
1
1
1
3
9
P
0
0
0
0
1
1
1
1
1
3
9
A
0
0
0
5
1
6
1
1
1
3
9
W
0
0
0
0
2
1
21
13
5
3
9
H
0
10
2
0
1
1
13
19
23
15
9
E
0
2
16
8
1
1
5
11
19
29
21
A
0
0
8
21
13
6
1
5
11
21
28
E
0
0
6
13
18
12
4
1
5
17
27
(n+1,0)
9
T = 20
The optimal alignment with total score 9 = 29 – 20
There are two separate match regions with scores 1 and 8
3/17/2005
HEA.AWHEA.AW-HE.
69
Overlap matches
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
3/17/2005
70
35
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
71
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”)
3/17/2005
72
36
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
73
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 ktuple 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
3/17/2005
74
37
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-spots
in a single diagonal
• Third:
– Evaluation
» Each hot-spot has a positive score
» The space between consecutive hot-spots has a negative score
» The score of a diagonal run is the sum
3/17/2005
75
Example:
H
E
A
G
A
W
G
H
E
E
P
A
W
H
E
A
E
3/17/2005
76
38
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
77
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’
3/17/2005
78
39
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
79
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 alignment
score (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
3/17/2005
80
40
BLAST
Strategy:
• With a fixed length w and a fixed threshold t, find all
length-w substrings of S that align to some length-w
substring 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
81
BLAST
Length-W
Query: KRHRKVLRDNIQGITKPAIRRLARRGGVKRISGLIYEETRGVLKIFLENVIRD
GVK 18
GAK 16
Neighborhood
GIK 16
words
GGK 14
neighborhood
GLK 13
score threshold
GNK 12
(T = 13)
GRK 11
GEK 11
GDK 11
extension
Query: 22
VLRDNIQGITKPAIRRLARRGGVKRISGLIYEETRGVLK 60
+++DN +G +
IR L
G+K I+ L+ E+ RG++K
Sbjct: 226 IIKDNGRGFSGKQIRNLNYGIGLKVIADLV-EKHRGIIK 263
High-scoring Pair (HSP)
3/17/2005
82
41
Original BLAST: Example
3/17/2005
From lectures by Serafim Batzoglou
(Stanford)
A 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
• w = 4, T = 4
• Exact keyword
match of
• Extend
diagonals with
mismatches
until score is
under T
• Output result
83
Gapped BLAST: Example
Original BLAST exact
keyword search,
THEN:
Extend with gaps in a
zone around ends of
exact match
Output result
• GTAAGGTCCAG
T
• GTTAGGTCAGT
From lectures by Serafim Batzoglou
(Stanford)
3/17/2005
C T G A T C C T G G A T T G C G A
A C G A A G T A A G G T C C A G T
84
42
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
85
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
3/17/2005
86
43