ALLINEAMENTI GLOBALI E LOCALI ALLINEAMENTI GLOBALI E LOCALI Consideriamo i seguenti due differenti allineamenti delle stesse sequenze

Nel primo caso si hanno 14 identità (evidenziate dalle linee verticali che uniscono aminoacidi uguali) e tre sostituzioni conservative (es. A-I, S-T) distribuite su tutta la lunghezza della sequenza. Nel secondo caso si hanno 13 identità ed una sostituzione conservativa su una regione di 14 aminoacidi.Quale dei due allineamenti è da considerarsi migliore?(N.B. L’allineamento globale, secondo alcuni, dovrebbe comprendere l’intera lunghezza di entrambe le sequenze; nell’esempio dovrebbero essere quindi aggiunti un gap all’inizio ed uno alla fine)

ALLINEAMENTI GLOBALI O ALLINEAMENTI GLOBALI O LOCALI? LOCALI?

Dal punto di vista biologico generalmente vengono privilegiati gli allineamenti locali, che riguardano regioni limitate delle proteine o di acidi nucleici.

In Biologia Molecolare avrete sicuramente sentito parlare di domini delle proteine o anche degli acidi nucleici. Se ad esempio siamo interessati a trovare tutte le sequenze di proteine di una banca dati che contengono un certo dominio, allora sicuramente si cercheranno similarità locali.

Gli allineamenti globali vengono applicati quando si vogliono confrontare accuratamente due sequenze in cui la similarità sia estesa per tutta la lunghezza

N.B. Un allineamento locale non è necessariamente limitato ad una piccola regione della sequenza, ma potrebbe estendersi anche all’intera lunghezza della sequenza.

Programmazione dinamicaProgrammazione dinamicaFornisce l’allineamento ottimale tra due

sequenzesemplici variazioni dell’algoritmo

producono allineamento globali o localil’allineamento calcolato dipende dalla scelta

di alcuni parametri

ALGORITMO “DINAMICI” DI ALGORITMO “DINAMICI” DI ALLINEAMENTO ALLINEAMENTO

Ora inizieremo a considerare alcuni algoritmi esatti di allineamento in grado di determinare il miglior allineamento possibile tra due sequenze in base ad una certa matrice di sostituzione (scelta a seconda della distanza “evolutiva” tra le due sequenze) e ad un criterio di penalità da attribuire ai gap inseriti.

Needleman e Wunsch nel 1970 furono i primi a risolvere il problema con un algoritmo in grado di trovare similarità globali in un tempo proporzionale al prodotto della lunghezza delle due sequenze.

Nel 1981 Smith e Waterman svilupparono un nuovo algoritmo in grado di individuare anche similarità locali.

Entrambi questi algoritmi sono basati su un approccio informatico chiamato di “programmazione dinamica”.

abbiamo visto che per generare e valutare il miglior allineamento di due sequenze di lunghezza m e n, è necessario effettuare mxn confronti

il numero di operazioni da effettuare cresce e i tempi di calcolo di conseguenza si allungano se si vogliono considerare anche i possibili gap in tutte le posizioni (e di tutte le lunghezze possibili) di entrambe le sequenze

IPLMTRWDQEQESDFGHKLPIYTREWCTRG            |||||||||| CHKIPLMTRWDQQESDFGHKLPVIYTREW

IPLMTRWDQEQESDFGHKLP-IYTREWCTRG   ||||||||| |||||||||| |||||| CHKIPLMTRWDQ-QESDFGHKLPVIYTREW

• punteggi diversi per ogni possibile coppia di residui allineati (matrici di sostituzione)

• gap penalties e

•gap extension penalties per valutare penalizzazioni dovute all’introduzione di gap nelle sequenze allineate

ora bisogna trovare il modo di utilizzare tutti gli strumenti e le valutazioni messe a punto finora senza superare la soglia di complessità di calcolo [ O(mxn) ] che renderebbe il problema non applicabile alle ricerche di similarità in banche dati

abbiamo definito un modo sofisticato di valutare il punteggio di un allineamento, che tenga conto di

allineamenti tra due sequenze - programmazione dinamica

buone notizie: la programmazione dinamica è in grado di trovare il miglior allineamento globale tra due sequenze

cattive notizie: 1) spesso l’output mostra più allineamenti

DIVERSI col massimo del punteggio2) ci mette TROPPO TEMPO per effettuare una

ricerca esaustiva

Algoritmi dinamici di allineamento

dividiamo la procedura in 3 passi successivi

1) consideriamo le due sequenze da allineare in una specie di dot matrix : nelle caselle scriviamo i punteggi in rosso derivati dalla matrice di sostituzione scelta

QERTY|||:QERS

allineamento punteggio

QQ + EE + RR + TS =

4 + 4 + 6 + 1 = 15

Q E R T YQ 4 2 1 -1 -4E 2 4 -1 0 -4R 1 -1 6 -1 -4S -1 0 0 1 -3

cominciamo a calcolare la matrice di questo allineamento usata nell’algoritmo di programmazione dinamica

calcolando le somme lungo le diagonali, effettueremmo un’operazione equivalente al calcolo dei punteggi ottenuto facendo scorrere le due sequenze l’una sull’altra

resterebbe aperto il problema della valutazione dei gap

passo 2 della procedura:ricerca del percorso che consente di ottenere il

massimo punteggio in base a delle regole stabilite, tenendo anche conto dei gap

Algoritmi dinamici di allineamento

qualche semplice osservazione ci consente di risparmiare tempo di calcolo:

se una sequenza è scritta da sinistra a destra e l’altra dall'alto in basso, allora qualsiasi percorso valido deve mantenere sempre una direzione tendenziale che va dall'angolo in alto a sinistra a quello in basso a destra

Misura della similarità:i punteggi in diagonale si SOMMANOfuori dalla diagonale, si PENALIZZA di 5 punti

vediamo quindi come si calcolano le cifre riportate in nero nella matrice

evidenzieremo poi in grigio il migliore percorso all’interno della matrice, secondo le regole e i punteggi stabiliti

il migliore allineamento globale per le sequenze in matrice risulta quindi il seguente:

TFDERILGVQ-TYWAECLA || | | | . || QTFWECIKGDNATY

per ricostruire l’allineamento migliore si può memorizzare il percorso disegnato riempiendo la matrice

alla fine bisogna partire dalla casella a punteggio maggiore e ricostruire il percorso a ritroso seguendo le freccette

TFDERILGVQ-TYWAECLA || | | | . ||QTFWECIKGDNATY

PERCORSI VALIDIPERCORSI VALIDIUn allineamento tra le due sequenze è rappresentato da un percorso all’interno della matrice, avente direzione tendenziale dall’angolo in alto a sinistra all’angolo in basso a destra (frecce nere di figura).Non avrebbero senso percorsi da destra a sinistra o dal basso verso l’alto: ciò significherebbe considerare nuovamente un aminoacido già allineato (una sorta di ripiegamento).Spostamenti orizzontali o verticali equivalgono all’inserimento di gap allineati con il simbolo che si raggiunge nella nuova riga o colonna

PUNTEGGI PUNTEGGI In ogni casella viene memorizzato il punteggio dell’allineamento fino a quella casella.La “programmazione dinamica” consiste proprio nell’assegnare un valore ad ogni casella della matrice di allineamento a partire dai valori contenuti nelle tre caselle adiacenti (raffigurate con il “?” in figura) che a loro volta saranno state calcolate precedentemente. L’algoritmo infatti procede da sinistra a destra lungo le righe della matrice e terminata una riga passa alla riga successiva. Se vengono predefinite la prima riga e la prima colonna, l’algoritmo è quindi in grado di riempire automaticamente tutto il resto della matrice.

PERCORSO OTTIMALE: ALL. PERCORSO OTTIMALE: ALL. GLOBALI GLOBALI

Così come è stato ideato da N. & W. l’allineamento globale comprende l’intera lunghezza di entrambe le sequenze e pertanto un percorso ottimale inizierà necessariamente dall’angolo in alto a sinistra della matrice e terminerà nella casella in basso a destra (che conterrà anche il punteggio dell’allineamento ottimo globale).

abbiamo deciso di trascurare i gap iniziali e finali nelle due sequenze, per cui gli allineamenti “globali” che consideriamo sono quelli che iniziano dalla prima riga o dalla prima colonna e terminano nell’ultima riga o nell’ultima colonna.Per individuare l’allineamento ottimale è sufficiente individuare appunto nell’ultima riga o colonna la casella con il massimo punteggio e poi ricostruire il percorso che ha portato a quella casella a partire da una casella della prima riga o colonna

ALLINEAMENTO GLOBALE ALLINEAMENTO GLOBALE

Nella versione di allineamento globale viene effettuata una sorta di pre-elaborazione, che consiste nel riportare tutti i punteggi di allineamento per ogni possibile coppia di simboli che si incontrerà nella matrice, in maniera da averli già tutti pronti e non doverli cercare successivamente nella matrice di sostituzione.

E’ da notare che anche la matrice di sostituzione usata non è una classica PAM o BLOSUM ma è stata normalizzata in modo da non contenere valori negativi. In questo modo si garantisce che il punteggio dell’allineamento non diminuirà spostandosi verso destra e verso il basso nella matrice di allineamento.

Smith & Waterman (1981)Smith & Waterman (1981)

Allineamento locale– Il sistema di punteggio deve includere valori

negativi per amminoacidi diversi– quando il valore della matrice diventa negativo,

allora viene fissato a 0– l’allineamento viene prodotto a partire dalla

casella che contiene il valore massimo attraverso un retropercorso che si ferma ad una casella con valore 0

Algoritmi dinamici di allineamento

é importante notare che il punteggio è massimo in senso relativo

il valore assoluto dei punteggi che associamo agli allineamenti dipende dai valori contenuti nella matrice di sostituzione che utilizziamo

ci sono matrici i cui valori variano tra 0 e 100, altre che variano da -1 a +1, adottando punteggi decimali

Algoritmi dinamici di allineamento

L’ algoritmo di Needleman e Wunsch è stato sviluppato per l’allineamento globale

L’ algoritmo di Smith e Waterman è stato sviluppato per l’allineamento locale

Ma ciò che realmente fa diventare un algoritmo di questo tipo locale o globale è il tipo di matrice di sostituzione che si usa: se contiene solo valori + allineamenti globalise contiene valori +/- allineamenti locali

RICOSTRUZIONE ALLINEAMENTO RICOSTRUZIONE ALLINEAMENTO Proviamo a ricostruire l’allineamento “globale” trovato come ottimo nell’esempio.Si parte dalla casella con il valore 66 (quella con il valore massimo nell’ultima riga o colonna).Il 66 è stato ottenuto da 56+10, da 59-5 o da 51-5? Da 56+10 e quindi si può allineare Y con Y.Il 56 da dove è stato ottenuto? Da 57-5, da45-5 o da 48+8?.....

N&W SU EMBOSS N&W SU EMBOSS

Sempre sul sito GUI di EMBOSS

http://bioinfo.pbi.nrc.ca:8090/EMBOSS/

è disponibile una versione eseguibile sul WEB dell’algoritmo di Needleman & Wunsch (needle).

PARAMETRI PARAMETRI In genere si lasciano i parametri prefissati, però è possibile cambiare il punteggio attribuito all’apertura di un gap (10) e alla sua estensione (0.5).

Anche la matrice di sostituzione può essere scelta, a seconda della distanza filogenetica tra le sequenze da confrontare

ESEMPIO ESEMPIO Proviamo a confontare le due diverse proteine derivanti dallo stesso gene “subunità 1A di rubisco” di Arabidopsis thaliana

ESEMPIO ESEMPIO Accediamo al record del gene e attraverso i link ai due diversi record delle proteine (hanno i codici NP_176880 e NP_974098)

Link ai record delle proteinecorrispondenti (nel database PROTEIN)

Link ai record dei mRNAcorrispondenti (nel database GENBANK)

ESEMPIO ESEMPIO Codici GENBANK : 15219826 e 42572015Codici REFSEQ (database composto di sequenze “pulite e verificate” di mRNA e PROTEINE: NP_176880 e NP_974098

180 AA

136 AA

ESEMPIOESEMPIO

ESEMPIOESEMPIO

| Aminoacidi conservati: Aminoacidi sostituiti in modo conservativo

ALTRO ESEMPIO ALTRO ESEMPIO Proviamo ad allineare anche le due sequenze nucleotidiche dei mRNA delle due varianti della 1A di rubisco di arabidopsis (clickare sui link mRNA dal record di GENE )

ALTRO ESEMPIO ALTRO ESEMPIO Proviamo ad allineare anche le due sequenze nucleotidiche dei mRNA delle due varianti della 1A di rubisco di arabidopsis (clickare sui link mRNA dal record di GENE )

S&W SU EMBOSS S&W SU EMBOSS

Sempre sul sito GUI di EMBOSS

http://bioinfo.pbi.nrc.ca:8090/EMBOSS/

è disponibile una versione eseguibile sul WEB dell’algoritmo di Smith & Waterman (water).

ESEMPIO ESEMPIO Sempre le due varianti della 1A di rubisco di arabidopsis

ESEMPIO ESEMPIO

ALTRO ESEMPIO ALTRO ESEMPIO Proviamo anche con le due sequenze nucleotidiche

METODI EURISTICI METODI EURISTICI I programmi dinamici visti sinora (N&W e S&W) sono ideali per allineare sequenze in modo esatto, ma sono troppo lenti per effettuare ricerche di similarità in banche dati (abbiamo visto le dimensioni delle banche dati...).Per allineare due sequenze di mille basi servono 1000x1000 operazioni=1.000.000. Anche contando un centesimo di secondo per allineamento provate ad immaginare una ricerca in un database di milioni di sequenze... Richiederebbe decine di migliaia di secondi cioè diverse ore!

Perciò sono stati ideati dei programmi molto più veloci ma “approssimati” che rinunciano ad un po’ di precisione (non è garantito che la sequenza indicata come più simile lo sia effettivamente!).

FASTA FASTA Sviluppato da Lipman e Pearson nel 1985.Effettua una indicizzazione di parole (ktup=2 per proteine (400 possibilità) e ktup=6 per acidi nucleici), cioè un elenco delle posizioni in cui compaiono tutte le possibili parole di quella lunghezza, sia per query, sia per ogni sequenza (subject) del database.Ogni volta che una parola è trovata su entrambe le sequenze questa è rappresentata come diagonale (fig. A). Il programma poi assegnando degli score cerca di unire più diagonali in modo da trovare il percorso migliore

SERVER WEB FASTA SERVER WEB FASTA http://www.ebi.ac.uk/fasta33/

ESEMPIO ESECUZIONE ESEMPIO ESECUZIONE Proviamo a cercare nel database SWISSPROT la solita sequenza proteica della subunità 1A di RUBISCO

Si può subito notare il tempo impiegato per la ricerca!

RISULTATI RISULTATI Elenco delle proteine più simili trovate

E-VALUE E-VALUE I programmi di ricerca di similarità restituiscono un E-VALUE come indice della bontà dell’allineamento.Tale valore (che dipende da molti fattori, tra cui la lunghezza della sequenza query, la lunghezza del match trovato, la dimensione del database su cui si è effettuata la ricerca...) rappresenta la probabilità che tale allineamento sia dovuto al caso.Quanto più tale valore è prossimo allo 0 tanto migliore è l’allineamento. In genere viene usata la notazione scientifica per esprimere l’e-value.

1.9e-110 significa 10 elevato alla –110 quindi un valore molto prossimo allo 0!0.1 invece significa che una volta su 10 si può ottenere casualmente lo stesso allineamento

BLAST BLAST Basic Local Alignment Search Tool è stato sviluppato (e successivamente) migliorato da Altschul ed altri ricercatori del NCBI a partire dal 1990.Anche BLAST effettua una indicizzazione di parole. Si crea un indice di parole di una certa lunghezza (es W=3 per le proteine). Per ogni parola di lunghezza W della query viene generata una lista di parole affini (W-mers) che producono uno score superiore ad una soglia T se allineati con la parola della sequenza query. Si cercano quindi in tutte le sequenze della banca dati le W-mers. BLAST cerca quindi di estendere l’allineamento in entrambe le direzioni, ottenendo dei segmenti HSP di allineamento locale non ulteriormente estensibili.

LE VERSIONI DI BLAST LE VERSIONI DI BLAST Esistono differenti versioni di BLAST a seconda della natura della sequenza query e del database.

BLASTN: query nucleotidi, database nucleotidiBLASTP: query aminoacidi, database aminoacidiBLASTX: query nucleotidi (tradotta nei 6 possibili frame), database aminoacTBLASTN: query aminoacidi, database nucleotidi (tradotto nei 6 frame)TBLASTX: query nucleotidi (tradotta), database nucleotidi (tradotto)

A

N

A

N

A

Nblastn

blastp

blastx

QUERY DATABASECONFRONTO A LIVELLO?

tblastn

tblastx

SERVER WEB BLAST SERVER WEB BLAST http://www.ncbi.nih.gov/BLAST/ (cercare NCBI BLAST)

TUTORIAL BLAST TUTORIAL BLAST http://www.ncbi.nlm.nih.gov/Education/BLASTinfo/information3.html

BLASTP BLASTP sequenza query

database

matrice

mascheramento repeat

BLASTP BLASTP

BLASTP BLASTP

visualizzazione

grafica degli

allineamenti

colori

BLASTP BLASTP

ALTRI BLAST ALTRI BLAST PSI-BLASTusa una ricerca iterativa. Le sequenze trovate in ogni ciclo sono usate per costruire un modello di sequenza da cercare nel ciclo successivo. In questo modo si trovano sequenze simili a quelle simili trovate in un solo passo!

BLAST2SEQUENCEEffettua il BLAST tra due sequenze

sequenza querysequenze simili alla query(primo ciclo di BLAST)

secondo ciclo di BLAST

questa sequenza potrebbeessere particolarmente

interessante ma non l’avrei trovata con un semplice BLAST

ESEMPIO BLAST2SEQUENCEESEMPIO BLAST2SEQUENCEProviamo ad allineare con il BLAST2SEQUENCE le solite due sequenze nucleotidiche

ESEMPIO BLAST2SEQUENCEESEMPIO BLAST2SEQUENCEVengono trovati due allineamenti locali