Metodi euristici, Fasta e Blast PDF

Preview

Summary

i più famosi algoritmi di allineamento a coppie e il loro funzionamento....

Description

FASTA E BLAST Le matrici di sostituzione come quelle ideate da Smith e Waterman sono molto precise ma hanno un problema: sono lente. Se volessimo fare un appaiamento tra due sequenze lunghe 1.000 residui la matrice dovrebbe calcolare 1.000.000 interazioni per ogni appaiamento. Il punto è che usando un database le sequenze da analizzare sarebbero migliaia facendo diventare l’operazione un’odissea interminabile. Perciò per effettuare ricerche di similarità in banche dati si usano metodi euristici: metodi che si basano su assunzioni molto probabili ma NON CERTE. Questo implica che avremo una ricerca più veloce ma non la certezza che si avrà la soluzione migliore. Questi metodi confrontano la sequenza di partenza (query) con le migliaia presenti della banca dati (subject) dandoci in pochi secondi un risultato. I programmi che sfruttano questi metodi euristici sono: FASTA e BLAST. In generale entrambi i programmi provano un allineamento, gli attribuiscono un punteggio, lo memorizzano e alla fine riportano quelli con gli scores migliori che erano sopra la “soglia” prestabilita. Questi due sono metodi “world” e “k-tuple” (vedremo poi cosa significa). FASTA Programma per la ricerca rapida di similarità sviluppato da Lpiman & Person nel 1985. Si basa su una strategia di “indicizzazione” delle parole. Un parametro fondamentale è il ktup che indica la lunghezza delle parole da indicizzare (che vengono chiamate ktuples). Solitamente si usa ktup=2 per le proteine (202=400 parole diverse di 2 amminoacidi) mentre ktup=6 per gli acidi nucleici (46=4096 parole diverse di 6 nucleotidi). Perciò l’indicizzazione altro non è che trovare tutte le “parole” all’interno della query. Dopo l’indicizzazione il programma inizia ad analizzare TUTTE le sequenze presenti nella banca dati (questo processo siccome è bello lungo viene diviso in 4 steps): • Step1= il programma consulta l’indice per identificare le stesse parole della query nella subject. Se trova delle corrispondenze (parole presenti in entrambe le sequenze) memorizza ogni volta “la diagonale” corrispondente (vedi immagine) in una ipotetica matrice

dotplot e alla fine unisce (se presenti) segmenti di parole contigue per formare dei “segmenti di identità” più lunghi. Ciò si fa calcolando gli offset (cioè le differenze) tra gli indici della casella subject con quello della query. Se duo o più parole hanno lo stesso offset allora si trovano nella stessa diagonale e non c’è inserzione o delezione.

•

Step2=i punteggi delle regioni che hanno i segmenti più lunghi sono ricalcolati usando una matrice di sostituzione (PAM, BLOSUM). Così facendo si ottengono le 10 “best initial regions” e i loro punteggi sono indicati con init1. Questi init1 sono usati per stipulare una graduatoria e solo quelli che superano un determinato valore soglia accederanno alla prossima fase.

•

Step3=in questa fase vengono generate regioni di similarità più estese chiamate initN. Questa operazione è effettuata congiungendo, dove possibile, le best initial regions applicando le giuste penalità ove fossero presenti dei GAPs (cioè se i migliori best initial regions hanno offsets diversi posso aggiungere dei GAPs per coniugarli).

•

Step4= in questa fase vengono applicati gli algoritmi di Smith & Waterman (allineamento locale) su una ventina di amminoacidi intorno alle best initial regions. Per calcolare il punteggio ottimizzato indicato dal programma con opt.

Ricorda che si sta parlando sempre di metodo euristico perciò non vi è la certezza che sia il miglior allineamento possibile. Certo, viene utilizzato l’algoritmo di Smith & Waterman ma solamente in una regione ristretta

(le best initial regions) e solamente DOPO che è stata effettuata la ricerca iniziale basata appunto sul metodo euristico (indicizzazione). Maggiore sarà il parametro di ktup utilizzato, più veloce sarà la ricerca (perché restringo il campo) a discapito dell’accuratezza che invece sarà minore. Ovviamente se si vuole ottenere la massima sensibilità dal programma si dovrà usare un ktup=1 tuttavia nella prima fase di indicizzazione il programma si basa su criteri di identità assoluta e non di similarità (come nelle matrici di sostituzione). Perciò il programma vede la leucina come un amminoacido differente dalla isoleucina portando ad una probabile mancata identificazione di allineamenti. BLAST Altro programma per la ricerca rapida di similarità ideato da Altschul nel 1990. Si può trovare su NCBI (banca dati americana) e il suo acronimo sta per BASIC LOCAL ALIGNMENT SEARCH TOOL. L’affinità delle parole viene determinata da una matrice di similarità (es. BLOSUM62) Proprio come FASTA, anche BLAST si basa sull’indicizzazione delle parole ma i due programmi differiscono per due cose: • Contenuto degli indici • Modo di procedere dopo aver trovato parole comuni a entrambe le sequenze Il procedimento di BLAST può essere suddiviso in tre steps: •

Step1: creazione di un indice leggendo ogni singola parola di lunghezza W sulla query (w=3 per proteine w=11 per acidi nucleici). Per ogni parola della query ne viene generata una affine chiamata W-mer(s) che dovrà superare un determinato punteggio soglia T. Tutte le sequenze superiori alla soglia T vengono inserite nell’elenco. L’affinità viene calcolata usando una matrice di sostituzione (es. BLOSUM62).

•

Step2= l’algoritmo ricerca nella banca dati tutte le subjects che hanno delle W-mers presenti nella lista stipulata nel primo step. Ogni corrispondenza trovata è indicata con l’acronimo hit. Ogni hit viene vista dal programma come una possibile posizione di un allineamento più esteso (in poche parole queste hit fungono da punto di partenza)

•

Step3:in questo step il programma prova ad estendere in entrambe le direzioni ogni hit, senza aggiungere alcun GAP. Quello che si ottiene è un segmento di allineamento locale non estendibile HSP (high scoring pairing). Qui entra in gioco un altro parametro: S che simboleggia il valore soglia che ogni HSP deve avere per essere ritenuto valido dal programma. Anche se il programma trova da

subito punteggi negativi non rinuncia a estendere l’allineamento. Infine subentra il quarto ed ultimo parametro X che stabilisce quanto il programma deve insistere per allungare HSP con punteggi negativi (infatti questo parametro è misurato in termini di score e si potrebbe dire rappresenti una sorta di penalità che spingerà il programma a portare avanti un allineamento con punteggi negativi solo se ne vale la pena).

Perciò i 4 parametri usati da BLAST sono: W,T,S,X. W e T insieme determinano la grandezza della lista delle W-mers perché W (lunghezza delle parole) genera le W-mers mentre T (valore soglia delle W-mers per entrare nella lista) le filtra. Alti valori di T potrebbero non identificare importanti HSP infatti potrebbero esserci HSP che superino il valore S (soglia per le HSP) pur non avendo W-mers maggiori o uguali alla soglia T. Aumentando il valore X (soglia per insistere sugli HSP negativi) si va ad aumentare anche la durata del procedimento perché ogni intorno a HSP viene “esplorato” con più precisione. Volendo può essere anche impostato un parametro E (expected) che sta per il numero di HSP aspettato. S viene calcolato in base ad E e se E non viene stabilitodall’operatore allora viene preso arbitrariamente uguale a 10. La seconda versione di BLAST, gapped BLAST, permette l’inserimento di GAPs con l’eventuale aggiunta di penalità quando si cerca di inserirli li

dove il programma cerca di estendere gli HSP. Esistono diverse varianti di BLAST: •

Blastp: cerca similarità in una banca dati amminoacidica partendo da una query di amminoacidi

•

Blastn: cerca similarità in una banca dati di sequenze nucleotidiche partendo da una query di nucleotidi

•

Blastx: cerca similarità in una banca dati di amminoacidi partendo da una query di nucleotidi (prima converte la sequenza nucleotidica in amminoacidica)

•

Tblastn: cerca similarità in una banca dati di nucleotidi partendo da una query di ammioacidi

•

Tblastx: carca similarità in una banca dati di nucleotidi partendo da una query di nucleotidi convertendo sia query che subject in amminoacidi

•

Megablast: è un BLAST ottimizzato per allineare sequenze uguali, mettendo in risalto eventuali errori nella sequenza o polimorfismi. La differenza tra megablast e blastn è la scelta di W che in megablast è di 16 o più (sempre multipli di 4). Avendo parole più lunghe ovviamente cerca più velocemente e con più precisione sequenze identiche (si usa in casi di 90% o più di identità).

•

Discontiguous megablast

Esistono altri tipi di BLAST che puoi vedere su internet. Oltre a questi ricorda che c’è un’applicazione di plast primer BLAST che permette di progettare dei primers per la PCR. ALLINEAMENTI MULTIPLI Uno dei problemi principali di BLAST e FASTA è che comparano solamente due sequenze, perciò gli allineamenti multipli tornano utili. Con gli allineamenti multipli hai una situazione di tipo: Nk dove N rappresenta la lunghezza delle sequenze e K rappresenta il numero di sequenze che si sta allineando.inutile spiegare perché gli allineamenti multipli sono così importati, grazie a loro infatti è possibile fare studi che permettono di

mettere in relazione sequenze omologhe e spiegarne l’evoluzione (stessa colonna=sequenze omologhe). Ricorda che due sequenze molto simili sono, quasi certamente, omologhe ma non tutte le sequenze omologhe sono simili (a causa della divergenza evolutiva). Per gli allineamenti multipli non è possibile usare algoritmi di programmazione dinamica, impiegherebbero troppo tempo e troppa memoria. Il problema principale degli msa (multiple sequences allignment) è come tener conto allo stesso tempo di tutti i matches, mismatches, Gaps e del grado di variazione. Per risolvere questa problematica si usano soluzione approssimate: • Fare un allineamento globale progressivo partendo dalle due più simili e poi estendendolo alle altre sequenze • Metodi che, dopo un iniziale allineamento, ricalcolano la matrice per ottenere risultati più affidabili • Allineamenti basati su “pattern locali” più conservati • Uso di modelli statistici e probabilistici. Gli msa possono rivelare se esiste una correlazione evolutiva tra tre o più sequenze e possono indicare quali regioni mostrano più similarità (regioni conservate). La cosa bella di questa cosa è che conoscendo la struttura di una o più parti delle proteine allineate si possono fare, usando determinati softwers, predizioni di struttura, previsione dei siti di regolazione di DNA, sonde specifiche, primers per PCR. Nota: su NCBI esistono anche msa basati su algoritmi dinamici, ma a causa della loro lentezza sono usati solo quando c’è bisogno di un’accuratezza perfetta. Per trovare un giusto compromesso tra accuratezza e praticità è stato proposto un metodo approssimativo (euristico) che si basa sull’assunto che le sequenze che si vanno ad allineare siano filogeneticamente collegate. Questo metodo prende il nome di allineamento progressivo o metodo gerarchico o ad albero. Si allineano le sequenze filogeneticamente più “vicine” e poi mano a mano ci si allontana dai parametri iniziali, perciò dipende tantissimo dall’assegnazione delle

relazioni iniziali che vengono date. I software più famosi ideati sulla base di questo metodo sono: ClastalW,TCoffe,PSAlign.

CLUSTALW Ideato nel 1988 da Higgins & Sharp, è uno dei programmi più utilizzati per l’allineamento multiplo. Come già accennato prima non utilizza un algoritmo dinamico ma progressivo. Sostanzialmente fa tre cose: • Si ottengono tutti gli allineamenti di coppia possibili e si registra il valore di ognuno (si fa una matrice di tutte le distanze) •

Si costruisce un albero filogenetico usando i valori registrati così da visualizzare eventuali relazioni evolutive (neighbour joining)

• Ad ogni passo si allinearà la coppia (seq-seq, seq-profilo, profiloprofilo) con la distanza minima (punteggio massimo).

Poi per allineare un'altra sequenza ad un allineamento già esistente si usa una matrice e si calcola il punteggio più elevato. I svantaggi di questo metodo sono:

•

A causa dei metodi di allineamento globale utilizzati non si possono allineare sequenze di lunghezze diverse

•

Spesso non è tollerata l’inserzione di lunghi GAPs e ciò peggiora l’accuratezza del metodo

•

L’allineamento finale è influenzato dall’ordine con cui vengono inserite le sequenze (albero guida)

•

L’algoritmo dipende dai primissimi accorgimenti fatti nella prima coppia di allineamenti (greedy). Se vengono inseriti i GAPs nei primi allineamenti essi vengono “fissati” ed eventuali errori fatti in questa fase non possono più essere corretti

•

Propagare errori all’interno degli allineamenti a causa dell’errore precedente.

Clustal e Clustal omega sono stati resi più accurati grazie ad una implementazione di HMM....