Fisica Computazionale applicata alle Macromolecole

Pier Luigi Martelli

Università di Bolognagigi@biocomp.unibo.it

051 2094005338 3991609

Metodi di allineamento

Ricordiamo...Ricordiamo...

La struttura di una proteina in ambiente fisiologico dipende solo dalla sua sequenza amminoacidicaEsperimento di Anfinsen

Differenti sequenze amminoacidiche assumono in ambiente fisiologico lo stesso foldBanche dati CATH e SCOP: Organizzazione gerarchica

La funzione dipende dalla struttura, sebben questa relazione non sia rigorosaLa funzione dipende da tutta la struttura, non solo dal fold

ProblemaProblema

Determinare il fold a partire dalla sequenza amminoacidica

Allineare le sequenze in modo da riprodurre l’allineamento generato dalla sovrapposizione delle loro due strutture

StrategiaStrategia

Esaminare come le sequenze hanno avuto origine

Perché nei vari organismi esistono sequenze differenti per una unica funzione?

Evoluzione Molecolare e omologiaEvoluzione 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 omologiaEvoluzione 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à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à strutturaleIdentità di sequenza e identità strutturale

Quando la similarità di sequenza implica similiarità strutturale?

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à strutturaleIdentità di sequenza e identità strutturale

0.0

2.5

0.5

1.5

2.0

1.0

100 050

Rm

sd o

f ba

ckbo

ne a

tom

s in

cor

e

Percent identical residues in core

0.0

1.0

0.2

0.6

0.8

0.4

100 050Percent identical residues in core

Fra

ctio

n of

res

idue

s in

cor

e w

ith

RM

SD

< 0

.1 n

m

Fino a quanto due sequenze simili danno strutture uguali?

•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

.

0

20

40

60

80

100

0 50 100 150 200 250

identity

Numero di residui allineati

Identi

tà d

i se

quenza

(%

)

Identità di sequenza implica identità strutturale

Identità di sequenza e identità strutturaleIdentità di sequenza e identità strutturale

Identità di sequenza NON implica identità strutturale

Rost B (1999). The twilight zone of protein alignments. Protein Engineering 12, 85-94.

.

Identità di sequenza e identità strutturaleIdentità di sequenza e identità strutturale

Quindi due sequenze più lunghe di 100 residui, che condividano il 30 % dei residui, hanno struttura simile

Per sequenze più corte la percentuale di identità deve essere più alta

Questo NON implica che sequenze con identità minore abbiano strutture differentiEsempio: Mioglobina di capodoglio e emoglobina batterica:

RMSD = 0.19 nm, Identità: 14%

Identità di sequenza e identità strutturaleIdentità di sequenza e identità strutturale

Per sequenze più lunghe di 100 residui

Midnight zone:

contiene la maggior parte delle proteine

strutturalmente simili

Twilight zone:

alto numero di falsi positivi

(sequenza similestruttura diversa)

Safe zone:

nessun falso positivotutte le sequenze

simili hanno la stessa struttura

20% 30%

Percentuale di identità

Allineamento di sequenzeAllineamento 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 per validare la significativicità dell’allineamento

Distanza tra sequenzeDistanza tra sequenze

Quali eventi consideriamo?

MutazioneVa definito un punteggio per la sostituzione dell’amminoacido i con l’amminoacido j

Matrici di sostituzione s(i,j)

A: ALASVLIRLITRLYP B: ASAVHLNRLITRLYP

),(),( ii BAsBAScore

La matrice di sostituzione riflette se una mutazione è mediamente compatibile col folding e col mantenimento della funzione

Derivazione degli score da allineamenti di Derivazione degli score da allineamenti di sequenze omologhesequenze 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: ALASVLIRAILRLYP B: 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

Qual è la probabilità che la sostituzione i->j sia casuale (e quindi non significativa)?

La sostituzione è significativa?La sostituzione è significativa?

Es: 1° insieme di sequenze omologhe

A: ALASVLIRAILRLYP B: ALAVLLNRLILRALP

La probabilità che questa sostituzione sia casuale dipende dalle frequenze di occorrenza dei singoli amminoacidi Pi e Pj

2° insieme di sequenze omologheA: LLLLAALLLALLALL B: LALLAALLAALLALL

P(A,L)= 2/15 in entrambi i casi. Sono ugualmente significativi?

Per determinare il grado di “non casualità” della sostituzione bisogna confrontare Pij con il prodotto PiPj

Es: 1° insieme di sequenze omologheA: ALASVLIRAILRLYP B: ALAVLLNRLILRALP

P(A)= 6/30, P(L) =10/30P(A,L) = 2/15 > 1/15 = P(A)P(L): sostituzione FAVORITA

2° insieme di sequenze omologheA: LLLLAALLLALLALL B: LALLAALLAALLALL

P(A)= 10/30, P(L) =20/30P(A,L) = 2/15 < 2/9 = P(A)P(L): sostituzione SFAVORITA

Sostituzione iA -> jB casuale significa che i 2 eventi:E1 = (i in A) e E2 = (j in B) sono INDIPENDENTI

Confronto con l’ipotesi di indipendenzaConfronto con l’ipotesi di indipendenza

SCORE di SOSTITUZIONE: s(i,j) =int[K log(Pij/PiPj)]

Il logaritmo rende la quantità additiva sulla sequenza

Minima distanza = Massimo score (s)

Score di sostituzioneScore 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: SLDPIKHTYRALMNVDSLRTFPILB: SFGIKKHTKLAKLPVDTIKSWPIL

la probabilità di sostituzione A->B sarà data dal prodotto degli rij : rSS rLF rDG rPI rIK … (indipendenza delle posizioni)

ESERCIZIOESERCIZIO

Calcolare la matrice di sostituzione a partire dalle seguenti sequenze allineate

ACAGGTGGACCTACTGGTCGACTT

CTATATGGCCGGATCG

Matrici di sostituzione: PAMMatrici 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 Mutation). Numero di eventi mutazionali pari a x%. Si costruisce la matrice:

A1ij = P(j|i) = N(i,j)/N(i)

per sequenze con 1% di mutazioni.

PAM 1 = Log(A1ij /Pi)

Anij=(A1

ij)n

Es: n=2 P(i|j) = lP(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)

Matrici di sostituzione: PAMMatrici di sostituzione: PAM

Per derivare gli score relativi a sequenze in cui siano avvenutin eventi mutazionali ogni 100 residui:

Relazione tra PAM e identità tra due sequenzeRelazione 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.

PAM10PAM10

Matrice molto stringente: nessun valore positivo fuori diagonale

PAM160PAM160

Iniziano valori positivi fuori diagonale: residui con valori di sostituzione positivi sono detti SIMILI

PAM250PAM250

Molto usata

PAM500PAM500

Matrici di sostituzioneMatrici 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.

BLOSUM62BLOSUM62

Molto usata

BLOSUM90BLOSUM90

BLOSUM30BLOSUM30

Distanza tra sequenzeDistanza tra sequenze

Quali eventi consideriamo?

MutazioneDelezione e InserzioneAlcuni amminoacidi possono essere stati deleti o inseriti nel corso dell’evoluzione

A: ALASVLIRLIT--YP B: ASAVHL---ITRLYP

)2()3(),(),( ii BAsBAScoreIl 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 sequenzeAllineamento 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

)(),(),( gapgapi

ii nBAsBAScore

Quanti sono i possibili allineamenti di due Quanti sono i possibili allineamenti di due sequenze?sequenze?

Scrivere TUTTI i possibili allineamenti senza gap interni delle sequenze:

A: tcaB: 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 -1 -1 0C 2 0 -1T 2 -1G 2

Quanti sono i possibili allineamenti di due Quanti sono i possibili allineamenti di due sequenze?sequenze?

Caso senza Gap interni

--tca -tca tca tca tca- tca--ga--- ga-- ga- -ga --ga ---ga

Date due sequenze di lunghezza m e n, il numero dei possibili scorrimenti differenti è m +n

Uguale al primo

Caso con gap interni

--tca -tca -tca -tca t-caga--- ga-- g-a- g--a ga--gatca gtaca gtcaa gtcaa tgaca22111 21211 21121 21112 12211

tca tca tc-a tca tca-ga- g-a -ga- -ga --gatgcaa tgcaa tcgaa tcgaa tcaga12121 12112 11221 11212 11122

Quanti sono i possibili allineamenti di due Quanti sono i possibili allineamenti di due sequenze?sequenze?

I possibili allineamenti sono uguali ai possibili modi di intercalare le due sequenze, mantenendo l’ordineDate due sequenze di lunghezze n e m, i possibili allineamenti sono (m+n)!/n!m!

Per n=m=80 ho 9•1042 possibili allineamenti !!!!!!!

Il calcolo per intero di tutti gli allineamenti è sovrabbondante

ALSKLASPALSAKDLDSPALSALSKIADSLAPIKDLSPASLT

ALSKLASPALSAKDLDSPAL-SALSKIADSLAPIKDLSPASLT-

Algoritmi di programmazione dinamica: idea Algoritmi di programmazione dinamica: idea basebase

I 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

Costruire l’allineamento per passiDate le due sequenze

ALSKLASPALSAKDLDSPALS, ALSKIADSLAPIKDLSPASLT

il miglior allineamento tra le sottostringhe

ALSKLASPA ALSKIAD

deriva dai migliori allineamenti

ALSKLASP A ALSKLASP A ALSKLASPA - ALSKIA D ALSKIAD - ALSKIA D

Ed è il migliore dei tre! (additività dei punteggi sulle posizioni)

Algoritmi di programmazione dinamica: idea Algoritmi di programmazione dinamica: idea basebase

+ + +

Algoritmo di Needleman e WunschAlgoritmo di Needleman e Wunsch

Allineamento globale di sequenze, gap a penalità lineareDate 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 F(0,0) = 0

F(i-1,j-1) + s(Ai,Bj)Iterazione F(i,j) = Max F(i-1,j) - d

F(i,j-1) - d

ALSKLASP A ALSKLASP A ALSKLASPA - ALSKIA D ALSKIAD - ALSKIA D F(i-1,j-1) F(i-1,j) F(i,j-1)

Iterazione F(a,b) è il punteggio del miglior allineamento

+ + +

Algoritmo di Needleman e WunschAlgoritmo di Needleman e Wunsch

Allineare le sequenze

ACTGG e ACCA

0 A C T G G

0 0

A

C

C

A

Algoritmo di Needleman e WunschAlgoritmo di Needleman e Wunsch

A C T GA 2 -1 -1 0C 2 0 -1T 2 -1G 2

d = 2

0 A C T G G

0 0 -2

A -2

C

C

A

Algoritmo di Needleman e WunschAlgoritmo di Needleman e Wunsch

A C T GA 2 -1 -1 0C 2 0 -1T 2 -1G 2

d = 2

0 A C T G G

0 0 -2

A -2 2

C

C

A

0+2

-2-2

-2 -2 MAX

Algoritmo di Needleman e WunschAlgoritmo di Needleman e Wunsch

A C T GA 2 -1 -1 0C 2 0 -1T 2 -1G 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 WunschAlgoritmo di Needleman e Wunsch

0 A C T G G0 A C C A -

0 A C T G G0 A C C - A

Gap in sequenza 2 Gap in sequenza 1 Match

Punteggio del miglior allineamento

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

Complessità computazionaleComplessità computazionale

Numero di operazioni necessario per ottenere un risultato seguendo un algoritmo

Algoritmo naïfDate 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-WunschVanno calcolati (n +1)2 valori della matrice. Ognuno richiede 4 operazioni:Complessità (n 2)

Allineamenti localiAllineamenti 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 WatermanAlgoritmo di Smith e Waterman

Allineamento locale di sequenze, gap a penalità lineareDate 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)Iterazione F(i,j) = Max F(i-1,j) - d

F(i,j-1) - d 0

Iterazione Il punteggio F(i,j) massimo sulla matrice dà il miglior allineamento locale

Algoritmo di Smith e WatermanAlgoritmo di Smith e Waterman

A C T GA 2 -1 -1 0C 2 0 -1T 2 -1G 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 WatermanAlgoritmo 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

0 A C T 0 A T T

Gap in sequenza 2 Gap in sequenza 1 Match

Gli allinementi significativi sono qua!

Significatività di un allineamentoSignificatività di un allineamento

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:

Score

Occ

orre

nza

Z=(S-<S>)/s

S=Punteggio di allineamento<S>=Media dei punteggi di allineamento su un insieme randoms=Deviazione dei punteggi di allineamento su un insieme random

Accuratezza dell’allineamento

Z<3 non significativo3<Z<6 putativamente significativo6<Z<10 possibilmente significativoZ>10 significativo

Z-scoreZ-score

Lo Z-score di questo allineamento locale è 7.5 su 54 residuiL’identità è 25.9%. Le sequenze sono completamente differenti in struttura secondaria

Citrate synthase (2cts) vs transthyritin (2paba)

Quanto è affidabile lo Z-score?Quanto è affidabile lo Z-score?

E-valueE-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-s

m, n: lunghezze delle due sequenzeK, : 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

Accuratezza dell’allineamentoLa significatività dell’E-value dipende dalla lunghezza della banca dati considerata. Per un numero di sequenze pari a quello di SwissProt

E> 10-1 non significativo10-1 > E > 10-3 putativamente significativo10 -3 > E > 10-8 possibilmente significativoE < 10-8 altamente significativo

E-valueE-value

Programmi di allineamento a coppie: LALIGNProgrammi di allineamento a coppie: LALIGNhttp://www.ch.embnet.org/software/LALIGN_form.html

1BVD.seq

1MWD.seq

Allineamento globale: Sequenze similiAllineamento globale: Sequenze simili

1BVD: mioglobina di capodoglio1MWD: mioglobina di maiale

L’allineamento corrisponde all’allineamento L’allineamento corrisponde all’allineamento strutturale?strutturale?

L’allineamento corrisponde all’allineamento L’allineamento corrisponde all’allineamento strutturale?strutturale?

Allineamento locale: Sequenze similiAllineamento locale: Sequenze simili

Allineamento globale: Sequenze differentiAllineamento globale: Sequenze differenti

1BVD.seq

1VHB.seq

1BVD: mioglobina di capodoglio1VHB: emoglobina batterica

L’allineamento corrisponde all’allineamento L’allineamento corrisponde all’allineamento strutturale?strutturale?

L’allineamento corrisponde all’allineamento L’allineamento corrisponde all’allineamento strutturale?strutturale?

Allineamento locale: Sequenze differentiAllineamento locale: Sequenze differenti

Allineamenti MultipliAllineamenti Multipli

Il confronto di più sequenze omologhe, può mettere in luce caratteristiche che non emergono da un allineamento a coppie.

Allineare molte sequenzeDate M sequenze Ai , si può definire come allineamento multiplo (globale) ottimo quello che massimizza lo score

S=i<j S(Ai,Aj)

Metodi esattiEsistono metodi di programmazione dinamica multidimensionale che trovano la soluzione ottima. Sono troppo lenti

Allineamento progressivo

Allineamenti Multipli ProgressiviAllineamenti Multipli Progressivi

Allineamento a coppie e raggruppamentoABCD

ACBD

Allineamento esatto delle sequenze più simili secondo l’albero

Allineamento progressivo dei profili derivati dagli allineamenti effettuati

CLUSTALWCLUSTALW

http://www.ebi.ac.uk/clustalw/

Allineamento di un insieme di mioglobine (più Allineamento di un insieme di mioglobine (più l’emoglobina)l’emoglobina)

Sequenze di Mioglobina

Allineamento con CLUSTALW

1BVD ---------VLSEGEWQLVLHVWAKVEAD---VAGHGQDILIRLFKSHPETLEKFDRFKH 481VHB ---------MLDQQTINIIKATVPVLKEHG---VTITTTFYKNLFAKHPEVRPLFDMGR- 47

1BVD LKTEAEMKASEDLKKHGVTVLTALGAILKKKGHHEAELKPLAQSHATKHKIP-----IKY 1031VHB ----------QESLEQPKALAMTVLAAAQNIENLPAILPAVKKIAVKHCQAG---VAAAH 94

1BVD LEFISEAIIHVLHSRHPGDFGADAQGAMNKALELFRKDIAAKYKELGYQG-- 1531VHB YPIVGQELLGAIKEVLGDAATDDILDAWGKAYGVIADVFIQVEADLYAQAVE 146

L’allineamento multiplo migliora l’allineamento L’allineamento multiplo migliora l’allineamento tra due sequenzetra due sequenze

Allineamento estratto dall’allineamento multiplo effettuato da CLUSTALW

Ricerca di similarità in Banche DatiRicerca 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

FASTABLAST

FASTAFASTA

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

FASTAFASTA

Query

Sub

ject

Identificazione delle identità di “parole”: identità consecutive danno origine a diagonali più lunghe

FASTAFASTA

Query

Sub

ject

I punteggi delle regioni più lunghe sono valutati con una matrice di score (PAM o BLOSUM)

FASTAFASTA

Query

Sub

ject

Vengono cercate regioni ad alta similarità su diagonali vicine

Query

Sub

ject

FASTAFASTA

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

BLASTBLAST

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.AAAAACAADACA.........

BLASTBLAST

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 16 ISH 14MSH 14VSH 13LAH 13LTH 13LNH 13

BLASTBLAST

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)

http://www.ebi.ac.uk/fasta33/

FASTAFASTA

BLASTBLAST

http://www.ncbi.nlm.nih.gov/BLAST/

Allineamento di tutte le sequenze Allineamento di tutte le sequenze

ATTENZIONE: Non è allineamento multiplo ottimale

1 Y K D Y H S - D K K K G E L - -2 Y R D Y Q T - D Q K K G D L - -3 Y R D Y Q S - D H K K G E L - -4 Y R D Y V S - D H K K G E L - -5 Y R D Y Q F - D Q K K G S L - -6 Y K D Y N T - H Q K K N E S - -7 Y R D Y Q T - D H K K A D L - -8 G Y G F G - - L I K N T E T T K 9 T K G Y G F G L I K N T E T T K10 T K G Y G F G L I K N T E T T K

A 0 0 0 0 0 0 0 0 0 0 0 10 0 0 0 0C 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0D 0 0 70 0 0 0 0 60 0 0 0 0 20 0 0 0E 0 0 0 0 0 0 0 0 0 0 0 0 70 0 0 0F 0 0 0 10 0 33 0 0 0 0 0 0 0 0 0 0G 10 0 30 0 30 0 100 0 0 0 0 50 0 0 0 0H 0 0 0 0 10 0 0 10 30 0 0 0 0 0 0 0K 0 40 0 0 0 0 0 0 10 100 70 0 0 0 0 100I 0 0 0 0 0 0 0 0 30 0 0 0 0 0 0 0L 0 0 0 0 0 0 0 30 0 0 0 0 0 0 0 0M 0 0 0 0 0 0 0 0 0 0 0 0 0 60 0 0N 0 0 0 0 10 0 0 0 0 0 30 10 0 0 0 0P 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0Q 0 0 0 0 40 0 0 0 30 0 0 0 0 0 0 0R 0 50 0 0 0 0 0 0 0 0 0 0 0 0 0 0S 0 0 0 0 0 33 0 0 0 0 0 0 10 10 0 0T 20 0 0 0 0 33 0 0 0 0 0 30 0 30 100 0V 0 0 0 0 10 0 0 0 0 0 0 0 0 0 0 0W 0 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0Y 70 0 0 90 0 0 0 0 0 0 0 0 0 0 0 0

Position

Profilo di sequenzaProfilo di sequenza

Utilità del profilo di sequenzaUtilità 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-BLASTPSI-BLAST

http://www.ncbi.nlm.nih.gov/BLAST/

Sequenza

Data Base

BLASTProfilo delle sequenze

rintracciate

PSI-BLAST

Fino a convergenza

(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.

The design of PSI-BLAST

Motivi di sequenzaMotivi 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 H C I C R I C C H C L C K I C C H C I C S L C D H C L C T I C C H C I D S I C C H C L C K I C

[CD]-H-C-[IL]-[CD]-[RKST]-[IL]-C

Deriviamo la seguente espressione regolare

Possiamo cercare l’espressione regolare in diverse proteine

..ALCPCHCLCRICPLIY.. ..KFRLCWCLCKICLKDF.. ..GGPLCHCICSLDASDQ.. ..FLPRCHCLCTICPIYL.. ..WERWDHCIDSICLKDE.. ..LPPICHCLCKICFGLK..

[CD]-H-C-[IL]-[CD]-[RKST]-[IL]-C

YesNoNoYesYesYes

Ricerca di motiviRicerca di motivi

PROSITEPROSITE

http://www.expasy.org/prosite/

PROSITEPROSITE

Problemi….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