Metodi euristici di

allineamento

Algoritmi euristici di allineamento

Sono nati insieme alle banche dati, con lo scopo di permettere una ricerca rapida, anche se meno accurata, utilizzando la similarità a coppie (o “pairwise”) sulle migliaia di sequenze depositate.

Attualmente i programmi più utilizzati sono:

FASTA : Lipman & Pearson (1985)Nasce con il nome di FAST-P (ricerca veloce di proteine), ma poi viene adattato per gli acidi

nucleici (FAST-N), quindi riunito in un FAST per tutti, FAST-A, o semplicemente FASTA.

http://www.ebi.ac.uk/Tools/fasta33/index.html

BLAST : Altshul (1990)Il Basic Local Analysis Search Tool viene pensato

http://blast.ncbi.nlm.nih.gov/Blast.cgi

FASTAIl frontend più utilizzato di FASTA è quello disponibile presso la EBI: l’interfaccia web permette di configurare il programma e di ottenere in diretta o tramite e-mail i risultati.

Metodo dell’indicizzazione

L’algoritmo implementato in FASTA si basa su una strategia di indicizzazione delle parole e sul concetto di “Lookup Table ”: la proteina QUERY viene spezzettata in parole di lunghezza ktup (k-tuples) e la query viene così indicizzata (cioè si memorizzano solo gli indici, non la coppia).

ELDERILGEVQTFDERIKGD1.EL

5.RI

2.LD

6.IL7.LG

4.ER

20.GD

3.DE

......

Maggiore è il valore ktup più rapida e meno accurata sarà la ricerca. Per una proteina a ktup = 2 potrò avere al massimo 202 = 400 combinazioni, sempre.

ktup = 214.DE15.ER

Ogni SUBJECT della banca dati viene pre-indicizzata con la stessa k-tup, e si procede, data la query e ciascuna subject, alla creazione delle tabelle degli offset (indice della query meno indice della subject). Le diagonali che totalizzano il miglior punteggio (in generale almeno 10) vengono registrate.

543210-1-2-34LD

------------SUBJECT---------�

432101-2-3-45DE

------------------- QUERY ------------------�

3210-1-2-3-4-56EV

6543210-1-23IL

76543210-12RI

8765432101ER

9EV8GE7LG6IL5RI4ER3DE2LD1EL0

Lookup tables e offset (diagonali)

Total = 3Offset = 3

Total= 2Offset = -2

Essendo somme di coppie, il numero di conteggi da fare non è più il prodotto delle lunghezze, bensì qualcosa di simile alla somma delle due, con un netto decremento del tempo di calcolo.

Scelta euristica dei subject

I conteggi per calcolare le migliori diagonali sono semplici somme i cui valori vengono presi da matrici di sostituzione (es. PAM, BLOSUM). Le migliori diagonali identificano le Best Initial Regions , i cui punteggi sono definiti Init1 .

Query

Subject

Subject

Query

Per ogni subject ho uno score che definisce la similarità media della query con ogni subject: in pratica, dato un Init1 minimo, vengono scelte in modo euristico delle sequenze candidate per analisi più approfondite.

Il passaggio successivo di FASTA è il tentativo di congiungere al meglio ogni BIR dei subject prescelti utilizzando criteri come:

- Esclusione di eventuali overlap fra regioni- Punteggio superiore ad un "valore-soglia“- Punteggi di penalizzazione (es. -16) per i gap

Congiungimento delle diagonali

Le regioni vengono allungate e avranno un nuovo score, detto InitN . Questa è una seconda soglia di scelta, alcune sequenze non passeranno questo test e verranno a loro volta scartate.

Subject

Query

Subject

Refinement finale con pairwise esaustivo

Alla fine tutta la regione della subject riconosciuta come simile viene allineata mediante l’algoritmo di Smith & Waterman, tenendo una finestra di analisi intorno alla diagonale principale abbastanza stretta (< 20 residui).

Subject

Subject

QueryQuery

Lo score definitivo deriva quindi da una allineamento pairwise esaustivo, ed è definito Opt .

Query

Subject

Query

Subject

Query

Subject

Query

Subject

Fase 1 : Indicizzazione col metodo lookup table

Fase 3: Definizione delle sequenze da approfondire, calcolo degli InitN

Fase 2 : Calcolo degli Init1, generazione delle bits

Fase 4 : Smith-Waterman (Opt)

Analisi Monte Carlo per la significatività

Si cerca di valutare quanto il risultato che ottengo è significativo, considerando l’ipotesi alternativa che il risultato ottenuto sia dovuto al caso.

Il concetto da tenere presente è che il risultato che si ottiene è dovuto agli aminoacidi che sono disposti in un certo ordine : se cambio l’ordine, lo score si dovrebbe perdere:

Monte Carlo : 1. Prendere ogni subject, registrare lo score (X)2. Produrre 100-200 versioni “randomizzate” di questo3. Allineare ogni random con fasta, registrando gli Opt (y)4. Calcolare la media (Y) e la deviazione standard (W) degli

score Opt calcolati in 3.

5. Standardizzare calcolando lo Z-score

Per z < 3 l'omologia NON è statisticamente significativaPer 3 < z < 6 l'omologia è POSSIBILMENTE statisticamente significativaPer 6 < z < 10 l'omologia è PROBABILMENTE statisticamente significativaPer z >10 l'omologia è statisticamente significativa

Z = X-Y

W

In ogni caso non si puòdefinire un p-valueesatto perchè non sipuò sapere la distribuzione di Z

La results page di FASTA

Modalità “Show Alignment”Premendo il bottone “Show Alignments” il risultato si arricchisce di dettagli: emergono i vari scores (init1, initN, opt, Z-score) dell’euristica, poi anche lo score dell’esaustiva. Viene poi presentato anche l’allineamento finale.

Il bit scoreTutti gli score S che emergono dalle analisi FASTA (ma è una regola generale) restano confinati al singolo allineamento, e non sono comparabili tra allineamenti diversi.

Il sistema dei punteggi (dato dalla matrice di sostituzione e dalle gap penalties) è però comune per tutti, quindi esiste un modo per convertire uno score S in un bit score S’ utile per i confronti tra allineamenti diversi.

S' = λ*S - ln Kln 2

λ e K sono i due fattori di conversione da utilizzare, e sono stati calcolati secondo regole statistiche precise.

da “Bioinformatics: Sequence and Genome Analysis” - David W. Mount – CSHL Press

Basic Local Alignment Search Tool (BLAST)

Il punto di accesso più utilizzato per eseguire chiamate BLAST è presso l’NCBI.

Come per FASTA la maschera permette di impostare i parametri di ricerca e di significatività minima richiesta.

E’ inoltre possibile scegliere il tipo di algoritmo BLAST da utilizzare.

Anche BLAST basa la sua euristica sull’indicizzazione, ma introduce una sofisticazione a livello dei k-tuples, che qui vengono chiamati “word”.

TFDER LSH GVQQTFWECIKGDVSH = 16ISH = 14LAH = 13LTH = 13LSH = 13

Word size (W) = 3Threshold (T) = 13

Si inizia con la creazione di un elenco di parole di lunghezza W dalla querye creazione di “w-mers”, cioè parole di lunghezza W che diano, secondo una matrice di sostituzione uno score > T se allineati sulla query stessa.

Per ogni parola vengono generati anche tutti i possibili w-mers, quindi ci sono molte più parole che in FASTA.

Indicizzazione in BLAST

La ricerca è basata sempre sulle diagonali, ma dato che si hanno molte words sinonime, verranno segnati dei match positivi (hits ) anche se non sono word identiche.

In ogni caso gli indici fanno riferimento alla word vera della query, non dei suoi sinonimi. Ottengo così una lista di proteine in cui è stata trovata una corrispondenza con i frammenti della query.

Ricerca delle hits

543210-1-2-34LD

------------SUBJECT---------�

432101-2-3-45DE

---------------------------- QUERY ------------------------------�

3210-1-2-3-4-56EV

6543210-1-23IL

76543210-12KI

8765432101EK

9 EV-EI-EL-DV-DL

8 DE-ED

7 LD-VD-ID

6 IL-IV-II-LI-VL

5 RI-KL-RL-RV-KI

4 ER-EK-DR-DK

3 DE-ED

2 LD-LE-VE-VD-ID

1 EL-EV-EI-DL-DI

0

Total = 6Offset = 3

Total = 2Offset = -2

Una volta che le varie hits sono state trovate, BLAST inizia a congiungerle. IN questa fase NON è previsto l’inserimento di gap. L’allungamento si ferma quando lo score del tratto scende sotto una seconda soglia, detta S (se è alta l’allungamento sarà minore).

A questo punto si è individuato un HSP (High-scoring Segment Pair).

In realtà anche se lo score scende sotto S, ma solo per alcuni residui, e poi risale, l’HSP può ancora allungarsi. Il parametro X dice la quantità di perdita di score massima tollerabile se si prosegue con l’allungamento dell’HSP.

Estensione senza gap – gli HSP

Query:83 LMVAISNVGTDTLSHLEAQNKIKSASHNLSLTLQKSK+++AIS GT+++SH +AQ++IK+AS+ L L + ++

Subject:48 VILAISGFGTESMSHADAQDRIKAASYQLCLKIDRAE

HSP

hit hit hit

BLAST ha dunque 4 parametri fondamentali:

W: word size, maggiore è il numero, minore è il numero di parole generate, minore è il tempo di esecuzione. Ma la sensibilità decresce sensibilmente.

T: threshold, minore è il numero, maggiore è il numero di w-mersinclusi nella lista, maggiore è il tempo di esecuzione. Si ha però un incremento di sensibilità.

S: score, minore è il numero, maggiore sarà la lunghezza degli HSP

X: maggiore è il numero, più estesamente sarà osservato l’intorno di una HSP, aumentando il tempo di esecuzione.

Ciò che rende BLAST uno strumento molto efficace è l’impronta statistica su cui si basa il parametro S, che in questo caso agisce su allineamenti locali senza gap. La statistica degli score in questo caso è nota e si basa su un modello di casualità che dipende dalla composizione del database in cui si cerca e dalla matrice di sostituzione usata.

Dato un S in fatti è possibile prevedere quanti HSP di quella lunghezza m si osservano in una banca dati della stessa grandezza di quella vera ma composta da proteine casuali. Questo numero è definito E (expected), secondo

La statistica di BLAST

E = K m n e -λSm e n indicano l’ampiezza dell’HSP e della

banda dati, rispettivamenteK e λλλλ sono fattori di scala che dipendono dal

sistema di scoring utilizzato

=> è molto più semplice pensare in termini di E che non in termini di S, quindi in realtà non si imposta S ma E.

La distribuzione degli scoresSupponiamo di avere fatto un allineamento tra due sequenze, e di avere uno score S.

Un modo per sapere se lo score è significativo, è quello di generare N sequenze casuali della stessa lunghezza, allinearle, calcolare la media e la deviazione standard degli scores ottenuti (Monte Carlo).

Se implicitamente si assume che essi abbiano una distribuzione normale, si può calcolare la p(S) integrando

In realtà, solo quelli che danno qualcosa di biologicamente rilevante vanno presi, eliminando gli score “peggiori”. Questo provoca una deviazione dalla “normalità” e definisce la “distribuzione dei valori estremi”.

La results page di BLAST – Graphic summary

Se BLAST riconosce una similarità ampia con una o più famiglie proteiche note, lo indica in modo grafico.

E’ presente poi un summary grafico che permette di esplorare velocemente i primi 100 hits mostrandoli allineati con la sequenza query.

La results page di BLAST – Descriptions

BLAST include nel suo output un riassunto testuale delle sequenze che sono state trovate: per ognuna mostra un link (in questo caso ad EntrezProtein), il nome, lo score (in bits) e L’Expect value, secondo cui i risultati sono ordinati.

La results page di BLAST – Alignments

Sotto alle descrizini inziano i risultati veri e propri, ossia gli HSP: oltre alle note viste nelal descrizione, vengono riportate le identità, le similarità (Positives) e i gaps inseriti, se ce ne sono. Notare come gli allineamenti servano come “spiegazione” del risultato: il risultato è che la proteina è stata identificata, non è stata allineata…

blastp : cerca similarità in banche dati proteiche a partire da un a querydi amino acidi.

blastn : cerca similarità in banche dati di nucleotidi a partire da una querydi nucleotidi.

blastx : cerca similarità in banche dati proteiche a partire da una query di nucleotidi che viene tradotta in tutti i frame.

tblastn : cerca similarità in banche dati di nucleotidi a partire da unaquery di amino acidi, traducendo in amino acidi tutti i subject della banca dati, in tutti frame.

tblastx : cerca similarità in banche dati di nucleotidi a partire da unaquery di nucleotidi, traducendo in amino acidi tutti i subject della banca dati

BLAST si è arricchito nel tempo

BLAST è stato recentemente implementato con un two-hit method , che prevede che l’estensione delle HSP possa avvenire solo se due hitsindipendenti si verifichino entro un numero di residui A, senza gaps in mezzo. Sono nate inoltre varie versioni specializzate:

gapped-blast : porta avanti la fase di estensione delle HSP considerando la possibilità di inserzione dei gap.

PSI-BLAST : effettua una ricerca iterativa utilizzando le HSP per generaredei profili caratteristici della query.

PHI-BLAST : estensione di PSI-BLAST per la ricerca in banca dati di pattern proteici più che di query esatte.

BL2SEQ : adattamento di blast per l’allineamento a coppie

MegaBLAST : può concatenare molte queries tra loro per minimizzare il tempo di esecuzione dovuto a sequenze query troppo lunghe (è adatto a sequenze nucleotidiche molto simili tra loro)

BLAST si è arricchito nel tempo

FASTA o BLAST ?

Gli algoritmi usati in BLAST e FASTA sono simili come strategia, ma molto diversi nei contenuti.

Il fatto che Fasta indicizzi le query in modo esatto lo porta a ridurre di molto il numero di subject su cui lavorerà in seguito, e questo è una tappa limitante che BLAST non ha a causa dei w-mers.

Però Blast crea i w-mers basati su una matrice quindi può accadere che match esatti diano meno score S di match non esatti:

es. secondo la Blosum62

- il match perfetto AIS-AIS dà score 12 - lo score inesatto LSH-MSH dà score 14

=> il secondo è premiato più del primo

Per ricerche in banche dati nucleotidiche, l’indicizzazione in w-mers simili ha poca rilevanza. Le basi infatti non sono mai “con caratteristiche chimico fisiche simili”…

Il valore W di default di BLAST per i nucleotidi è 11, il che lo porta a non riconoscere sequenze che condividano in modo esatto meno di 11 basi, è questo è un limite grosso (ma quello è il default…).

Fasta è molto più tollerante per sequenze che presentano gaps, visto che già nelle prime fasi prevede il loro inserimento, mentre BLAST li inserisce solo in fase di allungamento.

⇒ FASTA è più adatto a ricerche in banche dati nucleotidiche

⇒ BLAST è più adatto a ricerche in banche dati proteiche

Anche se questa regola è un po’ troppo arbitraria...

Scelte consapevoli