4 I sistemi euristici (fasta e blast)

Ricerche in banche dati con singola sequenza: i sistemi euristici

L'aumento esponenziale del numero di sequenze di proteine e acidi nucleici nelle banche dati ha reso necessario disporre di sistemi in grado di recuperare rapidamente sequenze simili a una certa sequenza (che chiameremo sequenza sonda o query). Una tipica domanda che spesso il ricercatore si pone è: “Data questa sequenza, quali sequenze simili sono già note e presenti nelle banche dati?”. Ancora più importante è chiedersi: "Di questa proteina non è nota la funzione: esistono nelle banche dati sequenze caratterizzate funzionalmente che possano suggerire una funzione per questa sequenza?”.

Naturalmente un sistema in grado di rispondere a queste domande deve essere rapido e fornire una soluzione utile in pochi minuti. Gli algoritmi di allineamento dinamico, anche se precisi, sono molto pesanti dal punto di vista del calcolo, e non possono essere impiegati efficacemente per confrontare sistematicamente una sequenza a tutte le migliaia presenti nelle banche dati, specialmente se la ricerca deve essere ripetuta più volte.

Sistemi euristici

Per rispondere a questa sfida, diversi autori hanno proposto alcuni sistemi euristici, sistemi cioè che trovano soluzioni approssimate, ma vicine a quella ottimale, in un tempo relativamente breve. In pratica, i metodi euristici si basano su assunzioni molto probabili ma non certe. La filosofia di base che segue la maggior parte di questi sistemi è quella di selezionare rapidamente le sequenze della banca dati potenzialmente simili alla sonda, per poi raffinare il confronto nell’ambito di questo sottoinsieme di sequenze.

La capacità di un programma di classificare correttamente le sequenze omologhe alla sonda si definisce sensibilità. La capacità del programma di discriminare correttamente le sequenze non omologhe si definisce, invece, specificità. Nella realtà, quasi sempre, la rapidità di ricerca di un sistema euristico si paga con una minore sensibilità e selettività.

FASTA

Uno dei primi metodi elaborati per eseguire ricerche rapide in banche dati è quello proposto da Pearson e Lipman, chiamato in origine FASTP. L’algoritmo di confronto su cui si basa FASTP utilizza una tecnica nota come lookup table (tavola di ricerca) che permette di evidenziare rapidamente le zone di identità tra due sequenze.

Vediamo in cosa consiste questa tecnica. Prendiamo le seguenti due sequenze non allineate ma semplicemente sovrapposte:

Posizione: 1 2 3 4 5 6 7
seq 1 F L W R T W S
seq 2 S W K T W T

Per ognuna si annota la posizione o le posizioni in cui si trova ciascuno dei 20 aminoacidi. Si scrive la sequenza dei 20 aminoacidi nella colonna di una tavola, come riportato di seguito:

Nella tavola, a fianco all’aminoacido si scrive la posizione o le posizioni che occupa nelle due sequenze considerate qualora questo aminoacido sia presente nell’una o nell’altra sequenza o in entrambe, come sopra. Per esempio, il triptofano (W) si osserva in posizione 3 e 6 nella prima sequenza e in posizione 2 e 5 nella seconda. Si calcola poi la differenza tra le posizioni degli aminoacidi identici nelle due sequenze.

Ad esempio, l’aminoacido S è posto in posizione 7 nella prima sequenza e in posizione 1 nella seconda. Quindi i due aminoacidi sono posti a 6 posizioni l’uno dall’altro (7-1=6). Oppure, l’aminoacido T è posto in posizione 5 nella prima sequenza e nelle posizioni 4 e 6 nella seconda sequenza. In questo caso si calcola la differenza di posizione sia tra il T della prima sequenza e il T in posizione 4 della seconda e sia tra il T della prima sequenza e il T in posizione 6 della seconda. Quindi avremo che il T della prima sequenza differisce per 1 posizione con il T in posizione 4 della seconda sequenza; la differenza di posizione tra il T della prima sequenza e il T in posizione 6 della seconda sequenza è -1 (5-6=-1). Queste differenze si riportano nella tabella di sopra, come di seguito:

Come si può notare dalla tabella, ci sono tre aminoacidi identici che differiscono per una sola posizione. Quindi, per far combaciare questi tre aminoacidi (un T e due W) possiamo far slittare una sequenza rispetto all’altra, come di seguito:

W T W
F L R S
W T W
S K T

Il tempo necessario per identificare le zone di somiglianza tra le due sequenze secondo la modalità sopra illustrata cresce in modo approssimativamente proporzionale alla somma delle lunghezze delle due sequenze.

La nuova versione del programma attualmente in uso prende il nome di FASTA. FASTA è un programma che cerca similarità locali utilizzando l’algoritmo di Pearson e Lipman. La sua strategia è quella di suddividere la sequenza query in tante sotto sequenze lunghe 1 o 2 amminoacidi (queste sotto sequenze sono dette parole o k-tuples). La lunghezza di queste sotto sequenze viene indicata con ktup. Se le sotto sequenze sono, ad esempio, composte da solo due aminoacidi, allora ktup=2. Questa fase prende il nome di indicizzazione.

EL
DE ktup=2
ER
RI
IL
LG
GD

Il ktup può essere anche uguale a 1. In questo caso consideriamo i singoli aminoacidi. Usando un ktup=2 avremo una velocizzazione del processo a scapito, però, della precisione del dato finale. Nel caso di sequenze nucleotidiche ktup vale 4 o 6. Maggiore è il valore ktup più rapida e meno accurata sarà la ricerca. Per una proteina ktup=2 potrò avere al massimo 20²=400 combinazioni.

Il passo successivo è quello di calcolare la posizione delle varie parole della query, trovate precedentemente, in tutte le sequenze subject. Ad esempio, consideriamo la parola (o sotto sequenza) EL della query. Si indica la posizione di questa parola nelle varie sequenze subject, se mai queste presentino la parola EL. Quindi viene applicata la cosiddetta tecnica del lookup table.

Subito dopo, FASTA si preoccupa di calcolare il cosiddetto offset, cioè calcola la differenza di posizione tra le parole comuni individuate nella sequenza query e nelle sequenze subject. Ad esempio, la parola LD è stata individuata in posizione 5 nella sequenza subject 1, mentre nella query è in posizione 2. Quindi l’offset1 (relativo, cioè, alla sequenza query 1) per la parola LD è pari a (2-5)= -3. Lo stesso procedimento va effettuato per le altre parole e le altre sequenze.