Fisica Computazionale applicata alle
Macromolecole
Metodi di allineamento
Pier Luigi Martelli
Università di Bologna
[email protected]
051 2094005
338 3991609
Ricordiamo...
La struttura di una proteina in ambiente fisiologico
dipende solo dalla sua sequenza amminoacidica
Esperimento di Anfinsen
Differenti sequenze amminoacidiche assumono in ambiente
fisiologico lo stesso fold
Banche dati CATH e SCOP: Organizzazione gerarchica
La funzione dipende dalla struttura, sebben questa
relazione non sia rigorosa
La funzione dipende da tutta la struttura, non solo dal fold
Problema
Determinare il fold a partire dalla sequenza amminoacidica
Allineare le sequenze in modo da riprodurre l’allineamento
generato dalla sovrapposizione delle loro due strutture
Strategia
Esaminare come le sequenze hanno avuto origine
Perché nei vari organismi esistono sequenze differenti per una
unica funzione?
Evoluzione Molecolare e omologia
Evoluzione: Mutabilità e Selezione Naturale
Le sequenze degli organismi attuali hanno avuto origine
dall’evoluzione di sequenze ancestrali
Le sequenze genomiche cambiano continuamente in modo
casuale
L’ambiente seleziona gli individui in base al loro fenotipo
Se il prodotto del gene modificato non è funzionale (perde
struttura o funzione) l’individuo muore e la modifica non si
trasmette
NB. Le mutazioni sono casuali? Almeno la loro velocità, non
sempre: SOS polimerasi di Radman
Evoluzione Molecolare e omologia
Omologia
Due sequenze sono dette omologhe se hanno un ancestore
comune
Ortologhe in due specie differenti
Paraloghe all’interno della stessa specie
(duplicazione genica)
Similarità
Due sequenze sono dette simili se condividono buona parte
della sequenza (molti amminoacidi uguali o simili): concetto
NON evolutivo, ma di confronto tra sequenze
Omologia e Similarità
Sequenze omologhe sono sempre simili?
Dipende dal grado di divergenza
Sequenze simili sono sempre omologhe?
Sequenze differenti possono essere evolute convergentemente
verso sequenze simili (es., non su sequenze, ali di uccelli e ali di
pipistrello sono evoluzioni convergenti, a partire da da rettili e
da mammiferi)
Di
principio
similarità
e
omologia
non
coincidono
esattamente. Tuttavia se due sequenze sono molto simili
sono probabilmente omologhe.
Per ora misuriamo la similarità in termini di identità di
sequenza
Identità di sequenza e identità strutturale
Quando la similarità di sequenza implica similiarità
strutturale?
Identità di sequenza e identità strutturale
Fino a quanto due sequenze simili danno strutture uguali?
Fraction of residues in core with
RMSD < 0.1 nm
Rmsd of backbone atoms in core
2.5
2.0
1.5
1.0
0.5
0.0
100
50
0
Percent identical residues in core
1.0
0.8
0.6
0.4
0.2
0.0
100
50
0
Percent identical residues in core
•2 proteine sono sovrapposte e si esamina la percentuale di
identità nel nucleo sovrapposto
•Proteine con identità maggiore del 60% hanno il 90% dei
residui sovrapposti a meno di 0.1 nm
Chothia, C. & Lesk, A. M. (1986). The relation between the divergence of sequence and structure in
proteins. EMBO J. 5, 823-826.
Identità di sequenza e identità strutturale
100
identity
Identità di sequenza (%)
.
80
Identità di sequenza implica
identità strutturale
60
40
Identità
di sequenza
20
NON implica identità strutturale
0
0
50
100
150
200
250
Numero di residui allineati
Rost B (1999). The twilight zone of protein alignments. Protein Engineering 12, 85-94.
Identità di sequenza e identità strutturale
Quindi due sequenze più lunghe di 100 residui,
condividano il 30 % dei residui, hanno struttura simile
che
.
Per sequenze più corte la percentuale di identità deve
essere più alta
Questo NON implica che sequenze con identità minore
abbiano strutture differenti
Esempio: Mioglobina di capodoglio e emoglobina batterica:
RMSD = 0.19 nm, Identità: 14%
Identità di sequenza e identità strutturale
Per sequenze più lunghe di 100 residui
Twilight zone:
Safe zone:
alto numero di falsi
positivi
(sequenza simile
struttura diversa)
nessun falso positivo
tutte le sequenze
simili hanno la
stessa struttura
Midnight zone:
contiene la maggior
parte delle proteine
strutturalmente simili
20%
30%
Percentuale di identità
Allineamento di sequenze
Problema: date due sequenze, confrontarle in modo da
rilevare la loro similarità
•Definire una distanza tra le sequenze
•Cercare un algoritmo per trovare l’allineamento a minima
distanza
•Studiare
metodi
dell’allineamento
per
validare
la
significativicità
Distanza tra sequenze
Quali eventi consideriamo?
Mutazione
Va definito un punteggio per la sostituzione dell’amminoacido
i con l’amminoacido j
Matrici di sostituzione s(i,j)
A:
B:
ALASVLIRLITRLYP
ASAVHLNRLITRLYP
Score( A, B)   s( Ai , B i )
La matrice di sostituzione riflette se una mutazione è
mediamente compatibile col folding e col mantenimento della
funzione
Derivazione degli score da allineamenti di sequenze
omologhe
Vogliamo misurare la probabilità di mutazione di ogni tipo
di amminoacido in un insieme di sequenze omologhe
Date (molte) coppie di sequenze correlate, misuriamo la
frequenza della sostituzione iA->jB o iB->jA (indipendente dalla
direzione): Pij
Es:
A:
B:
ALASVLIRAILRLYP
ALAVLLNRLILRALP
P(A,A)= N(AA,AB)/N = 2/15
P(A,L)= P(L,A)= [N(LA,AB)+N(AA,LB)]/N = 2/15
La sostituzione è significativa?
Qual è la probabilità che la sostituzione i->j sia casuale (e
quindi non significativa)?
Es: 1° insieme di sequenze omologhe
A:
B:
ALASVLIRAILRLYP
ALAVLLNRLILRALP
2° insieme di sequenze omologhe
A:
LLLLAALLLALLALL
B:
LALLAALLAALLALL
P(A,L)= 2/15 in entrambi i casi. Sono ugualmente significativi?
La probabilità che questa sostituzione sia casuale dipende dalle
frequenze di occorrenza dei singoli amminoacidi Pi e Pj
Confronto con l’ipotesi di indipendenza
Sostituzione iA -> jB casuale significa che i 2 eventi:
E1 = (i in A) e E2 = (j in B) sono INDIPENDENTI
Per determinare il grado di “non casualità” della sostituzione
bisogna confrontare Pij con il prodotto PiPj
Es: 1° insieme di sequenze omologhe
A:
ALASVLIRAILRLYP
B:
ALAVLLNRLILRALP
P(A)= 6/30, P(L) =10/30
P(A,L) = 2/15 > 1/15 = P(A)P(L): sostituzione FAVORITA
2° insieme di sequenze omologhe
A:
LLLLAALLLALLALL
B:
LALLAALLAALLALL
P(A)= 10/30, P(L) =20/30
P(A,L) = 2/15 < 2/9 = P(A)P(L): sostituzione SFAVORITA
Score di sostituzione
Il rapporto rij = Pij/PiPj
determina se la sostituzione i -> j è più o meno frequente di
quanto ci si aspetterebbe casualmente.
Dato un allineamento tra due sequenze:
A: SLDPIKHTYRALMNVDSLRTFPIL
B: SFGIKKHTKLAKLPVDTIKSWPIL
la probabilità di sostituzione A->B sarà data dal prodotto
degli rij : rSS rLF rDG rPI rIK … (indipendenza delle posizioni)
SCORE di SOSTITUZIONE: s(i,j) =int[K log(Pij/PiPj)]
Il logaritmo rende la quantità additiva sulla sequenza
Minima distanza = Massimo score (s)
ESERCIZIO
Calcolare la matrice di sostituzione a partire dalle
seguenti sequenze allineate
ACAGGTGGACCT
ACTGGTCGACTT
CTATATGG
CCGGATCG
Matrici di sostituzione: PAM
In base a questo concetto, differenti matrici possono
essere derivate.
La differenza fondamentale sta nell’insieme di allineamenti
considerati per costruire le matrici.
PAMx: (Point Accepted
mutazionali pari a x%.
Si costruisce la matrice:
Mutation).
A1ij = P(j|i) = N(i,j)/N(i)
per sequenze con 1% di mutazioni.
PAM 1 = Log(A1ij /Pi)
Numero
di
eventi
Matrici di sostituzione: PAM
Per derivare gli score relativi a sequenze in cui siano avvenuti
n eventi mutazionali ogni 100 residui:
Anij=(A1ij)n
Es: n=2 P(i|j) =
Pl P(i|l) P(l|j)
NOTA BENE: n % eventi mutazionali: numero di mutazioni,
NON di residui mutati. Possono essere rimutati
posizioni già mutate. 100 eventi mutazionali
indipendenti ogni 100 residui lasciano alcune
posizioni invariate
PAM n = Log(Anij /Pi)
Relazione tra PAM e identità tra due sequenze
Il numero di eventi mutazionali (PAM) è differente dal
numero di residui differenti tra due sequenze, quando le
mutazioni si accumulano.
PAM10
Matrice molto stringente: nessun valore positivo fuori
diagonale
PAM160
Iniziano valori positivi fuori diagonale: residui con valori di
sostituzione positivi sono detti SIMILI
PAM250
Molto usata
PAM500
Matrici di sostituzione
Le matrici PAM ricavano ipotesi sulle mutazioni in sequenze
lontane a partire dalle mutazioni osservate in sequenze molto
simili. Ipotesi molto stretta.
BLOSUMx: Famiglia di matrici ricavate direttamente da
allineamenti di sequenze con identità maggiore al x%.
Per sequenze molto relate vanno usate PAM basse o BLOSUM
alte. Per sequenze lontane, viceversa.
BLOSUM62
Molto usata
BLOSUM90
BLOSUM30
Distanza tra sequenze
Quali eventi consideriamo?
Mutazione
Delezione e Inserzione
Alcuni amminoacidi possono essere stati deleti o inseriti nel
corso dell’evoluzione
A:
ALASVLIRLIT--YP
B:
ASAVHL---ITRLYP
Score( A, B)   s( A , B )   (3)   (2)
i
i
Il punteggio (negativo) di un gap dipende solo dal numero di
posizioni
(n) = -nd lineare
(n) = -d - (n-1)e affine (d: apertura, e: estensione)
N.B. Tutti i punteggi sono indipendenti dalla posizione
lungo la sequenza
Allineamento tra sequenze
Date due sequenze, qual è l’allineamento a punteggio
massimo?
Soluzione naïf: provare tutti gli allineamenti possibili e
scegliere quello a punteggio maggiore!
Per ogni allineamento, possiamo infatti calcolare il punteggio
tramite la formula
Score( A, B)   s ( Ai , B i )    (ngap )
i
gap
Quanti sono i possibili allineamenti di due sequenze?
Scrivere TUTTI i possibili allineamenti senza gap interni
delle sequenze:
A:
B:
tca
ga
Scrivere TUTTI i possibili allineamenti con gap
delle medesime sequenze
Scrivere i punteggi di allineamento per ognuno degli
allineamenti secondo la seguente matrice con penalità di
gap LINEARE (d=2)
A C T G
A 2
C
T
G
-1 -1 0
2 0 -1
2 -1
2
Quanti sono i possibili allineamenti di due sequenze?
Caso senza Gap interni
--tca
ga---
-tca
ga--
tca
ga-
tca
-ga
Uguale al primo
tca--ga
tca----ga
Date due sequenze di lunghezza m e n, il numero dei possibili
scorrimenti differenti è m +n
Quanti sono i possibili allineamenti di due sequenze?
Caso con gap interni
--tca
ga--gatca
22111
-tca
ga-gtaca
21211
-tca
g-agtcaa
21121
-tca
g--a
gtcaa
21112
t-ca
ga-tgaca
12211
tca
gatgcaa
12121
tca
g-a
tgcaa
12112
tc-a
-gatcgaa
11221
tca
-ga
tcgaa
11212
tca--ga
tcaga
11122
I possibili allineamenti sono uguali ai possibili modi di
intercalare le due sequenze, mantenendo l’ordine
Date due sequenze di lunghezze n e m, i possibili allineamenti
sono (m+n)!/n!m!
Per n=m=80 ho 9•1042 possibili allineamenti !!!!!!!
Algoritmi di programmazione dinamica: idea base
Il calcolo per intero di tutti gli allineamenti è
sovrabbondante
ALSKLASPALSAKDLDSPALS
ALSKIADSLAPIKDLSPASLT
ALSKLASPALSAKDLDSPAL-S
ALSKIADSLAPIKDLSPASLTI due allineamenti sono per la maggior parte uguali.
Lo score è additivo lungo l’allineamento. Col metodo naïf la
prima parte dell’allineamento viene ricalcolata!
Si possono memorizzare i punteggi degli allineamenti parziali
Algoritmi di programmazione dinamica: idea base
Costruire l’allineamento per passi
Date le due sequenze
ALSKLASPALSAKDLDSPALS, ALSKIADSLAPIKDLSPASLT
il miglior allineamento tra le sottostringhe
ALSKLASPA
ALSKIAD
deriva dai migliori allineamenti
ALSKLASP + A
ALSKIA
D
ALSKLASP + A
ALSKIAD
-
ALSKLASPA + ALSKIA
D
Ed è il migliore dei tre! (additività dei punteggi sulle posizioni)
Algoritmo di Needleman e Wunsch
Allineamento globale di sequenze, gap a penalità lineare
Date due sequenze A e B, di lunghezze a e b, definiamo la
matrice F(i,j): punteggio del miglior allineamento tra le
sottosequenze: A1A2A3…….Ai e B1B2B3…….Bj.
Inizializzazione
Iterazione
ALSKLASP A
+
ALSKIA
D
F(i-1,j-1)
Iterazione
F(0,0) = 0
F(i,j) = Max
ALSKLASP A
+
ALSKIAD
F(i-1,j)
F(i-1,j-1) + s(Ai,Bj)
F(i-1,j) - d
F(i,j-1) - d
ALSKLASPA +
ALSKIA
D
F(i,j-1)
F(a,b) è il punteggio del miglior allineamento
Algoritmo di Needleman e Wunsch
Allineare le sequenze
ACTGG e ACCA
0
0
A
C
C
A
0
A
C
T
G
G
Algoritmo di Needleman e Wunsch
A C T
A 2 -1 -1
2 0
C
2
T
G
0
A
0
0
-2
A
-2
C
C
A
C
G
0
-1
-1
2
d=2
T
G
G
Algoritmo di Needleman e Wunsch
A C T
A 2 -1 -1
2 0
C
2
T
G
0
A
0
0
-2
A
-2
2
C
G
0
-1
-1
2
d=2
T
G
G
C
C
0
+2
-2
-2
A
-2
-2
MAX
Algoritmo di Needleman e Wunsch
A C T
A 2 -1 -1
2 0
C
2
T
G
G
0
-1
-1
2
d=2
0
A
C
T
G
G
0
0
-2
-4
-6
-8
-10
A
-2
2
0
-2
-4
-6
C
-4
0
4
2
0
-2
C
-6
-2
2
4
2
0
A
-8
-4
0
2
4
2
Algoritmo di Needleman e Wunsch
0
A
C
T
G
G
0
0
-2
-4
-6
-8
-10
A
-2
2
0
-2
-4
-6
C
-4
0
4
2
0
-2
C
-6
-2
2
4
2
0
A
-8
-4
0
2
4
2
Gap in sequenza 2
0 A C T G G
0 A C C A -
Gap in sequenza 1
0 A C T G G
0 A C C - A
Punteggio
del miglior
allineamento
Match
Complessità computazionale
Numero di operazioni necessario per ottenere un risultato
seguendo un algoritmo
Algoritmo naïf
Date due sequenze di lunghezza n dobbiamo calcolare
(2n)!/(n !)2 punteggi di allineamento.
Ognuno richiede dalle n alle 2n operazioni.
Poiché n !  n n (2 n)1/2 e-n
Complessità  O(22n n 1/2)
Algoritmo Needleman-Wunsch
Vanno calcolati (n +1)2 valori della matrice. Ognuno richiede 4
operazioni:
Complessità  (n 2)
Allineamenti locali
Quelli visti fino ad ora sono allineamenti GLOBALI (tutta la
sequenza)
Se volessimo cercare solo le zone di miglior
sovrapposizione (domini comuni, elementi funzionali
conservati…)?
La strategia è la medesima. Solo si eliminano i punteggi
negativi (meglio riiniziare un allineamento che portarlo a
punteggi negativi)
Algoritmo di Smith e Waterman
Allineamento locale di sequenze, gap a penalità lineare
Date due sequenze A e B, di lunghezze a e b, definiamo la
matrice F(i,j): punteggio del miglior allineamento locale tra le
sottosequenze: A1A2A3…….Ai e B1B2B3…….Bj.
Inizializzazione
F(0,0) =0
F(i-1,j-1) + s(Ai,Bj)
F(i-1,j) - d
F(i,j-1) - d
0
Iterazione
F(i,j) = Max
Iterazione
Il punteggio F(i,j) massimo sulla matrice dà
il miglior allineamento locale
Algoritmo di Smith e Waterman
A C T
A 2 -1 -1
2 0
C
2
T
G
G
0
-1
-1
2
d=2
0
A
C
T
C
T
0
0
0
0
0
0
0
A
0
2
0
0
0
0
T
0
0
2
0
0
2
T
0
0
0
4
2
2
A
0
2
0
2
3
1
A
0
2
1
0
1
2
Algoritmo di Smith e Waterman
0
A
C
T
C
T
0
0
0
0
0
0
0
A
0
2
0
0
0
0
T
0
0
2
0
0
2
T
0
0
0
4
2
2
A
0
2
0
2
3
1
A
0
2
1
0
1
2
Gap in sequenza 2
0 A C T
0 A T T
Gap in sequenza 1
Match
Significatività di un allineamento
Occorrenza
Dato un allineamento (globale o locale) che abbia ottenuto
un punteggio S, come valutare se è significativo?
Come sono distribuiti i punteggi di allineamenti di sequenze
casuali? Con 100,000 allineamenti di sequenze scorrelate e
randomizzate:
Gli allinementi
significativi
sono qua!
Score
Z-score
Z=(S-<S>)/s
S=Punteggio di allineamento
<S>=Media dei punteggi di allineamento su un insieme random
s=Deviazione dei punteggi di allineamento su un insieme
random
Accuratezza dell’allineamento
Z<3
3<Z<6
6<Z<10
Z>10
non significativo
putativamente significativo
possibilmente significativo
significativo
Quanto è affidabile lo Z-score?
Lo Z-score di questo allineamento locale è 7.5 su 54 residui
L’identità è 25.9%.
Le sequenze sono completamente differenti in struttura
secondaria
Citrate synthase (2cts) vs transthyritin (2paba)
E-value
Numero atteso di allineamenti random con punteggio
maggiore o uguale a un punteggio dato (s)
E’ reso possibile dal calcoli statistici
E=Kmn e-ls
m, n: lunghezze delle due sequenze
K, l: Costanti di “scaling”
Il numero di allineamenti random a punteggio maggiore di s
cresce col crescere delle lunghezze delle sequenze (o dei
data base con cui confrontiamo una sequenza) e cala
esponenziamente al crecere di s
E-value
Accuratezza dell’allineamento
La significatività dell’E-value dipende dalla lunghezza della
banca dati considerata. Per un numero di sequenze pari a
quello di SwissProt
E> 10-1
10-1 > E > 10-3
10 -3 > E > 10-8
E < 10-8
non significativo
putativamente significativo
possibilmente significativo
altamente significativo
Programmi di allineamento a coppie: LALIGN
http://www.ch.embnet.org/software/LALIGN_form.html
1BVD.seq
1MWD.seq
Allineamento globale: Sequenze simili
1BVD: mioglobina di capodoglio
1MWD: mioglobina di maiale
L’allineamento corrisponde all’allineamento strutturale?
L’allineamento corrisponde all’allineamento strutturale?
Allineamento locale: Sequenze simili
Allineamento globale: Sequenze differenti
1BVD: mioglobina di capodoglio
1VHB: emoglobina batterica
1BVD.seq
1VHB.seq
L’allineamento corrisponde all’allineamento strutturale?
L’allineamento corrisponde all’allineamento strutturale?
Allineamento locale: Sequenze differenti
Allineamenti Multipli
Il confronto di più sequenze omologhe, può mettere in luce
caratteristiche che non emergono da un allineamento a
coppie.
Allineare molte sequenze
Date M sequenze Ai , si può definire come allineamento
multiplo (globale) ottimo quello che massimizza lo score
S=Si<j S(Ai,Aj)
Metodi esatti
Esistono
metodi
di
programmazione
dinamica
multidimensionale che trovano la soluzione ottima. Sono
troppo lenti
Allineamento progressivo
Allineamenti Multipli Progressivi
Allineamento a coppie e raggruppamento
A
A
C
B
B
C
D
D
Allineamento esatto delle sequenze più simili secondo l’albero
Allineamento progressivo dei profili derivati dagli
allineamenti effettuati
CLUSTALW
http://www.ebi.ac.uk/clustalw/
Allineamento di un insieme di mioglobine (più l’emoglobina)
Sequenze di Mioglobina
Allineamento con CLUSTALW
L’allineamento multiplo migliora l’allineamento tra due
sequenze
1BVD
1VHB
---------VLSEGEWQLVLHVWAKVEAD---VAGHGQDILIRLFKSHPETLEKFDRFKH 48
---------MLDQQTINIIKATVPVLKEHG---VTITTTFYKNLFAKHPEVRPLFDMGR- 47
1BVD
1VHB
LKTEAEMKASEDLKKHGVTVLTALGAILKKKGHHEAELKPLAQSHATKHKIP-----IKY 103
----------QESLEQPKALAMTVLAAAQNIENLPAILPAVKKIAVKHCQAG---VAAAH 94
1BVD
1VHB
LEFISEAIIHVLHSRHPGDFGADAQGAMNKALELFRKDIAAKYKELGYQG-- 153
YPIVGQELLGAIKEVLGDAATDDILDAWGKAYGVIADVFIQVEADLYAQAVE 146
Allineamento estratto dall’allineamento
multiplo effettuato da CLUSTALW
Ricerca di similarità in Banche Dati
Data una sequenza, cercare se esistono sequenze simili in
una banca dati
Di principio si potrebbero fare allineamenti tra la sequenza
target e TUTTE le sequenze
Le sequenze da allineare sono troppe, e il processo non è
fattibile in tempi brevi nemmeno usando l’algoritmo di NW
Si utilizzano algoritmi euristici, che non assicurano il
raggiungimento dell’allineamento ottimo
FASTA
BLAST
FASTA
Data una sequenza (Query), viene divisa in “parole” lunghe
k-tup (generalmente k-tup = 2 per proteine, 6 per DNA)
ADKLPTLPLRLDPTNMVFGHLRI
Parole (indicizzate per posizione):
AD, DK, KL, LP, PT, TL, LP, PR, RL, …,…,
1
2
3
4
5
6
7
8
9
….
Lo stesso elenco di parole indicizzato è compilato per ogni
sequenza (Subject) del data base in cui si cercano sequenze.
E’ molto rapida la ricerca di parole uguali tra Query e
Subject. La differenza degli indici determina la diagonale
FASTA
Query
Identificazione delle identità di “parole”: identità
consecutive danno origine a diagonali più lunghe
FASTA
Query
I punteggi delle regioni più lunghe sono valutati con una
matrice di score (PAM o BLOSUM)
FASTA
Query
Vengono cercate regioni ad alta similarità su diagonali
vicine
FASTA
Query
Si procede ad un allineamento esatto (Smith-Waterman)
su una banda stretta attorno alla diagonale di maggior
similarità (solitamente banda larga attorno ai 32 residui)
Sequence similarity with FASTA
BLAST
Data un data base di sequenze, questo viene indicizzato:
per ogni tripletta di residui consecutivi si memorizza in quali
sequenze e in quali posizioni questa tripletta viene trovata.
AAA
AAC
AAD
ACA
...
...
...
BLAST
Data una sequenza (Query), viene divisa in “parole” lunghe
W (generalmente W = 3 per proteine)
LSHLPTLPLRLDPTNMVFGHLRI
LSH, SHL, HLP, LPT, PTL, TLR, …,…,
Per ognuna vengono generate le parole affini secondo la
BLOSUM62: parole con punteggio > T (T = 11--13)
LSH
ISH
MSH
VSH
LAH
LTH
LNH
16
14
14
13
13
13
13
BLAST
Per ognuna delle parole affini vengono recuperate le
sequenze del data base che la contengono (secondo
l’indicizzazione)
La corrispondenza viene estesa (senza gap) a destra e a
sinistra fino a che lo score rimane superiore a una soglia S
Sequence similarity with BLAST (Basic Local Alignment
Search Tool)
FASTA
http://www.ebi.ac.uk/fasta33/
BLAST
http://www.ncbi.nlm.nih.gov/BLAST/
Allineamento di tutte le sequenze
ATTENZIONE: Non è allineamento multiplo ottimale
Profilo di sequenza
1
2
3
4
5
6
7
8
9
10
Y
Y
Y
Y
Y
Y
Y
G
T
T
K
R
R
R
R
K
R
Y
K
K
D
D
D
D
D
D
D
G
G
G
Y
Y
Y
Y
Y
Y
Y
F
Y
Y
H
Q
Q
V
Q
N
Q
G
G
G
0
0
0
0
0
0
0
40
0
0
0
0
0
0
50
0
0
0
10
0
0
0
70
0
0
30
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
10
0
0
0
0
0
0
0
0
0
0
0
0
0
0
90
0
0
0
0
0
30
10
0
0
0
0
10
0
40
0
0
0
10
0
0
S
T
S
S
F
T
T
F
F
G
G
D
D
D
D
D
H
D
L
L
L
0
0
0
0
0
0
0
0
33
0
0 100
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
33
0
33
0
0
0
0
0
0
0
0
0
60
0
0
0
10
0
0
30
0
0
0
0
0
0
0
0
0
0
K
Q
H
H
Q
Q
H
I
I
I
K
K
K
K
K
K
K
K
K
K
K
K
K
K
K
K
K
N
N
N
G
G
G
G
G
N
A
T
T
T
E
D
E
E
S
E
D
E
E
E
0
0
0
0
0
0
0
0
0
0
0
0
30
0
10 100
30
0
0
0
0
0
0
0
0
0
30
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
70
0
0
0
30
0
0
0
0
0
0
0
0
10
0
0
0
0
50
0
0
0
0
0
10
0
0
0
0
30
0
0
0
0
0
20
70
0
0
0
0
0
0
0
0
0
0
0
10
0
0
0
0
L
L
L
L
L
S
L
T
T
T
T
T
T
K
K
K
Position
A 0
C 0
D 0
E 0
F 0
G 10
H 0
K 0
I 0
L 0
M 0
N 0
P 0
Q 0
R 0
S 0
T 20
V 0
W 0
Y 70
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0 100
0
0
0
0
0
0
60
0
0
0
0
0
0
0
0
0
0
0
0
0
0
10
0
0
30 100
0
0
0
0
0
0
0
0
0
0
Utilità del profilo di sequenza
Il profilo di sequenza dà una descrizione complessiva di tutte
le sequenze:
evidenzia le zone più conservate o le mutazioni più frequenti
posizione per posizione
Allineare una sequenza contro un profilo
I parametri di un allineamento sono generalmente identici
per tutte le posizioni. Allineare contro un profilo pesa
differentemente le mutazioni nelle differenti posizioni
PSI-BLAST
http://www.ncbi.nlm.nih.gov/BLAST/
Sequenza
Profilo delle
sequenze
rintracciate
BLAST
Data Base
PSI-BLAST
Fino a convergenza
The design of PSI-BLAST
(1) PSI-BLAST takes as an input a single protein sequence and compares
it to a protein database, using the gapped BLAST program
(2) The program constructs a multiple alignment, and then a profile,
from any significant local alignments found. The original query
sequence serves as a template for the multiple alignment and profile,
whose lengths are identical to that of the query. Different numbers
of sequences can be aligned in different template positions
(3) The profile is compared to the protein database, again seeking local
alignments. After a few minor modifications, the BLAST algorithm
can be used for this directly.
(4) PSI-BLAST estimates the statistical significance of the local
alignments found. Because profile substitution scores are
constructed to a fixed scale, and gap scores remain independent of
position, the statistical theory and parameters for gapped BLAST
alignments remain applicable to profile alignments.
(5) Finally, PSI-BLAST iterates, by returning to step (2), an arbitrary
number of times or until convergence.
Motivi di sequenza
Da allineamenti locali e considerazioni strutturali possono
essere derivati motivi sequenziali importanti.
Espressioni regolari
Allineando i seguenti frammenti che coordinano un atomo di Zn
C
C
C
D
C
C
H
H
H
H
H
H
C
C
C
C
C
C
I
L
I
L
I
L
C
C
C
C
D
C
R
K
S
T
S
K
I
I
L
I
I
I
C
C
C
C
C
C
Deriviamo la seguente espressione regolare
[CD]-H-C-[IL]-[CD]-[RKST]-[IL]-C
Ricerca di motivi
Possiamo cercare l’espressione regolare in diverse proteine
[CD]-H-C-[IL]-[CD]-[RKST]-[IL]-C
..ALCPCHCLCRICPLIY..
..KFRLCWCLCKICLKDF..
..GGPLCHCICSLDASDQ..
..FLPRCHCLCTICPIYL..
..WERWDHCIDSICLKDE..
..LPPICHCLCKICFGLK..
Yes
No
No
Yes
Yes
Yes
PROSITE
http://www.expasy.org/prosite/
PROSITE
Problemi….
Espressioni regolari
La risposta dello scan è sempre Sì o No
..ALCPCHCLCRICPLIY..
..è riconosciuto come legante Zn, così come...
..WERWDHCIDSICLKDE..
…anche se l’occorrenza di due acidi aspartici come
leganti non è mai osservata
Allineamenti
I parametri di sostituzione, di apertura di gap, ecc.. sono
indipendenti dalla posizione, anche se in realtà esistono
grossi vincoli all’interno di una stessa famiglia
Scarica

Lezione3 - Università di Bologna