Clustal-W
Oscar Miranda
Conteúdo





Problema
Características
A ferramenta
Algoritmos
Referências
ClustalW
17/06/2001
Alinhamento Múltiplo


Comparando Várias Seqüências
Visualmente
–
Manter bases conservadas
-----GC-GATAG---CAGTCGCTGATCGTACG

Quantificando a qualidade de um alinhamento
–
Tratamento de gaps e substituições
ClustalW
17/06/2001
Para quê?





Encontrar padrões que caracterizam famílias de
proteínas
Detectar ou demonstrar homologia entre novas
seqüências e famílias de seqüências existentes
Ajuda a predizer as estruturas secundárias e terciárias
de novas seqüências
Sugerir oligonucleotídios primários para PCR
Análise da evolução molecular
ClustalW
17/06/2001
Comparando Várias Seqüências

Caso geral do alinhamento de entre 2 seqüências
–

Alinhamento Ótimo
–
–

Programação dinâmica O(k22knk)
NP-completo
Tree Alignment
–
–

O(n2 )
Qualidade aceitavel
Rápido para poucas seqüências
Outras Heurísticas
–
Busca em base de dados
ClustalW
17/06/2001
Clustal-W: A ferramenta





Disponível gratuitamente
Código aberto
Várias plataformas
Parâmetros definidos pelo usuário
Reconhece automaticamente vários formatos
–

NBRF/PIR, EMBL/SWISSPROT, Pearson (Fasta), Clustal (*.aln),
GCG/MSF (Pileup), GCG9/RSF e GDE flat file.
Clustal-X
–
–
–
Versão mais amigável
Alinhamento colorido
Ajuda/explicação de parâmetros
ClustalW
17/06/2001
Processo

Dividido em 3 passos
Matriz de
distâncias
Geração
da árvore
ClustalW
Alinhamento
17/06/2001
Processo: Passo 1

Passo 1
–
–
–
É gerada a matriz de distâncias
Todas as seqüências são comparadas par a par
Dois métodos:

Fast Approximate method
–

Rápido
Full dynamic programming
–
Eficaz mas lento
– default
ClustalW
17/06/2001
Processo: Passo 1

Programação dinâmica
–
–
–
Alinha todas as seqüências par a par
Algoritmo de Myers e Miller modificado
Usa Matriz de pesos


–
Proteínas: PAM, BLOSUM, GONNET
DNA: IUB(bestfit), clustal
Parâmetros GAP


Abertura de gap: GOP
Extensão de gap: GEP
ClustalW
17/06/2001
Algoritmo de Myers e Miller


Espaço linear
Cálculo do escore em
espaço linear
–
Cada elemento da
matriz é calculado com
apenas 3 vizinhos
ClustalW
17/06/2001
Algoritmo de Myers e Miller
ClustalW
17/06/2001
Algoritmo de Myers e Miller

Dividir para
conquistar
–
Encontrar na linha do
meio o ponto que faz
parte do alinhamento
ClustalW
17/06/2001
Algoritmo de Myers e Miller
Path(i1,j1, i2, j2)
midi = (i1+i2)/2
S+ <- alinhamento(i1, j1, midi, j2);
S* <- alinhamento_reverso(midi, j1, i2, j2);
midj = j entre j1 e j2 tal que S+[j] + S*[j] é máximo
path(i1, j1, midi, midj);
path(midi, midj, i2, j2);
ClustalW
17/06/2001
Matriz de Distância
>S1
ATCTCGAGA
>S2
ATCCGAGA
>S3
ATGTCGACGA
>S4
ATGTCGACAGA
>S5
ATTCAACGA
S1 S2 S3
S4
S1
-
S2
87
-
S3
77
62
-
S4
77
62
90
-
S5
55
62
77
66
ClustalW
S5
-
17/06/2001
Processo: Passo 1

Fast Approximate
–
–
–
Algoritmo de Wilbur e Lipman
Alinhamento Aproximado
O(n + m + M2)

M: número de fragmentos
ClustalW
17/06/2001
Algoritmo de Wilbur e Lipman
1.
Seleciona os fragmentos onde cada fragmento é uma tripla
(i,j,k) tal que as k-tuplas de símbolos das duas seqüências
casam; xi=yj, xi+1=yj+1,...,xi+k=yj+k O(n+m+M)
Um fragmento (i’,j’,k’) é dito abaixo(i,j,k) se i+k<=i’
e j+k<=j’;
Quando as substring no fragmento (i’,j’,k’) aparecem
estritamente depois das de (i,j,k) nas strings de entrada.
O tamanho do fragmento (i,j,k) é k.
A diagonal do fragmento (i,j,k) é o número j – i e a
diagonal reversa é i + j;
ClustalW
17/06/2001
Algoritmo de Wilbur e Lipman
Um alinhamento de fragmentos é definido como uma seqüência
de fragmentos tais que, se (i,j,k) e (i’,j’,k’) são
fragmentos adjacentes na seqüência, ou (i’,j’,k’) está
abaixo de (i,j,k) em uma diagonal diferente(um gap), ou os
dois fragmentos estão na mesma diagonal, com i’> i(mismatch).
ClustalW
17/06/2001
Matriz de Distância 2
S1
S2
S3
S4
S1
-
S2
62
-
S3
67
50
-
S4
78
50
80
-
S5
44
50
67
44
S5
-
S1
S2
S3
S4
S1
-
S2
87
-
S3
77
62
-
S4
77
62
90
-
S5
55
62
77
66
S5
-
Programação dinâmica
Fast-Approximate
ClustalW
17/06/2001
Processo: Passo 2

Construção da árvore a partir da matriz de
distâncias
–


Usada como guia para o próximo passo
Método Neighbour-Joining
Gera arquivo que pode ser visualizado
posteriormente
ClustalW
17/06/2001
Método Neighbor-Joining


Saitou and Nei (1987)
Algoritmo guloso
–
–
–
Inicia Com uma Árvore Estrela
A cada iteração junta os dois nós da raiz os quais a
soma das divergências de cada para o resto da
árvore seja mínimo
Estima o tamanho do novo nó a partir dos valores
de divergência dos nós escolhidos
ClustalW
17/06/2001
Exemplo Neighbor-Joining
S1
S2
S3
S4
S1
-
S2
87
-
S3
77
62
-
S4
77
62
90
-
S5
55
62
77
66
S5
-
ClustalW
17/06/2001
Processo: Passo 3

Alinhamento Progressivo baseado na árvore
filogenética
–




Feng e Doolittle
Diferentes Penalidades para GAP
Opção para modificar valores iniciais
Valores atualizados durante o processo
Utiliza o Algoritmo de Myers e Miller
modificado para o alinhamento do consenso
ClustalW
17/06/2001
Tratamento de GAPs

Parâmetros iniciais dados pelo usuário
–


Abertura de gap(GOP) e extensão de gap(GEP)
GAPs terminais não tem custo
Escolha dos valores automaticamente durante
o processo de alinhamento
ClustalW
17/06/2001
GAP: valores iniciais

1) GOP dependente da matriz de pesos
utilizada
–

Variar a penalidade dos gaps de acordo com
diferentes matrizes melhora a qualidade.
2) Dependência no grau de similaridade das
seqüências
–
Uso do percentual de semelhança entre seqüências
para aumentar ou diminuir o GOP.
ClustalW
17/06/2001
GAP: valores iniciais

3) Dependência no tamanho das seqüências
–
Crescimento do escore com o tamanho das
seqüências
GOP = GOP_origem + log(min(N,M)))*
(escore médio de resíduos não casados) *
(percentual de semelhança)
ClustalW
17/06/2001
GAP: valores iniciais

4) Dependência na diferença do tamanho das
seqüências
–
Se uma seqüência é muito menor que a outra, GEP
é aumentado para inibir muitos gaps longos na
seqüência menor.
GEP = GEP_origem * ( 1.0 + |log(N/M)| )
ClustalW
17/06/2001
GAP: penalidades localizadas


Antes de cada alinhamento gera uma tabela de gaps
para cada posição.
1) Diminuição da penalidade para gaps existentes
Se já existe um gap na posição o GOP é reduzido em
proporção ao número de seqüências com gap, e o GEP é
diminuído pela metade.
GOP = GOP*0.3*(No_seqüências_sem_gap/No_seqüências)
–
ClustalW
17/06/2001
GAP: penalidades localizadas

2) Aumento da penalidade proximo a gaps existentes
Se uma posição não possui gaps mas está a 8 residuos de um
gap, o GOP é modificado para:
GOP = GOP*(2 + ((8-distancia_do_gap)*2)/8)
–

3) Redução da penalidade em trecho hidrófilos
–
–
Uma seqüência de 5 resíduos hidrófilos é considerada um
trecho hidrófilo
Se uma posição não há gaps e existe um trecho hidrófilo, o
GOP é reduzido por um terço
ClustalW
17/06/2001
GAP: penalidades localizadas

4) Penalidades especificas por resíduo
–
–
Se não há trechos hidrófilos e não há gaps em uma
posição então o GOP é multiplicado pela média
números atribuídos a cada aparição do resíduo na
posição
Números provenientes da tabela de Pascarella e
Argos com fatores de modificação do gap para cada
resíduo
ClustalW
17/06/2001
Matriz de Pesos

Matrizes usadas para cálculo de similaridade
entre amino ácidos
–


Dados auxiliares
Dependendo da semelhança entre as
seqüências uma matriz mais “flexível” é
escolhida
Pode-se definir uma matriz a ser utilizada
ClustalW
17/06/2001
Matriz de Pesos

Séries
–
GONNET(default)

–
BLOSUM(Heinkoff)

–
[80-100%]: Blosum80; [60-80%]: Blosum62; [30-60%]: Blosum45;
[0-30%]: Blosum30
PAM(Dayhoff)


[35-100%]: Gonnet80; [25-35%]: Gonnet120; [0-25%]:
Gonnet250
[80-100%]: Pam20; [60-80%]: Pam60; [40-60%]: Pam120; [040%]: Pam350
DNA
–
–
IUB (BESTFIT) (padrão)
CLUSTAL
ClustalW
17/06/2001
Seqüências Divergentes

Atrasar o alinhamento das seqüências mais
divergentes para diminuir o erro na fase inicial
do alinhamento
ClustalW
17/06/2001
Exemplos
ClustalW
17/06/2001
Referências




Programas, documentação e artigos sobre Clustal-W e Clustal-X
– http://www-igbmc.u-strasbg.fr/BioInfo/
Thompson, J.D., Higgins, D.G. and Gibson, T.J. (1994) CLUSTAL W:
improving the sensitivity of progressive multiple sequence alignment
through sequence weighting, position specific gap penalties and weight
matrix choice. Nucleic Acids Research, 22(22):4673-4680.
Eppstein, D.A. (1989) Efficient Algorithms for Sequence Analisys With
Concave and Convex Gap Costs
Neighbor-Joining
– http://www.biology.usu.edu/biol6750/Lecture_18.htm
ClustalW
17/06/2001