Embed Size (px)
Citation preview
Clustal-W
Oscar Miranda
17/06/2001ClustalW
Conteúdo
Problema Características A ferramenta Algoritmos Referências
17/06/2001ClustalW
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
17/06/2001ClustalW
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
17/06/2001ClustalW
Comparando Várias Seqüências
Caso geral do alinhamento de entre 2 seqüências– O(n2 )
Alinhamento Ótimo– Programação dinâmica O(k22knk)– NP-completo
Tree Alignment– Qualidade aceitavel– Rápido para poucas seqüências
Outras Heurísticas– Busca em base de dados
17/06/2001ClustalW
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
17/06/2001ClustalW
Processo
Dividido em 3 passos
Matriz de distâncias
Geração da árvore
Alinhamento
17/06/2001ClustalW
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
17/06/2001ClustalW
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
17/06/2001ClustalW
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
17/06/2001ClustalW
Algoritmo de Myers e Miller
17/06/2001ClustalW
Algoritmo de Myers e Miller
Dividir para conquistar– Encontrar na linha do
meio o ponto que faz parte do alinhamento
17/06/2001ClustalW
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);
17/06/2001ClustalW
Matriz de Distância
>S1
ATCTCGAGA
>S2
ATCCGAGA
>S3
ATGTCGACGA
>S4
ATGTCGACAGA
>S5
ATTCAACGA
S1 S2 S3 S4 S5
S1 -
S2 87 -
S3 77 62 -
S4 77 62 90 -
S5 55 62 77 66 -
17/06/2001ClustalW
Processo: Passo 1
Fast Approximate– Algoritmo de Wilbur e Lipman– Alinhamento Aproximado– O(n + m + M2)
M: número de fragmentos
17/06/2001ClustalW
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;
17/06/2001ClustalW
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).
17/06/2001ClustalW
Matriz de Distância 2
Fast-Approximate Programação dinâmica
S1 S2 S3 S4 S5
S1 -
S2 62 -
S3 67 50 -
S4 78 50 80 -
S5 44 50 67 44 -
S1 S2 S3 S4 S5
S1 -
S2 87 -
S3 77 62 -
S4 77 62 90 -
S5 55 62 77 66 -
17/06/2001ClustalW
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
17/06/2001ClustalW
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
17/06/2001ClustalW
Exemplo Neighbor-Joining
S1 S2 S3 S4 S5
S1 -
S2 87 -
S3 77 62 -
S4 77 62 90 -
S5 55 62 77 66 -
17/06/2001ClustalW
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
17/06/2001ClustalW
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
17/06/2001ClustalW
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.
17/06/2001ClustalW
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)
17/06/2001ClustalW
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)| )
17/06/2001ClustalW
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)
17/06/2001ClustalW
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
17/06/2001ClustalW
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
17/06/2001ClustalW
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
17/06/2001ClustalW
Matriz de Pesos
Séries– GONNET(default)
[35-100%]: Gonnet80; [25-35%]: Gonnet120; [0-25%]: Gonnet250– BLOSUM(Heinkoff)
[80-100%]: Blosum80; [60-80%]: Blosum62; [30-60%]: Blosum45; [0-30%]: Blosum30
– PAM(Dayhoff) [80-100%]: Pam20; [60-80%]: Pam60; [40-60%]: Pam120; [0-40%]:
Pam350
DNA– IUB (BESTFIT) (padrão)– CLUSTAL
17/06/2001ClustalW
Seqüências Divergentes
Atrasar o alinhamento das seqüências mais divergentes para diminuir o erro na fase inicial do alinhamento
17/06/2001ClustalW
Exemplos
17/06/2001ClustalW
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
