Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D La Corte in Rete
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Giovanni Paolella » 13.Algoritmi di allineamento di tipo euristico


Biotecnologie cellulari e molecolari

Algoritmi di allineamento di tipo euristico

Prof. Giovanni Paolella

Dott. Leandra Sepe

Algoritmi euristici

Nella precedente lezione sono stati descritti metodi di allineamento che procedono selezionando il migliore allineamento tra tutti quelli possibili (Needleman e Wunsch e Smith e Waterman). Per questo motivo questi metodi sono stati definiti esaustivi.
Per quanto questi algoritmi per la ricerca di similarità di sequenza permettano di trovare rapidamente l’allineamento migliore, comunque l’applicazione di questi metodi richiede tipicamente da qualche secondo a qualche minuto, che è un tempo accettabile per il confronto di due sequenze ma diventa completamente inadatto se il confronto deve avvenire con una banca dati che contiene da migliaia a milioni di sequenze.
Allo scopo di ridurre tale impegno, è possibile affrontare il problema in un modo alternativo: anzichè procedere valutando tutti gli allineamenti possibili, si può scegliere di effettuare la ricerca in modo da considerare esclusivamente quelli più probabili. In questo modo si riduce drasticamente l’ampiezza del campo all’interno del quale effettuare la ricerca, con conseguente riduzione del tempo di calcolo.
Gli algoritmi di allineamento che usano questo approccio vengono definiti euristici; essi, accettando di non avere la certezza di trovare sempre il migliore allineamento possibile, garantiscono però una forte riduzione del tempo necessario ad effettuare la ricerca, tanto più importante quanto più è ampio il set di sequenze da studiare. L’approccio euristico può essere completato dall’applicazione di algoritmi di allineamento esaustivi ad un set ristretto di sequenze, dopo averle identificate inizialmente con l’approccio euristico, e garantendo così allineamenti finali di buona qualità.

FASTA

L’approssimazione descritta, cioè quella di eseguire la ricerca solo laddove è più probabile trovare l’allineamento, richiede in primo luogo la selezione di sedi adeguate. Tale selezione sfrutta alcune assunzioni, per esempio che la sequenza cercata abbia almeno alcune basi consecutive identiche. A questo scopo si esegue prima la ricerca di cosiddette tuple, cioè ennuple di sequenza che tipicamente sono di 2 aminoacidi e 6 nucleotidi. L’assunzione funziona correttamente nella maggior parte dei casi, anche perchè è alquanto difficile che due proteine correlate non abbiano almeno alcune coppie di aminoacidi in comune. Un minimo rischio può esserci nel caso, ad esempio, di proteine relativamente lontane con livelli molto bassi di identità, nelle quali tutti gli aminoacidi identici sono isolati.

FASTA: indicizzazione

Una seconda tecnica utilizzata per accorciare drasticamente I tempi di esecuzione, consiste nel fatto che tutti i blocchi di 2, per gli aminoacidi (400), e di 6, per i nucleotidi (4096), vengono precalcolati per una intera banca dati e conservati in un indice. Questo evita di effettuare il confronto tra la sequenza query e quelle della banca dati, perchè è sufficiente cercare i blocchi della sequenza query nell’indice (figura). In questo modo si selezionano rapidamente un gran numero di piccole zone di similarità, come rappresentato. A questo punto il filtraggio dei match trovati, conduce all’eliminazione dei match piccoli e isolati. Inoltre, nel successivo ricalcolo della similarità per quelli rimanenti, si utilizza una matrice PAM o BLOSUM. I match locali trovati vengono a questo punto connessi, selezionando, per ciascuno di essi, il migliore tra quelli alternativi. Infine, solo nell’intorno dei match trovati, viene applicato un algoritmo esaustivo, per ottenere un allineamento di buona qualità.


E-value

Poichè, con la ricerca in banche dati di grandi dimensioni, il numero di match trovati è in genere piuttosto alto, il problema è di avere uno strumento per valutarne l’attendibilità. E’ stato dimostrato che il numero di match locali trovati è funzione del prodotto della lunghezza delle due sequenze e di alcune costanti caratteristiche della libreria e della specifica sequenza query. Il numero di match di punteggio superiore ad una soglia ha una distribuzione di tipo Poisson come quella indicata in figura 1. In un tipico output di FASTA, per i match trovati viene riportata la percentuale di identità, il numero dei gap, il punteggio che tiene conto del grado di similarità e dei gap introdotti, e un valore statistico, l’e-value.

L’e-value è un parametro tipicamente utilizzato come indice di attendibilità; esso indica il numero di match, di punteggio uguale o superiore a quello trovato, che si troverebbe nella stessa banca dati usando, come sequenza query, una casuale, della stessa lunghezza e composizione della sequenza in esame. Un altro parametro spesso usato è il p-value, cioè la probabilità di trovare un match del tipo descritto sopra. I valori del parametro e-value variano tra numeri anche molto elevati e tendono asintoticamente a 0 al crescere del punteggio (score), mentre il p-value, essendo una probabilità, può assumere al massimo il valore di 1. Per valori inferiori a 0.1, i due valori sono essenzialmente sovrapponibili (figura 2).

Fig. 2

Fig. 2


Blast

Blast, come FASTA, è un programma che utilizza un algoritmo di tipo euristico per la ricerca di similarità in banche dati. Come FASTA, lavora ricercando delle piccole zone di similarità di lunghezza definita (2 aminoacidi e 6 nucleotidi), utilizzando librerie indicizzate per ottenere velocità di esecuzione elevate. A differenza di FASTA, pero’, le regioni di similarità inizialmente trovate vengono valutate con una matrice di tipo BLOSUM, per l’identificazione di High Scoring Segment Pairs (HSPs). Queste piccole regioni, vengono poi estese allontanandosi a sinistra e a destra finchè l’estensione risulta in un miglioramento del punteggio globale. Le regioni di similarità trovate in questo modo, Maximal Segment Pairs (MSPs), rappresentano quindi degli allineamenti locali. Il programma, nella sua versione originale, non prevede l’introduzione di gap, tuttavia versioni più recenti (gapped Blast), pur rimanendo programmi per la ricerca di allineamenti locali, accettano l’introduzione di un numero limitato di gap, se questi sono utili ad estendere ulteriormente i match trovati. Blast è un package che include diversi programmi, specificamente adattati per la ricerca di similarità tra sequenze aminoacidiche o nucleotidiche. Inoltre, nello stesso package, sono inseriti programmi che, accoppiando traduzione e ricerca di similarità, permettono di comparare sequenze query aminoacidiche con banche dati di acidi nucleici e viceversa. Infine, il programma tblastx, consente di comparare seuqenze nucleotidiche tra loro, tenendo conto della traduzione nei sei frames di entrambe le sequenze.

Riepilogo

Dalle tecniche di allineamento descritte, emerge una complessa varietà di algoritmi utili per rispondere a diverse esigenze sperimentali in quanto capaci di affrontare il problema da diverse angolazioni. In figura è riportato un riepilogo in cui sono distinti, a destra e a sinistra, metodi per la ricerca di allineamenti locali e globali. I programmi Needle e Water, del package Emboss, sono esempi, rispettivamente, di implementazioni degli algoritmi di Needleman e Wunsch e di Smith e Waterman, ma esistono naturalmente altri programmi che introducono variazioni agli algoritmi di base. In basso in figura sono invece riportati due tipici programmi largamente in uso basati su algoritmi di tipo euristico, che eseguono ricerca di similarità in banche dati. Anche per loro è possibile differenziare la capacità di identificare allineamenti di tipo globale o locale.


  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion

Fatal error: Call to undefined function federicaDebug() in /usr/local/apache/htdocs/html/footer.php on line 93