4 I sistemi euristici (fasta e blast)

ELDERILGEVQTFDERIKGD1.EL2.LD3.DE ktup=24.ER5.RI6.IL7.LG………….. 20.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 2a ktup=2 potrò avere al massimo 20 = 400 combinazioni, sempre.

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) 1.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. Ovviamente se una parola della query è stata individuata in più posizioni di una subject, viene calcolato l'offset relativo a ciascuna posizione per quella stessa parola. Quindi avremo:

Ora facciamo un esempio pratico. Consideriamo una sequenza query come quella scritta di seguito: M A P E S R T G S A A T A T S T D

Per prima cosa, il programma divide questa sequenza in tante sotto sequenze di lunghezza (ktup) pari a 2. Ciò vuol dire che verranno considerate sotto sequenze composte da soli due aminoacidi. Le sotto sequenze sono le seguenti:

1. MA
2. AP
3. PE
4. ES
5. SR
6. RT
7. TG
8. GS
9. SA
10. AA
11. AT
12. TA
13. AT
14. TS
15. ST
16. TD

MA2. AP3. PE4. ES5. SR6. RT7. TG8. GS9. SA10.AA11.AT12.TA13.AT14.TS15.ST16.TD

Vengono poi prese in esame le sequenze subject, con le quali verrà confrontata la sequenza query. Un esempio di sequenza subject che si vuole confrontare con la query riportata sopra è scritta qui di seguito:

E T A H G S A A T A T W K L I N C V

Ora viene verificato se ciascuna sotto sequenza della query riportata sopra è presente nella subject. Se la sotto sequenza è presente anche nella subject viene indicata anche la sua eventuale posizione nella subject. Dopo aver fatto questo, bisogna calcolare gli offset. Tutti questi dati vengono annotati in una tabella, come quella riportata qui sotto:

Notiamo dalla tabella che ci sono 6 sotto sequenze della query che differiscono con le rispettive sotto sequenze della subject per 3 posizioni; 1 sotto sequenza della query che differisce con la corrispondente sotto sequenza della subject per 1 posizione; 1 sotto sequenza della query che differisce con la

corrispondente sotto sequenza dellasubject per 5 posizioni; e 1 sotto sequenza della query che differisce con lacorrispondente sotto sequenza della subject per 10 posizioni. Vengono consideratequelle sottosequenze che differiscono per 3 posizioni (quindi viene considerato comeoffset migliore quello avente valore pari a 3) perché in questo modo il programma puòeffettuare l’allineamento di 6 sotto sequenze. Gli altri offset permettono l’allineamentodi una sola sotto sequenza. Quindi, la sequenza query e la subject scorrono l’unasull’altra di tre posizioni, ottenendo il seguente allineamento:

M A P E S R T G S A A T A T S T DE T A H G S A A T A T W K L I N C V

Abbiamo così ottenuto un allineamento locale tra la sequenza query e una dellesequenze subject. Questo lavoro viene ripetuto ogni volta per tutte le altre subject deldatabase. Questo è il metodo secondo il quale lavorava il programma FASTP. In realtà,FASTA integra la tecnica

Del lookup table con le dot plot matrix. Innanzitutto viene costruita una tabella degli offset. Cioè vengono riportate le sotto sequenze della subject sulla prima colonna di una tabella; sulla prima riga della stessa tabella vengono riportate le sotto sequenze della query. Vengono poi riportati gli offset, che si calcolano sottraendo all'indice di ciascuna sotto sequenza della query l'indice di ciascuna sotto sequenza della subject. Vedi l'esempio sotto:

Vengono unite le caselle corrispondenti alle sotto sequenze della query e della subject che sono tra loro identiche e che hanno lo stesso offset. Quindi, per esempio, viene unita la casella con valore 3 relativa alla parola ER con la casella con valore 3 relativa alla parola RI e con la casella con valore 3 relativa alla parola IL. Poi viene unita la casella con valore -2 relativa alla parola LD con la casella con valore -2 relativa alla parola DE. Viene evidenziata anche la casella con valore 3 relativa alla parola EV.

Per meglio comprendere, vedi il disegno sotto:

Unendo queste caselle si ottengono delle diagonali, di cui alcune più lunghe altre più corte. Si ottiene quindi una dot plot matrix. Queste diagonali indicano le regioni di disimilarità.

Ora, immaginiamo che il numero dei residui amminoacidici delle due sequenze sia di gran lunga maggiore rispetto al numero di residui delle due sequenze sopra riportate.

Ne consegue che ci saranno di sicuro molte più regioni di similarità. Si ottiene così una dot plot matrix simile a quella riportata di seguito in cui ci sono tante diagonali (regioni di similarità) sparse in tutta la matrice.

Tra tutte queste regioni di similarità vengono scelte 10 regioni che hanno maggiore somiglianza, cioè 10 regioni che contengono un numero significativo di k-tuple: in definitiva, si scelgono le regioni relative alle diagonali più lunghe. La ricerca delle 10 regioni di maggiore somiglianza viene effettuata da FASTA.

Per ciascun confronto, a questo punto un nuovo algoritmo valuta eventuali sostituzioni intervenute nelle 10 migliori regioni di similarità selezionate nella prima fase, utilizzando a questo scopo delle matrici empiriche (le scoring matrix) fra cui le più note e diffuse sono le PAM e le BLOSUM, e la più usata delle quali è la PAM250. A ciascuna delle 10 migliori regioni di similarità viene quindi assegnato un punteggio in base all'analisi effettuata con la scoring matrix, il quale punteggio è detto punteggio iniziale (initial score o INIT1). Le regioni in questione si dicono Best Initial Regions. Solo le regioni che hanno un INIT1 maggiore rispetto a un valore soglia prefissato accederanno alla prossima fase. A questo punto la matrice riportata sopra diventa simile a quella riportata di seguito:

Le regioni iniziali che hanno un INIT1 maggiore rispetto a un valore soglia e che, quindi, possono essere utilizzate per la fase successiva, vengono

evidenziatemaggiormente nella dot pot matrix.A questo punto FASTA procede con un altro step, che è aggiuntivo rispetto all'originaleFASTp. In pratica, FASTA effettua una valutazione relativa alla possibilità di collegare(join) fra loro diverse regioni iniziali. Cerca di unire le regioni a più alta somiglianza,dove possibile, incorporandole in un unico allineamento. Vengono aggiunti dei gap perfare questa operazione dandogli, però, un peso (gap penality). Quindi, la dot plotmatrix diventa:Viene anche ricalcolato il punteggio relativo a questo allineamento. Il nuovo punteggioviene indicato con INITN e risulta dalla somma dei punteggi (ricavati dalle scoringmatrix) relativi a ciascun appaiamento tra aminoacidi e tiene conto anche dellepenalità date ai gap che sono stati aggiunti.Successivamente viene applicato un algoritmo dinamico relativo a questoallineamento. L'algoritmo determina un punteggio, detto punteggio ottimizzato(OPT). Una voltaparole, l'E-value ci fornisce una stima della probabilità di ottenere un punteggio ottimizzato S o superiore, semplicemente per caso, allineando la sequenza A con una sequenza non omologa presa a caso dalla banca dati. L'E-value è espresso in forma di valore numerico, ad esempio 1e-10, che indica la probabilità di ottenere un punteggio ottimizzato S o superiore per caso, una volta ogni 10 miliardi di allineamenti casuali. Quindi, se l'E-value associato al punteggio ottimizzato è molto basso (ad esempio, inferiore a 0.05), significa che la probabilità di ottenere quel punteggio per caso è molto bassa e quindi il risultato è statisticamente significativo. Al contrario, se l'E-value è alto (ad esempio, superiore a 0.05), significa che la probabilità di ottenere quel punteggio per caso è alta e quindi il risultato potrebbe non essere significativo. L'utilizzo dell'E-value è fondamentale per valutare la significatività statistica dei risultati ottenuti nell'allineamento di sequenze e per distinguere tra omologia e casualità.

parole:” che probabilità ho di ottenere il punteggio S per caso?”. Se questaoptprobabilità è relativamente elevato vuol dire che A e B non sono significativamentecorrelate e verosimilmente non sono omologhe. In altri termini, poichè, con la ricercamatchin banche dati di grandi dimensioni, il numero di trovati è in genere piuttostoalto, il problema è di avere uno strumento per valutarne l’attendibilità. In un tipicooutput di FASTA, per i match trovati viene riportata la percentuale di identità, ilgap,numero dei il punteggio che tiene conto del grado di similarità e dei gapintrodotti, e un valore statistico, l’e-value. L’e-value è un parametro tipicamentematch,utilizzato come indice di attendibilità; esso indica il numero di di punteggiouguale o superiore a quello trovato, che si troverebbe nella stessa banca dati usando,come sequenza query, una casuale, della stessa lunghezza e

composizione dellasequenza in esame. Per esempio, se a un certo punteggio S è associato un E-value diopt-210 , questo vuol dire che ci aspettiamo di trovare in quella banca dati 0,01 sequenzenon correlate alla nostra che ottengono un punteggio superiore a S (falsi positivi).

optBLAST

Il metodo BLAST è stato elaborato per rendere ancora più rapide le ricerche nelle banche dati rispetto a FASTA senza perdere significativamente in sensibilità e selettività. BLAST, che è l'acronimo di Basic Local Alignment Search Tool (strumento di ricerca di base per l'allineamento locale), è un programma euristico per la ricerca di omologie locali di sequenza. Il software BLAST in realtà è composto da diversi algoritmi che consentono di allineare non solo sequenze nucleotidiche consequenze nucleot