Blast

Problematiche dell algoritmo di allineamento ottimo e soluzioni euristiche

Gli algoritmi di allin ott hanno un costo computazionale elevato,

devo calcolare n*m valori della matrice di procedura e memorizzarli.

Nell allin tra solo 2 sequ il problema non si pone, ma molto spesso si

confronta 1 sequ con tante sequ, con tutte quelle note. E’ un

numero elevatissimo di allineamenti a coppie.

Servono soluzioni euristiche, che sono soluz non ottime, non

abbiamo la stessa garanzia degli algoritmi ottimi ma dà risultati

accettabili ed è una strategia +veloce.

Il più noto è BLAST.

BLAST (Basic Local Alignment Search Tool): i suoi programmi

E’ un tipo di analisi che è a strategia intrinsecamente locale.

Funz sia per proteine (seq aa) che per dna (seq nucl). Cerca nei

rispettivi database.

E’ un insieme di programmi che riguardano il confronto di dievrsi tipi

di sequenze.

Le sei frecce rappresentano le 6 Open Reading Frames (ORF), cioè le

sei possibili finestre di lettura del dna. Quando ho una seq di dna

devo individuare una seq di triplette da leggere e tradurre, in

direzione 5’3’. Ma posso iniziare a leggere dal primo nucl opp dal sec

opp dal terzo, ottenendo 3 diverse seq di triplette ovvero open reading

frame, per ogni filamento. E posso leggere il dna su un filamneto o sull

altro. Quindi sono 6 in totale.

Algoritmo locale applicato da BLAST

E’ una strategia locale quindi riguarda delle sottosequenze.

Si compila una lista di sottosequenze/parole di lunghezza

prefissata (w). Da queste parole si deriva un vocabolario, cioè da

queste parole se ne ricavano altre simili, che abbiano similarità sopra

una certa soglia T, e poi tutte queste vengono cercate nel

database alla ricerca di un match (hit). Quando vengono trovate, l

algoritmo cerca di estendere a monte e a valle l allineamento, per

vedere se riguarda una regione più estesa, in questo modo il punteggio

subirà delle oscillazioni, e l estensione verrà interrotta nel momento

in cui dall ultimo picco di max si scenderà di una quantità X

stabilita, la regione estesa è chiamata High Scoring Pair (HSP).

Questo allin viene poi valutato dal pov statistico, ad ogni match viene

assegnata una significatività statistica e poi si selezioneranno i match

che rispetteranno una certa soglia di significatività.

Nell esempio, a partire dalla query faccio una scansione delle possibili

parole da 3 lettere, dalla singola parola deriviamo le parole simili a essa

(anche se non contenute nella query) e trattengo nel vocabolario tutte le

word che hanno similarità con la word originale sopra una certa soglia (es

T=13). Questo viene fatto per ogni sottosequenza. E quei punteggi sono

attribuiti mediante schema di punteggio es blosum. Provo a estendere la

finestra es da 3 a 4 aa e calcolo il nuovo punteggio, che può salire o

scendere. Estendo e tengo memoria del max raggiunto, quando scendo

sotto un parametro prefissato x alloro torno indietro all ultimo picco.

Le x rappreesntano le corrispondenze delle word (i match o hit).

Estendo l allin se e solo se trovo almeno due x (hit) sulla stessa

seq matchata, che siano sulla diagonale e con distanza inferiore

a parametro A. Chiedo sulla diag perché non voglio gap e la distanza

per avere una corrispondenza estesa. Per rendere il tutto più efficiente,

+ veloce.

Presentazione dei risultati

Le varie sequ risultato trovate vengono presentate nell output

grafico con la banda di punteggio secondo un codice colore.

Nell output tabulare, sono presentate con i loro codici di sequenza e

una descrizione, i punteggi e i valori di significatività statistica E. Ci

interessano quelle con punteggio elevato e bassa E.

Nel dettaglio, ovvero nell output di allineamento, troviamo l

allineamento (su più righe perché ho dei limiti di lunghezza dei caratteri

per l interfaccia). Dove c è identità vengono riportati i caratteri, dove

ho dei + ci sono sostituzioni ok dal pov biologico cioè che anche se

non sono corrispondenze esatte hanno punteggio positivo nella

matrice di sostituz.

La % di identità dice la % di corrispondenze. La % di positivi indica la

% di corrispondenze/sostituz con +. I gaps indicano il numero di gap.

Lo score è il punteggio e viene dato in bit.

Expect è il valore atteso, cioè E, che è legato alla significatività

statistica p.

I punteggi e significatività statistica

Esistono due tipi di punteggi. Il raw score è il punteggio grezzo, cioè

quello ottenuto direttamente dall allineamento. Il bit score è il

punteggio in bit, cioè il punteggio normalizzato sia rispetto alla

matrice di sostituzione utilizzata sia rispetto all ampiezza del

database di ricerca usato, in modo da permettere dei confronti tra

punteggi provenienti da allineamenti aventi parametri differenti.

Dato S il punteggio grezzo e S’ il punteggio in bit:

Dove lambda è stimata dalla matrice di sostituzione e K dall

ampiezza del database di ricerca.

La distribuzione di probabilità dei punteggi di similarità somiglia

alla normale/gaussiana, è una campana, ma non è simmetrica e segue

la distribuzione del valore estremo.

La probabilità che S sia sopra una certa soglia x è:

M=lunghezza query, N=lunghezza seq database.