Appunti Laboratorio di bioinformatica

MATRICI DI PUNTEGGIO

Problema dell’algoritmo Needleman-Wunsch (NW): non tiene conto della penalizzazione

degli indel.

Algoritmo Waterman-Smith (SW) introduce una funzione di penalizzazione.

Serve un sistema di pesatura degli indel: w(k) = g + e(k-1)

Ovvero, il peso w di una indel di lunghezza k dipende dalla penalizzazione per l’apertura

di una singola indel (g) e dalla penalizzazione per l’allungamento (e)

SW si può usare per allineamento locale e globale.

S = score dell’allineamento (dipende dal metodo di allineamento e non è assoluto)

Per allineamento locale trova le sottosequenze (regioni) di due sequenze che si allineano

in modo ottimale. Per permettere che faccia allineamenti locali basta introdurre fra i casi

possibili S(i,j) = 0, ovvero il caso in cui l’allineamento globale è negativo. In pratica cerco

la cella con il valore massimo assoluto e poi si procede a ritroso.

L’allineamento locale è molto utilizzato per ricerche su database e per trovare domini

all’interno delle sequenze.

Per l’allineamento globale si tiene conto dei possibili modi per arrivare alla casella (i,j). Il

punteggio che si otterrà in quella casella dipende da questi modi:

- Ci si può muovere in diagonale (no indel), il punteggio sarà dato dal punteggio

della casella di partenza + punteggio della casella (i,j) secondo la matrice di

inizializzazione

- Ci si può muovere in verticale o orizzontale, inserirò indel nella sequenza i e j. Il

punteggio sarà dato da “punteggio della casella di partenza” –“ funzione di

penalizzazione w(k)”

Alla fine scelgo il percorso che dà il punteggio migliore.

L’allineamento globale può mascherare la corrispondenza fra zone somiglianti

Ottenuto un punteggio di allineamento S, come possa capire se le due sequenze sono

omologhe? Che probabilità ho di ottenere il punteggio S “per caso”?

Per allineamento globale, la seq A è mantenuta fissa; la B è “anagrammata” n volte

ed ogni volta globalmente allineata ad A, calcolando lo score Si per l’allineamento i.

Si si distribuisce su una curva di cui si calcola la media µ e la deviazione standard sigma,

Si definisce allora la distanza Z del punteggio S dell’allineamento dalla media in termini di

dev. Standard: Z = (S - µ)/sigma

Uno Z-score 0 = significa che la somiglianza osservata non è migliore rispetto alla media

di permutazioni casuali della sequenza, e può anche essere casuale.

Si assume una distribuzione normale, ma dato che questa non può essere corretta, Z

deve essere considerato come una soglia di significatività.

Per allineamento locale, date due sequenze casuali, di lunghezza m e n, sia E il

numero atteso di sottosequenze allineate localmente senza indel che ottengono un

punteggio S>= x

E(S>= x) = K * m * n * e ^lambda*x

Dove lambda dipende dalla composizione e K dipende dalla matrice di punteggio

Partendo da questa formula posso calcolare la probabilità di osservare un allineamento

locale con punteggio S>= x: p(S >= x) = 1 – exp(K * m * n * e^lambda * x)

In pratica:

Allineamo localmente le seq

otteniamo il punteggio x

calcoliamo p(S>=x)nell’ipotesi che due seq non siano omologhe

Se p < soglia (es 1%), possiamo ritenerci confidenti che siano omologhe

Occorre sempre la significatività biologica, oltre che statistica

Le matrici di punteggio (o di sostituzione) sono matrici 20x20. Sono matrici

simmetriche A->B = B->A (non sappiamo evolutivamente chi si è trasformato dei due).

Tuttavia è difficile stabilire dei criteri oggettivi per le somiglianze fisico-chimiche degli aa.

Non è possibile sapere quali delle varie caratteristiche fisico-chimiche sono più importanti

per le proteine.

Vogliamo ottenere delle matrici di punteggio che assegna i punti e tollera le discordanze

(come PAM250) ma anche matrici di punteggio che siano via via meno tolleranti con i

disallineamenti (come PAM10)

PAM: Point Accepted Mutation

Mutazione puntuale accettata: E’ l’evento in cui il DNA subisce una mutazione che

produce il cambiamento di un amminoacido e tale mutazione diviene prevalente in una

specie.

Le matrici PAM sono basate su allineamenti globali di proteine strettamente correlate.

es. PAM 1 è la matrice calcolata dal confronto di seq con non più di 1% di divergenza (un

cambiamento si è verificato su una lunghezza di 100 aa), PAM 250, 250 sostituzioni si

sono verificate tra due proteine su una lunghezza di 100 aa, nel passo evolutivo che

essa rappresenta.

In pratica le PAM rappresentano la distanza evolutiva fra due sequenze.

Una matrice di sostituzione contiene valori proporzionali alla probabilità che

l’amminoacido muti nell’amminoacido j per tutte le coppie possibili di aa.

Le matrici di sostituzione sono costruite assemblando un campione ampio e diversificato

di allineamenti a coppie (o allineamenti multipli di sequenza) di aminoacidi.

Le matrici di sostituzione dovrebbero riflettere la probabilità reale di mutazione in un

periodo di evoluzione.

I due tipi principali di matrici di sostituzione sono PAM e BLOSUM

PAM

Con (PAM1)^n si può simulare il passaggio di n passi di evoluzione.

PAM0 significa che non si sono verificati passi d’evoluzione, dunque non è cambiato nulla

(PAM1)^2000 = PAM2000 ovvero il caso. Si arriva alla situazione in cui la probabilità

presente nella matrice converge alla frequenza osservata.

Assegnazione di punteggi

Dayhoff ha definito il punteggio per due generici residui i, j come

qi,j = probabilità che l’aa i venga sostituito da j (prob di omologia in base alle sostituzioni

osservate)

pi,j = Probabilità di trovare casualmente l’appaiamento i,j (prodotto delle probabilità di

prodotto delle

trovare un ‘i’ e quella di trovare un ‘j’ in una qualunque sequenza, cioè

frequenze)

Il valore viene quindi convertito in log e moltiplicato per 10: Si,j = 10 * log(qi,j/pi,j)

BLOSUM (BLOck SUbstitution Matrix)

Le matrici BLOSUM sono basate su allineamenti locali, tratti dal database BLOCKS che

raggruppa blocchi (regioni) di allineamenti locali di sequenze lontanamente correlate.

BLOSUM62 è una matrice calcolata a partire da seq con divergenza minore del 62%, è il

default per BLAST

Il metodo di calcolo degli score è simili a quello per le PAM ma si usa lambda = 2 invece

che 10

(in BLOSUM il range è 90-45, contro 30-250 per le PAM)

Si,j = (1/lambda) log (pi,j/(qi*qj))

PAM si basa su principi evoluzionistici, BLOSUM si basa sull’osservazione di allineamenti

reali, senza fare assunzioni di omologia

BLAST (Basic Local Alignment Search Tool)

Gli algoritmi appena visti (WS, NV) sono precisi ma lenti. Occorrono metodi euristici che

trovano soluzioni approssimate ma vicine a quella ottimale in tempi brevi.

BLAST permette un confronto rapido tra una sequenza query e il contenuto di un

database. E’ un algoritmo veloce, accurato, web-accessibile

I suoi utilizzi comprendono:

- Individuare ortologhi e paraloghi

- Scoperta di nuovi geni o proteine

- Scoperta di varianti di geni o proteine noti

- Lo studio delle expressed sequence tags (EST)

- Lo studio di struttura e funzione delle proteine

FASI DELLA RICERCA BLAST:

Scegli la sequenza: può essere inserita in formato FASTA o con RefSeq

Selezionare il tipo di programma BLAST (Nucleotide BLAST/blastn , Protein

BLAST/blastp, blastx ovvero BLAST tradotto n->p, tblastn ovvero BLAST tradotto p->n)

Scegliere il database: nr = non ridondante (database più generale, ritorna una

sequenza e diversi riferimenti in database in cui la stessa è presente); refseq = solo

sequenze con codice refseq; dbest = database di EST; dbsts = database di sequenze

localizzate; gss = genome sequence surveys (BAC, Yac, ecc); Altri… pdb, genomi

completi, solo sequenze oggetto di brevetti (pat) ecc. ecc.

Parametri opzionali: scegliere organismo di ricerca, attivare filtri, modificare matrice di

punteggio, cambiare il valore minimo di affidabilità dei risultati, modificare la dimensione

della parola (Word size)

BLAST è una approssimazione euristica per l’allineamento locale. Esamina solo una parte

dello spazio di ricerca

"L'idea centrale dell’algoritmo di BLAST è di limitare l'attenzione a coppie di segmenti in

cui si allineano parole di lunghezza w con un punteggio di almeno T.”

Fase 1: compilare una lista di coppie di parole (lunghezza w = 3) con un punteggio oltre la

soglia T (se T = 11, tutte le coppie di parole il cui allineamento ha dato come risultato x <

11, verranno escluse dai passi successivi)

Fase 2: i database sono indicizzati per la ricerca di parole di lunghezza W e si cerca fra

queste quelle che corrispondono alla lista compilata (con punteggio maggiore della soglia

T)

Fase 3: quando si riesce a trovare una corrispondenza (parola con punteggio > T al

database), si estende l’allineamento in entrambe le direzioni. Si tiene traccia del

punteggio e ci si ferma quando il punteggio è inferiore a una certa soglia

Nella versione originale di BLAST (1990) ciascun hit è esteso in entrambe le direzioni.

Nella versione migliorata, dal 1997, sono necessari due hit vicini (entro una distanza A).

In questo modo le estensioni avvengono meno frequentemente ma si ottiene un notevole

risparmio di tempo

Si possono personalizzare i parametri sia per le soglie sia per le dimensioni delle parole w.

Parole più grandi producono meno hits, velocizzano la ricerca a scapito della sensibilità.

Il valore atteso E è il numero di allineamenti con punteggio maggiore o uguale a un

punteggio S che dovrebbero verificarsi per caso in quella ricerca sula database. Si può

pensarlo come un indice di incertezza.

E = KMN e^-lambda *S

M lunghezza della query

N lunghezza della sequenza nel database

S score

lambda,K parametri che dipendono dallo scoring system (lambda) dal database usato (K)

Il valore E descesce esponenzialmente all’aumentare di S. Valori più elevati di S

corrispondono a migliori allineamenti e a E values più bassi.

Ottenere un allineamento con E = 1 significa che esiste un altro allineamento con lo

stesso score S che è risultato per caso

La stessa ricerca, su un database più grande o più piccolo, anche se restituisce lo stesso

allineamento deve avere un valore di E diverso (dipende da K).

I punteggi grezzi sono calcolati da una particolare matrice di sostituzione

I punteggi bit sono punteggi normalizzati, quindi sono paragonabili tra diverse ricerche

(con diverse matrici di sostituzione o diverse banche dati) perché sono normalizzati,

appunto

Una soglia E elevata può aver se