Allineamento Pairwise e Multiplo di Bio-Sequenze

Allineamento Pairwise e

Multiplo di Bio-Sequenze

Confronto fra BiosequenzeConfronto fra BiosequenzeConfronto fra BiosequenzeConfronto fra Biosequenze I polimeri biologici a più alto ocntenuto di informazione I polimeri biologici a più alto ocntenuto di informazione

sono gli acidi nucleici e le proteine.sono gli acidi nucleici e le proteine. Le unità informative di base sono rispettivamente le 4 Le unità informative di base sono rispettivamente le 4

basi azotate ed i 20 aminocidi.basi azotate ed i 20 aminocidi.

Perché è possibile confrontare biosequenze?Perché è possibile confrontare biosequenze? Quali sono gli obiettivi di un confronto di Quali sono gli obiettivi di un confronto di

sequenze?sequenze? Filogenesi molecolare;Filogenesi molecolare; Evoluzione dei singoli genomi (confronto tra banche Evoluzione dei singoli genomi (confronto tra banche

dati);dati); Caratterizzazione di proteine con funzione Caratterizzazione di proteine con funzione

sconosciuta (ed identificazione di domini funzionali).sconosciuta (ed identificazione di domini funzionali). Possibilità di identificare mutazioni responsabili di un Possibilità di identificare mutazioni responsabili di un

fenotipofenotipo

I polimeri biologici a più alto ocntenuto di informazione I polimeri biologici a più alto ocntenuto di informazione sono gli acidi nucleici e le proteine.sono gli acidi nucleici e le proteine.

Le unità informative di base sono rispettivamente le 4 Le unità informative di base sono rispettivamente le 4 basi azotate ed i 20 aminocidi.basi azotate ed i 20 aminocidi.

Perché è possibile confrontare biosequenze?Perché è possibile confrontare biosequenze? Quali sono gli obiettivi di un confronto di Quali sono gli obiettivi di un confronto di

sequenze?sequenze? Filogenesi molecolare;Filogenesi molecolare; Evoluzione dei singoli genomi (confronto tra banche Evoluzione dei singoli genomi (confronto tra banche

dati);dati); Caratterizzazione di proteine con funzione Caratterizzazione di proteine con funzione

sconosciuta (ed identificazione di domini funzionali).sconosciuta (ed identificazione di domini funzionali). Possibilità di identificare mutazioni responsabili di un Possibilità di identificare mutazioni responsabili di un

fenotipofenotipo

Confronto fra biosequenze Confronto fra biosequenze (2)(2)

Confronto fra biosequenze Confronto fra biosequenze (2)(2)

La filogenesi classica è basata La filogenesi classica è basata sull’osservazione di caratteristiche sull’osservazione di caratteristiche morfologiche e fisologiche.morfologiche e fisologiche.

La La filogenesi molecolarefilogenesi molecolare è basata sulla è basata sulla tendenza a divergere che hanno sequenze tendenza a divergere che hanno sequenze nucleotidiche o aminoacidiche originatesi nucleotidiche o aminoacidiche originatesi da un progenitore comune. Consente di da un progenitore comune. Consente di costruire alberi filogenetici che illustrino le costruire alberi filogenetici che illustrino le distanze ed i rapporti evolutivi tra le distanze ed i rapporti evolutivi tra le molecole analizzate.molecole analizzate.

La filogenesi classica è basata La filogenesi classica è basata sull’osservazione di caratteristiche sull’osservazione di caratteristiche morfologiche e fisologiche.morfologiche e fisologiche.

La La filogenesi molecolarefilogenesi molecolare è basata sulla è basata sulla tendenza a divergere che hanno sequenze tendenza a divergere che hanno sequenze nucleotidiche o aminoacidiche originatesi nucleotidiche o aminoacidiche originatesi da un progenitore comune. Consente di da un progenitore comune. Consente di costruire alberi filogenetici che illustrino le costruire alberi filogenetici che illustrino le distanze ed i rapporti evolutivi tra le distanze ed i rapporti evolutivi tra le molecole analizzate.molecole analizzate.

Similarità e OmologiaSimilarità e OmologiaSimilarità e OmologiaSimilarità e Omologia Similarità: somiglianza nella composizione di Similarità: somiglianza nella composizione di

due sequenze biologichedue sequenze biologiche Omologia: relazione filogenetica tra due Omologia: relazione filogenetica tra due

sequenze.sequenze.

Spesso 2 sequenze omologhe hanno un elevato Spesso 2 sequenze omologhe hanno un elevato grado di omologia, ma possono divergere per grado di omologia, ma possono divergere per mutazione ed evoluzione: possono restare mutazione ed evoluzione: possono restare omologhe anche se non troppo simili.omologhe anche se non troppo simili.

Le regioni che tendono a restare simili sono Le regioni che tendono a restare simili sono quelle più importanti per l’attività della quelle più importanti per l’attività della proteinaproteina

Similarità: somiglianza nella composizione di Similarità: somiglianza nella composizione di due sequenze biologichedue sequenze biologiche

Omologia: relazione filogenetica tra due Omologia: relazione filogenetica tra due sequenze.sequenze.

Spesso 2 sequenze omologhe hanno un elevato Spesso 2 sequenze omologhe hanno un elevato grado di omologia, ma possono divergere per grado di omologia, ma possono divergere per mutazione ed evoluzione: possono restare mutazione ed evoluzione: possono restare omologhe anche se non troppo simili.omologhe anche se non troppo simili.

Le regioni che tendono a restare simili sono Le regioni che tendono a restare simili sono quelle più importanti per l’attività della quelle più importanti per l’attività della proteinaproteina

Allineamento di sequenzeAllineamento di sequenzeAllineamento di sequenzeAllineamento di sequenze

Per poter procedere al confronto tra sequenze Per poter procedere al confronto tra sequenze nucleotidiche o tra sequenze proteiche è necessario nucleotidiche o tra sequenze proteiche è necessario che queste sequenze venganoche queste sequenze vengano allineate allineate..

Questo è un esempio di allineamento multiplo di 5 Questo è un esempio di allineamento multiplo di 5 brevi sequenze aminoacidiche.brevi sequenze aminoacidiche.

Per poter procedere al confronto tra sequenze Per poter procedere al confronto tra sequenze nucleotidiche o tra sequenze proteiche è necessario nucleotidiche o tra sequenze proteiche è necessario che queste sequenze venganoche queste sequenze vengano allineate allineate..

Questo è un esempio di allineamento multiplo di 5 Questo è un esempio di allineamento multiplo di 5 brevi sequenze aminoacidiche.brevi sequenze aminoacidiche.

Allineamento di stringheAllineamento di stringheAllineamento di stringheAllineamento di stringhe Cominciamo con l’affrontare il problema più Cominciamo con l’affrontare il problema più

generale dell’allineamento di una coppia di generale dell’allineamento di una coppia di stringhe.stringhe.

Date due stringhe acbcdb e cadbd, in che modo Date due stringhe acbcdb e cadbd, in che modo possiamo stabilire quanto sono simili?possiamo stabilire quanto sono simili?

La similarità scaturisce dall’allineamento ottimale La similarità scaturisce dall’allineamento ottimale delle due stringhe. Ecco un possibile allineamento:delle due stringhe. Ecco un possibile allineamento:

a c - - b c d ba c - - b c d b- c a d b - d -- c a d b - d -

Il carattere speciale “-” rappresenta l’inserimento Il carattere speciale “-” rappresenta l’inserimento di uno spazio, che sta a significare una di uno spazio, che sta a significare una cancellazione nella sequenza o, equivalentemente, cancellazione nella sequenza o, equivalentemente, un’inserzione nell’altra sequenza (Operazioni di un’inserzione nell’altra sequenza (Operazioni di INDEL).INDEL).

Cominciamo con l’affrontare il problema più Cominciamo con l’affrontare il problema più generale dell’allineamento di una coppia di generale dell’allineamento di una coppia di stringhe.stringhe.

Date due stringhe acbcdb e cadbd, in che modo Date due stringhe acbcdb e cadbd, in che modo possiamo stabilire quanto sono simili?possiamo stabilire quanto sono simili?

La similarità scaturisce dall’allineamento ottimale La similarità scaturisce dall’allineamento ottimale delle due stringhe. Ecco un possibile allineamento:delle due stringhe. Ecco un possibile allineamento:

a c - - b c d ba c - - b c d b- c a d b - d -- c a d b - d -

Il carattere speciale “-” rappresenta l’inserimento Il carattere speciale “-” rappresenta l’inserimento di uno spazio, che sta a significare una di uno spazio, che sta a significare una cancellazione nella sequenza o, equivalentemente, cancellazione nella sequenza o, equivalentemente, un’inserzione nell’altra sequenza (Operazioni di un’inserzione nell’altra sequenza (Operazioni di INDEL).INDEL).

Similarità e distanzaSimilarità e distanzaSimilarità e distanzaSimilarità e distanza

a c - c b c d ba c - c b c d b

- c a d b - d -- c a d b - d -

Per valutare il grado di correlazione Per valutare il grado di correlazione tra stringhe possiamo calcolare la tra stringhe possiamo calcolare la similarità o la distanza.similarità o la distanza.

Alta similarità -> bassa distanza, Alta similarità -> bassa distanza, Bassa similarità -> elevata distanza.Bassa similarità -> elevata distanza.

a c - c b c d ba c - c b c d b

- c a d b - d -- c a d b - d -

Per valutare il grado di correlazione Per valutare il grado di correlazione tra stringhe possiamo calcolare la tra stringhe possiamo calcolare la similarità o la distanza.similarità o la distanza.

Alta similarità -> bassa distanza, Alta similarità -> bassa distanza, Bassa similarità -> elevata distanza.Bassa similarità -> elevata distanza.

Distanza di EditingDistanza di EditingDistanza di EditingDistanza di Editing E’ possibile calcolare la distanza tra due stringhe E’ possibile calcolare la distanza tra due stringhe

utilizzando, per esempio, la distanza di editing.utilizzando, per esempio, la distanza di editing. La distanza di editing è definita come il minimo La distanza di editing è definita come il minimo

numero di operazioni da eseguire (inserimenti, numero di operazioni da eseguire (inserimenti, cancellazioni, sostituzioni) per trasformare una cancellazioni, sostituzioni) per trasformare una stringa in un’altra.stringa in un’altra.

In questo caso per trasformare la prima stringa In questo caso per trasformare la prima stringa nella seconda dobbiamo inserire una g, sostituire nella seconda dobbiamo inserire una g, sostituire una c con una t e cancellare una g. La distanza di una c con una t e cancellare una g. La distanza di editing tra le due stringhe è dunque 3.editing tra le due stringhe è dunque 3.

E’ possibile calcolare la distanza tra due stringhe E’ possibile calcolare la distanza tra due stringhe utilizzando, per esempio, la distanza di editing.utilizzando, per esempio, la distanza di editing.

La distanza di editing è definita come il minimo La distanza di editing è definita come il minimo numero di operazioni da eseguire (inserimenti, numero di operazioni da eseguire (inserimenti, cancellazioni, sostituzioni) per trasformare una cancellazioni, sostituzioni) per trasformare una stringa in un’altra.stringa in un’altra.

In questo caso per trasformare la prima stringa In questo caso per trasformare la prima stringa nella seconda dobbiamo inserire una g, sostituire nella seconda dobbiamo inserire una g, sostituire una c con una t e cancellare una g. La distanza di una c con una t e cancellare una g. La distanza di editing tra le due stringhe è dunque 3.editing tra le due stringhe è dunque 3.

a - c c t g aa g c t t - a

La scoring function: La scoring function: similaritàsimilarità

La scoring function: La scoring function: similaritàsimilarità

In generale è possibile valutare il grado di In generale è possibile valutare il grado di similarità o la distanza tra due stringhe, similarità o la distanza tra due stringhe, assegnando un punteggio (score) assegnando un punteggio (score) all’allineamento utilizzando un’opportuna all’allineamento utilizzando un’opportuna scoring functionscoring function..

Per esempio, se assegniamo un punteggio Per esempio, se assegniamo un punteggio di +2 per ogni match esatto e un punteggio di +2 per ogni match esatto e un punteggio di -1 per ogni mismatch o indel, la similarità di -1 per ogni mismatch o indel, la similarità tra le due sequenze secondo l’allineamento tra le due sequenze secondo l’allineamento considerato sarà:considerato sarà:

In generale è possibile valutare il grado di In generale è possibile valutare il grado di similarità o la distanza tra due stringhe, similarità o la distanza tra due stringhe, assegnando un punteggio (score) assegnando un punteggio (score) all’allineamento utilizzando un’opportuna all’allineamento utilizzando un’opportuna scoring functionscoring function..

Per esempio, se assegniamo un punteggio Per esempio, se assegniamo un punteggio di +2 per ogni match esatto e un punteggio di +2 per ogni match esatto e un punteggio di -1 per ogni mismatch o indel, la similarità di -1 per ogni mismatch o indel, la similarità tra le due sequenze secondo l’allineamento tra le due sequenze secondo l’allineamento considerato sarà:considerato sarà:

a c - c b c d ba c a d b - d -

4)1(424 S

La scoring function: La scoring function: distanzadistanza

La scoring function: La scoring function: distanzadistanza

Se assegniamo uno score pari a 0 nel caso Se assegniamo uno score pari a 0 nel caso di matches, pari ad 1 in caso di di matches, pari ad 1 in caso di sostituzione di caratteri e pari a 2 in caso sostituzione di caratteri e pari a 2 in caso di allineamento con uno spazio, la distanza di allineamento con uno spazio, la distanza tra le due stringhe precedenti secondo tra le due stringhe precedenti secondo l’allineamento considerato è:l’allineamento considerato è:

Se assegniamo uno score pari a 0 nel caso Se assegniamo uno score pari a 0 nel caso di matches, pari ad 1 in caso di di matches, pari ad 1 in caso di sostituzione di caratteri e pari a 2 in caso sostituzione di caratteri e pari a 2 in caso di allineamento con uno spazio, la distanza di allineamento con uno spazio, la distanza tra le due stringhe precedenti secondo tra le due stringhe precedenti secondo l’allineamento considerato è:l’allineamento considerato è:

a c - c b c d ba c a d b - d -

7231104 d

La scoring function (2)La scoring function (2)La scoring function (2)La scoring function (2) Più formalmente:Più formalmente: Se Se xx e e yy sono singoli caratteri o spazi, allora con sono singoli caratteri o spazi, allora con

il simbolo denotiamo lo score il simbolo denotiamo lo score dell’allineamento di dell’allineamento di xx con con yy; è la ; è la scoring scoring functionfunction..

Ovviamente possiamo costruire delle scoring Ovviamente possiamo costruire delle scoring function function ad hocad hoc per ogni problema; se, ad per ogni problema; se, ad esempio, volessimo costruire una scoring esempio, volessimo costruire una scoring function per il confronto di aminoacidi, faremmo function per il confronto di aminoacidi, faremmo in modo da tenere presenti le similarità chimico-in modo da tenere presenti le similarità chimico-fisiche e le differenze tra gli aminoacidi stessi.fisiche e le differenze tra gli aminoacidi stessi.

Più formalmente:Più formalmente: Se Se xx e e yy sono singoli caratteri o spazi, allora con sono singoli caratteri o spazi, allora con

il simbolo denotiamo lo score il simbolo denotiamo lo score dell’allineamento di dell’allineamento di xx con con yy; è la ; è la scoring scoring functionfunction..

Ovviamente possiamo costruire delle scoring Ovviamente possiamo costruire delle scoring function function ad hocad hoc per ogni problema; se, ad per ogni problema; se, ad esempio, volessimo costruire una scoring esempio, volessimo costruire una scoring function per il confronto di aminoacidi, faremmo function per il confronto di aminoacidi, faremmo in modo da tenere presenti le similarità chimico-in modo da tenere presenti le similarità chimico-fisiche e le differenze tra gli aminoacidi stessi.fisiche e le differenze tra gli aminoacidi stessi.

),( yx

Allineamento PairwiseAllineamento PairwiseAllineamento PairwiseAllineamento Pairwise Sia S una sequenza. Con il simbolo |S| Sia S una sequenza. Con il simbolo |S|

denotiamo la lunghezza di S e con S[i] denotiamo la lunghezza di S e con S[i] indichiamo l’i-esimo carattere di S.indichiamo l’i-esimo carattere di S.

Con il termine Con il termine residuoresiduo denotiamo un singolo denotiamo un singolo carattere di una sequenza biologica.carattere di una sequenza biologica.

Se ad es. S = acbcdb, avremo |S|=6 e S[3]=b.Se ad es. S = acbcdb, avremo |S|=6 e S[3]=b. Siano S e T due sequenze. Un Siano S e T due sequenze. Un allineamento allineamento

A associa ad S e T le sequenze S’ e T’, che A associa ad S e T le sequenze S’ e T’, che possono contenere simboli di spazio “-”, in possono contenere simboli di spazio “-”, in modo chemodo che |S’|=|T’||S’|=|T’| Rimuovendo gli spazi da S’ e T’ otteniamo S e T.Rimuovendo gli spazi da S’ e T’ otteniamo S e T.

Sia S una sequenza. Con il simbolo |S| Sia S una sequenza. Con il simbolo |S| denotiamo la lunghezza di S e con S[i] denotiamo la lunghezza di S e con S[i] indichiamo l’i-esimo carattere di S.indichiamo l’i-esimo carattere di S.

Con il termine Con il termine residuoresiduo denotiamo un singolo denotiamo un singolo carattere di una sequenza biologica.carattere di una sequenza biologica.

Se ad es. S = acbcdb, avremo |S|=6 e S[3]=b.Se ad es. S = acbcdb, avremo |S|=6 e S[3]=b. Siano S e T due sequenze. Un Siano S e T due sequenze. Un allineamento allineamento

A associa ad S e T le sequenze S’ e T’, che A associa ad S e T le sequenze S’ e T’, che possono contenere simboli di spazio “-”, in possono contenere simboli di spazio “-”, in modo chemodo che |S’|=|T’||S’|=|T’| Rimuovendo gli spazi da S’ e T’ otteniamo S e T.Rimuovendo gli spazi da S’ e T’ otteniamo S e T.

Allineamento PairwiseAllineamento PairwiseAllineamento PairwiseAllineamento Pairwise

Lo score dell’allineamento di una coppia di Lo score dell’allineamento di una coppia di sequenze è dato da:sequenze è dato da:

Dove Dove l l =|S’|=|T’|.=|S’|=|T’|. L’allineamento ottimale di S e T è quello che L’allineamento ottimale di S e T è quello che

massimizza la similarità tra le sequenze o che massimizza la similarità tra le sequenze o che minimizza la loro distanza.minimizza la loro distanza.

Nel seguito utilizzeremo il termine “score” per Nel seguito utilizzeremo il termine “score” per indicare il grado di similarità tra sequenze.indicare il grado di similarità tra sequenze.

Lo score dell’allineamento di una coppia di Lo score dell’allineamento di una coppia di sequenze è dato da:sequenze è dato da:

Dove Dove l l =|S’|=|T’|.=|S’|=|T’|. L’allineamento ottimale di S e T è quello che L’allineamento ottimale di S e T è quello che

massimizza la similarità tra le sequenze o che massimizza la similarità tra le sequenze o che minimizza la loro distanza.minimizza la loro distanza.

Nel seguito utilizzeremo il termine “score” per Nel seguito utilizzeremo il termine “score” per indicare il grado di similarità tra sequenze.indicare il grado di similarità tra sequenze.

l

i

iTiS1

]['],['

Matrici di SostituzioneMatrici di SostituzioneMatrici di SostituzioneMatrici di Sostituzione Un particolare allinemento è casulae o Un particolare allinemento è casulae o

biologicamnete significativo? E’ possibile biologicamnete significativo? E’ possibile quentificare la sua significatività biologica?quentificare la sua significatività biologica?

Abbiamo visto che la scoring function associa Abbiamo visto che la scoring function associa un valore numerico ad ogni coppia di un valore numerico ad ogni coppia di caratteri.caratteri.

Le matrici di sostituzione associano un valore Le matrici di sostituzione associano un valore numerico ad ogni possibile coppia di numerico ad ogni possibile coppia di aminoacidi, tenendo conto delle similarità aminoacidi, tenendo conto delle similarità chimiche tra di essi.chimiche tra di essi.

Tali matrici possono quindi essere utilizzate Tali matrici possono quindi essere utilizzate come scoring functions per l’allineamento di come scoring functions per l’allineamento di proteine.proteine.

Un particolare allinemento è casulae o Un particolare allinemento è casulae o biologicamnete significativo? E’ possibile biologicamnete significativo? E’ possibile quentificare la sua significatività biologica?quentificare la sua significatività biologica?

Abbiamo visto che la scoring function associa Abbiamo visto che la scoring function associa un valore numerico ad ogni coppia di un valore numerico ad ogni coppia di caratteri.caratteri.

Le matrici di sostituzione associano un valore Le matrici di sostituzione associano un valore numerico ad ogni possibile coppia di numerico ad ogni possibile coppia di aminoacidi, tenendo conto delle similarità aminoacidi, tenendo conto delle similarità chimiche tra di essi.chimiche tra di essi.

Tali matrici possono quindi essere utilizzate Tali matrici possono quindi essere utilizzate come scoring functions per l’allineamento di come scoring functions per l’allineamento di proteine.proteine.

Similarità chimica tra Similarità chimica tra aminoacidiaminoacidi

Similarità chimica tra Similarità chimica tra aminoacidiaminoacidi

Matrici PAMMatrici PAMMatrici PAMMatrici PAM Le matrici PAM (Percent Accepted Mutations) Le matrici PAM (Percent Accepted Mutations)

furono sviluppate esaminando le mutazioni furono sviluppate esaminando le mutazioni all’interno di superfamiglie di sequenze all’interno di superfamiglie di sequenze aminoacidiche strettamente correlate tra loro.aminoacidiche strettamente correlate tra loro.

Si notò che le sostituzioni che occorrevano tra Si notò che le sostituzioni che occorrevano tra sequenze strettamente correlate non erano sequenze strettamente correlate non erano casuali.casuali.

Si concluse che alcune sostituzioni di aminoacidi Si concluse che alcune sostituzioni di aminoacidi occorrono più facilmente di altre, probabilmente a occorrono più facilmente di altre, probabilmente a causa del fatto che tali sostituzioni non alterano causa del fatto che tali sostituzioni non alterano significativamente la struttura e la funzione di significativamente la struttura e la funzione di una proteina.una proteina.

Ciò significa che proteine omologhe non devono Ciò significa che proteine omologhe non devono necessariamente avere gli stessi aminoacidi in necessariamente avere gli stessi aminoacidi in ogni posizione.ogni posizione.

Le matrici PAM (Percent Accepted Mutations) Le matrici PAM (Percent Accepted Mutations) furono sviluppate esaminando le mutazioni furono sviluppate esaminando le mutazioni all’interno di superfamiglie di sequenze all’interno di superfamiglie di sequenze aminoacidiche strettamente correlate tra loro.aminoacidiche strettamente correlate tra loro.

Si notò che le sostituzioni che occorrevano tra Si notò che le sostituzioni che occorrevano tra sequenze strettamente correlate non erano sequenze strettamente correlate non erano casuali.casuali.

Si concluse che alcune sostituzioni di aminoacidi Si concluse che alcune sostituzioni di aminoacidi occorrono più facilmente di altre, probabilmente a occorrono più facilmente di altre, probabilmente a causa del fatto che tali sostituzioni non alterano causa del fatto che tali sostituzioni non alterano significativamente la struttura e la funzione di significativamente la struttura e la funzione di una proteina.una proteina.

Ciò significa che proteine omologhe non devono Ciò significa che proteine omologhe non devono necessariamente avere gli stessi aminoacidi in necessariamente avere gli stessi aminoacidi in ogni posizione.ogni posizione.

Unità e matrici PAMUnità e matrici PAMUnità e matrici PAMUnità e matrici PAM

Usiamo le Usiamo le unità PAMunità PAM per misurare la per misurare la distanza tra sequenze aminoacidiche. distanza tra sequenze aminoacidiche.

Due sequenze S1 ed S2 distano Due sequenze S1 ed S2 distano 1 unità PAM1 unità PAM se S1 può essere trasformata in S2 con una se S1 può essere trasformata in S2 con una media di 1 mutazione puntuale ogni 100 media di 1 mutazione puntuale ogni 100 aminoacidi. aminoacidi.

In una sequenza la stessa posizione può In una sequenza la stessa posizione può mutare più volte e tornare quindi al mutare più volte e tornare quindi al carattere originario; dunque due sequenze carattere originario; dunque due sequenze che distano 1 PAM possono differire di che distano 1 PAM possono differire di meno dell’1%.meno dell’1%.

Usiamo le Usiamo le unità PAMunità PAM per misurare la per misurare la distanza tra sequenze aminoacidiche. distanza tra sequenze aminoacidiche.

Due sequenze S1 ed S2 distano Due sequenze S1 ed S2 distano 1 unità PAM1 unità PAM se S1 può essere trasformata in S2 con una se S1 può essere trasformata in S2 con una media di 1 mutazione puntuale ogni 100 media di 1 mutazione puntuale ogni 100 aminoacidi. aminoacidi.

In una sequenza la stessa posizione può In una sequenza la stessa posizione può mutare più volte e tornare quindi al mutare più volte e tornare quindi al carattere originario; dunque due sequenze carattere originario; dunque due sequenze che distano 1 PAM possono differire di che distano 1 PAM possono differire di meno dell’1%.meno dell’1%.

Matrici PAMMatrici PAMMatrici PAMMatrici PAM Esistono diversi tipi di matrici PAM. Ognuna di Esistono diversi tipi di matrici PAM. Ognuna di

esse è utilizzata per confrontare due sequenze esse è utilizzata per confrontare due sequenze che distano un certo numero di unità PAM l’una che distano un certo numero di unità PAM l’una dall’altra.dall’altra.

Ad es. la PAM120 può essere utilizzata per Ad es. la PAM120 può essere utilizzata per confrontare sequenze che distano 120 unità confrontare sequenze che distano 120 unità PAM.PAM.

La entry (i,j) della matrice PAM120 contiene lo La entry (i,j) della matrice PAM120 contiene lo score assegnato alla coppia di aminoacidi score assegnato alla coppia di aminoacidi (Ai,Aj); tale score è proporzionale alla frequenza (Ai,Aj); tale score è proporzionale alla frequenza con cui ci si aspetta che Ai sostituisca Aj in due con cui ci si aspetta che Ai sostituisca Aj in due sequenze che distano 120 unità PAM.sequenze che distano 120 unità PAM.

Esistono diversi tipi di matrici PAM. Ognuna di Esistono diversi tipi di matrici PAM. Ognuna di esse è utilizzata per confrontare due sequenze esse è utilizzata per confrontare due sequenze che distano un certo numero di unità PAM l’una che distano un certo numero di unità PAM l’una dall’altra.dall’altra.

Ad es. la PAM120 può essere utilizzata per Ad es. la PAM120 può essere utilizzata per confrontare sequenze che distano 120 unità confrontare sequenze che distano 120 unità PAM.PAM.

La entry (i,j) della matrice PAM120 contiene lo La entry (i,j) della matrice PAM120 contiene lo score assegnato alla coppia di aminoacidi score assegnato alla coppia di aminoacidi (Ai,Aj); tale score è proporzionale alla frequenza (Ai,Aj); tale score è proporzionale alla frequenza con cui ci si aspetta che Ai sostituisca Aj in due con cui ci si aspetta che Ai sostituisca Aj in due sequenze che distano 120 unità PAM.sequenze che distano 120 unità PAM.

Matrice PAM 120Matrice PAM 120Matrice PAM 120Matrice PAM 120A 2

R -2 6

N 0 0 2

D 0 -1 2 4

C -2 -4 -4 -5 12

Q 0 1 1 2 -5 4

E 0 -1 1 3 -5 2 4

G 1 -3 0 1 -3 -1 0 5

H -1 2 2 1 -3 3 1 -2 6

I -1 -2 -2 -2 -2 -2 -2 -3 -2 5

L -2 -3 -3 -4 -6 -2 -3 -4 -2 2 6

K -1 3 1 0 -5 1 0 -2 0 -2 -3 5

M -1 0 -2 -3 -5 -1 -2 -3 -2 2 4 0 6

F -3 -4 -3 -6 -4 -5 -5 -5 -2 1 2 -5 0 9

P 1 0 0 -1 -3 0 -1 0 0 -2 -3 -1 -2 -5 6

S 1 0 1 0 0 -1 0 1 -1 -1 -3 0 -2 -3 1 2

T 1 -1 0 0 -2 -1 0 0 -1 0 -2 0 -1 -3 0 1 3

W -6 2 -4 -7 -8 -5 -7 -7 -3 -5 -2 -3 -4 0 -6 -2 -5 17

Y -3 -4 -2 -4 0 -4 -4 -5 0 -1 -1 -4 -2 7 -5 -3 -3 0 10

V 0 -2 -2 -2 -2 -2 -2 -1 -2 4 2 -2 2 -1 -1 -1 0 -6 -2 4

A R N D C Q E G H I L K M F P S T W Y V

Matrici BLOSUMMatrici BLOSUMMatrici BLOSUMMatrici BLOSUM Le matrici BLOSUM sono matrici di sostituzione di Le matrici BLOSUM sono matrici di sostituzione di

aminoacidi simili alle PAM.aminoacidi simili alle PAM. Mentre la matrici PAM si basano su allineamenti globali Mentre la matrici PAM si basano su allineamenti globali

tra sequenze, le BLOSUM si basano su allineamenti di tra sequenze, le BLOSUM si basano su allineamenti di blocchi di segmenti di sequenze strettamente correlate.blocchi di segmenti di sequenze strettamente correlate.

I segmenti appartenenti a ciascun blocco vengono I segmenti appartenenti a ciascun blocco vengono suddivisi in clusters in base alla percentuale di suddivisi in clusters in base alla percentuale di similarità. Ogni cluster sarà considerato come un’unica similarità. Ogni cluster sarà considerato come un’unica sequenza.sequenza.

Ad es. nella costruzione della matrice BLOSUM62 ogni Ad es. nella costruzione della matrice BLOSUM62 ogni cluster sarà costituito da sequenze che hanno identità cluster sarà costituito da sequenze che hanno identità superiore al 62%.superiore al 62%.

Anche in questo caso la entry (i,j) della matrice è Anche in questo caso la entry (i,j) della matrice è proporzionale alla frequenza di sostituzione proporzionale alla frequenza di sostituzione dell’aminoacido Ai con l’aminoacido Aj.dell’aminoacido Ai con l’aminoacido Aj.

Le matrici BLOSUM sono matrici di sostituzione di Le matrici BLOSUM sono matrici di sostituzione di aminoacidi simili alle PAM.aminoacidi simili alle PAM.

Mentre la matrici PAM si basano su allineamenti globali Mentre la matrici PAM si basano su allineamenti globali tra sequenze, le BLOSUM si basano su allineamenti di tra sequenze, le BLOSUM si basano su allineamenti di blocchi di segmenti di sequenze strettamente correlate.blocchi di segmenti di sequenze strettamente correlate.

I segmenti appartenenti a ciascun blocco vengono I segmenti appartenenti a ciascun blocco vengono suddivisi in clusters in base alla percentuale di suddivisi in clusters in base alla percentuale di similarità. Ogni cluster sarà considerato come un’unica similarità. Ogni cluster sarà considerato come un’unica sequenza.sequenza.

Ad es. nella costruzione della matrice BLOSUM62 ogni Ad es. nella costruzione della matrice BLOSUM62 ogni cluster sarà costituito da sequenze che hanno identità cluster sarà costituito da sequenze che hanno identità superiore al 62%.superiore al 62%.

Anche in questo caso la entry (i,j) della matrice è Anche in questo caso la entry (i,j) della matrice è proporzionale alla frequenza di sostituzione proporzionale alla frequenza di sostituzione dell’aminoacido Ai con l’aminoacido Aj.dell’aminoacido Ai con l’aminoacido Aj.

GapsGapsGapsGaps Abbiamo visto che due sequenze biologiche Abbiamo visto che due sequenze biologiche

possono differire tra loro non solo per sostituzione possono differire tra loro non solo per sostituzione di un residuo con un altro ma anche per di un residuo con un altro ma anche per inserzione o delezione di residui.inserzione o delezione di residui.

E’ quindi spesso necessario introdurre degli spazi E’ quindi spesso necessario introdurre degli spazi “-” in una o in entrambe le sequenze da allineare, “-” in una o in entrambe le sequenze da allineare, anche al fine di portare le sequenze alla stessa anche al fine di portare le sequenze alla stessa lunghezza.lunghezza.

Una sequenza di spazi contigui si definisce Una sequenza di spazi contigui si definisce gapgap.. Ovviamente è necessario determinare un criterio Ovviamente è necessario determinare un criterio

per l’inserimento di tali gap.per l’inserimento di tali gap. L’inserimento di un gap abbassa lo score L’inserimento di un gap abbassa lo score

dell’allineamento; in questo modo, essendo il dell’allineamento; in questo modo, essendo il nostro scopo quello di massimizzare lo score nostro scopo quello di massimizzare lo score dell’allineamento, verranno inseriti gaps solo dell’allineamento, verranno inseriti gaps solo quando ciò è strettamente necessario.quando ciò è strettamente necessario.

Abbiamo visto che due sequenze biologiche Abbiamo visto che due sequenze biologiche possono differire tra loro non solo per sostituzione possono differire tra loro non solo per sostituzione di un residuo con un altro ma anche per di un residuo con un altro ma anche per inserzione o delezione di residui.inserzione o delezione di residui.

E’ quindi spesso necessario introdurre degli spazi E’ quindi spesso necessario introdurre degli spazi “-” in una o in entrambe le sequenze da allineare, “-” in una o in entrambe le sequenze da allineare, anche al fine di portare le sequenze alla stessa anche al fine di portare le sequenze alla stessa lunghezza.lunghezza.

Una sequenza di spazi contigui si definisce Una sequenza di spazi contigui si definisce gapgap.. Ovviamente è necessario determinare un criterio Ovviamente è necessario determinare un criterio

per l’inserimento di tali gap.per l’inserimento di tali gap. L’inserimento di un gap abbassa lo score L’inserimento di un gap abbassa lo score

dell’allineamento; in questo modo, essendo il dell’allineamento; in questo modo, essendo il nostro scopo quello di massimizzare lo score nostro scopo quello di massimizzare lo score dell’allineamento, verranno inseriti gaps solo dell’allineamento, verranno inseriti gaps solo quando ciò è strettamente necessario.quando ciò è strettamente necessario.

Gap PenaltiesGap PenaltiesGap PenaltiesGap Penalties La maggior parte degli algoritmi di allineamento La maggior parte degli algoritmi di allineamento

usano delle usano delle gap penaltiesgap penalties diverse per l’apertura diverse per l’apertura di un nuovo gap e per l’estensione di un gap già di un nuovo gap e per l’estensione di un gap già esistente.esistente.

Il GOP (Gap Opening Penalty) è la penalità da Il GOP (Gap Opening Penalty) è la penalità da pagare ogni qual volta viene inserito un gap.pagare ogni qual volta viene inserito un gap.

Il GEP (Gap Extension Penalty) è la penalità da Il GEP (Gap Extension Penalty) è la penalità da pagare ogni qual volta viene esteso un gap già pagare ogni qual volta viene esteso un gap già esistente.esistente.

Solitamente GOP>GEP, cioè aprire un nuovo gap Solitamente GOP>GEP, cioè aprire un nuovo gap è più costoso che estenderne uno esistente; in è più costoso che estenderne uno esistente; in questo modo si tende ad avere inserzioni e questo modo si tende ad avere inserzioni e delezioni di parecchi residui per volta piuttosto delezioni di parecchi residui per volta piuttosto che inserzioni o delezioni sparse.che inserzioni o delezioni sparse.

La maggior parte degli algoritmi di allineamento La maggior parte degli algoritmi di allineamento usano delle usano delle gap penaltiesgap penalties diverse per l’apertura diverse per l’apertura di un nuovo gap e per l’estensione di un gap già di un nuovo gap e per l’estensione di un gap già esistente.esistente.

Il GOP (Gap Opening Penalty) è la penalità da Il GOP (Gap Opening Penalty) è la penalità da pagare ogni qual volta viene inserito un gap.pagare ogni qual volta viene inserito un gap.

Il GEP (Gap Extension Penalty) è la penalità da Il GEP (Gap Extension Penalty) è la penalità da pagare ogni qual volta viene esteso un gap già pagare ogni qual volta viene esteso un gap già esistente.esistente.

Solitamente GOP>GEP, cioè aprire un nuovo gap Solitamente GOP>GEP, cioè aprire un nuovo gap è più costoso che estenderne uno esistente; in è più costoso che estenderne uno esistente; in questo modo si tende ad avere inserzioni e questo modo si tende ad avere inserzioni e delezioni di parecchi residui per volta piuttosto delezioni di parecchi residui per volta piuttosto che inserzioni o delezioni sparse.che inserzioni o delezioni sparse.

Gap PenaltiesGap PenaltiesGap PenaltiesGap Penalties

Esempio di apertura di un gap:Esempio di apertura di un gap:

Esempio di estensione di un gap già Esempio di estensione di un gap già esistente:esistente:

Esempio di apertura di un gap:Esempio di apertura di un gap:

Esempio di estensione di un gap già Esempio di estensione di un gap già esistente:esistente:

a c t c a a …

t c a t c a …- t c a t c …

a c t c a a …

- - t c a t …- t c a t c …

Algoritmi per il l’allineamento Algoritmi per il l’allineamento PairwisePairwise

Algoritmi per il l’allineamento Algoritmi per il l’allineamento PairwisePairwise

Come trovare l’allinemento ottimale?Come trovare l’allinemento ottimale? Il metodo più ovvio per determinare Il metodo più ovvio per determinare

l’allineamento ottimale tra due sequenze l’allineamento ottimale tra due sequenze consiste nel costruire tutti i possibili consiste nel costruire tutti i possibili allineamenti e valutare quello con lo score allineamenti e valutare quello con lo score più alto:più alto:

APPROCCIO IMPRATICABILEAPPROCCIO IMPRATICABILE

Allineare sequenze di appena 20 caratteri Allineare sequenze di appena 20 caratteri (lunghezza inusuale per una biosequenza, (lunghezza inusuale per una biosequenza, che solitamente è formata da un numero che solitamente è formata da un numero molto maggiore di caratteri) richiederebbe molto maggiore di caratteri) richiederebbe un tempo sicuramente inaccettabile.un tempo sicuramente inaccettabile.

Come trovare l’allinemento ottimale?Come trovare l’allinemento ottimale? Il metodo più ovvio per determinare Il metodo più ovvio per determinare

l’allineamento ottimale tra due sequenze l’allineamento ottimale tra due sequenze consiste nel costruire tutti i possibili consiste nel costruire tutti i possibili allineamenti e valutare quello con lo score allineamenti e valutare quello con lo score più alto:più alto:

APPROCCIO IMPRATICABILEAPPROCCIO IMPRATICABILE

Allineare sequenze di appena 20 caratteri Allineare sequenze di appena 20 caratteri (lunghezza inusuale per una biosequenza, (lunghezza inusuale per una biosequenza, che solitamente è formata da un numero che solitamente è formata da un numero molto maggiore di caratteri) richiederebbe molto maggiore di caratteri) richiederebbe un tempo sicuramente inaccettabile.un tempo sicuramente inaccettabile.

Allineamento medianteAllineamento medianteProgrammazione DinamicaProgrammazione Dinamica

Allineamento medianteAllineamento medianteProgrammazione DinamicaProgrammazione Dinamica

Date due stringhe S e T, con |S|=n e |T|=m, il Date due stringhe S e T, con |S|=n e |T|=m, il nostro obiettivo è il calcolo dell’allineamento nostro obiettivo è il calcolo dell’allineamento ottimale di S e T.ottimale di S e T.

Gli algoritmi di programmazione dinamica vengono Gli algoritmi di programmazione dinamica vengono utilizzati nella risoluzione di problemi di utilizzati nella risoluzione di problemi di ottimizzazione; nel nostro caso ci interessa ottimizzazione; nel nostro caso ci interessa massimizzare lo score dell’allineamento.massimizzare lo score dell’allineamento.

Un algoritmo di programmazione dinamica trova la Un algoritmo di programmazione dinamica trova la soluzione migliore spezzando il problema originale soluzione migliore spezzando il problema originale in sottoproblemi più semplici da risolvere.in sottoproblemi più semplici da risolvere.

La soluzione di ogni sottoproblema si basa sulle La soluzione di ogni sottoproblema si basa sulle soluzioni dei sottoproblemi già risolti.soluzioni dei sottoproblemi già risolti.

Date due stringhe S e T, con |S|=n e |T|=m, il Date due stringhe S e T, con |S|=n e |T|=m, il nostro obiettivo è il calcolo dell’allineamento nostro obiettivo è il calcolo dell’allineamento ottimale di S e T.ottimale di S e T.

Gli algoritmi di programmazione dinamica vengono Gli algoritmi di programmazione dinamica vengono utilizzati nella risoluzione di problemi di utilizzati nella risoluzione di problemi di ottimizzazione; nel nostro caso ci interessa ottimizzazione; nel nostro caso ci interessa massimizzare lo score dell’allineamento.massimizzare lo score dell’allineamento.

Un algoritmo di programmazione dinamica trova la Un algoritmo di programmazione dinamica trova la soluzione migliore spezzando il problema originale soluzione migliore spezzando il problema originale in sottoproblemi più semplici da risolvere.in sottoproblemi più semplici da risolvere.

La soluzione di ogni sottoproblema si basa sulle La soluzione di ogni sottoproblema si basa sulle soluzioni dei sottoproblemi già risolti.soluzioni dei sottoproblemi già risolti.

Programmazione Dinamica Programmazione Dinamica (2)(2)


Consideriamo l’algoritmo di programmazione Consideriamo l’algoritmo di programmazione dinamica proposto da Needleman & Wunsch (1970).dinamica proposto da Needleman & Wunsch (1970).

Date due sequenze S e T, confrontiamo il primo Date due sequenze S e T, confrontiamo il primo residuo di S con il primo residuo di T considerando i residuo di S con il primo residuo di T considerando i seguenti score:seguenti score:

Ci chiediamo quindi se conviene allineare il primo Ci chiediamo quindi se conviene allineare il primo residuo di S con il primo residuo di T o il primo residuo di S con il primo residuo di T o il primo residuo di S con un gap o il primo residuo di T con residuo di S con un gap o il primo residuo di T con un gap; scegliamo quindi di intraprendere l’azione un gap; scegliamo quindi di intraprendere l’azione cui è associato lo score maggiore.cui è associato lo score maggiore.

Consideriamo l’algoritmo di programmazione Consideriamo l’algoritmo di programmazione dinamica proposto da Needleman & Wunsch (1970).dinamica proposto da Needleman & Wunsch (1970).

Date due sequenze S e T, confrontiamo il primo Date due sequenze S e T, confrontiamo il primo residuo di S con il primo residuo di T considerando i residuo di S con il primo residuo di T considerando i seguenti score:seguenti score:

Ci chiediamo quindi se conviene allineare il primo Ci chiediamo quindi se conviene allineare il primo residuo di S con il primo residuo di T o il primo residuo di S con il primo residuo di T o il primo residuo di S con un gap o il primo residuo di T con residuo di S con un gap o il primo residuo di T con un gap; scegliamo quindi di intraprendere l’azione un gap; scegliamo quindi di intraprendere l’azione cui è associato lo score maggiore.cui è associato lo score maggiore.

])1[,(

)],1[(

])1[],1[(

T

S

TS



Utilizziamo una matrice Utilizziamo una matrice n n xx m m, con |S|=n e |T|, con |S|=n e |T|=m, che andremo a riempire riga per riga:=m, che andremo a riempire riga per riga:

Il valore di ogni entry viene calcolato con la Il valore di ogni entry viene calcolato con la seguente formula:seguente formula:

Caso base:Caso base:

Utilizziamo una matrice Utilizziamo una matrice n n xx m m, con |S|=n e |T|, con |S|=n e |T|=m, che andremo a riempire riga per riga:=m, che andremo a riempire riga per riga:

Il valore di ogni entry viene calcolato con la Il valore di ogni entry viene calcolato con la seguente formula:seguente formula:

Caso base:Caso base:

) ])[,()1,(

),],[(),1(

]),[],[()1,1(max(),(

jTjiV

iSjiV

jTiSjiVjiV

i

kkSiV

0

),()0,(

j

kkTjV

0

),(),0(


• In questo modo ad ogni passo scegliamo il massimo tra gli score che otterremmo allineando il residuo i di S con il residuo j di T, o allineando il residuo i di S con un gap o allineando il residuo j di T con un gap.

) ])[,()1,(

),],[(),1(

]),[],[()1,1(max(),(

jTjiV

iSjiV

jTiSjiVjiV

• Considerando 1),( ,1),( ,2),( cccc

• Avremo:

1)12,11,21max()1,2( V

Programmazione Dinamica (5)Programmazione Dinamica (5)Programmazione Dinamica (5)Programmazione Dinamica (5) La entry (n,m) sarà lo score La entry (n,m) sarà lo score

dell’allineamento:dell’allineamento:

A questo punto come facciamo ad A questo punto come facciamo ad ottenere l’allineamento vero e proprio?ottenere l’allineamento vero e proprio?

La entry (n,m) sarà lo score La entry (n,m) sarà lo score dell’allineamento:dell’allineamento:

A questo punto come facciamo ad A questo punto come facciamo ad ottenere l’allineamento vero e proprio?ottenere l’allineamento vero e proprio?

) ),()4,6(

),,()5,5(

),,()4,5(max()5,6(

dV

bV

dbVV



• Mediante un traceback procediamo a ritroso a partire dalla entry (6,5). Sappiamo che:

• Quindi possiamo risalire scegliendo indifferentemente la entry (6,4) o la entry (5,5)

2)13,13,10max(

Programmazione Dinamica (7)Programmazione Dinamica (7)Programmazione Dinamica (7)Programmazione Dinamica (7)• Seguendo la strada indicata dalle frecce otterremo il seguente allineamento:

a

-

c b c d b -

c a - dbd

Allineamento globale e Allineamento globale e localelocale

Allineamento globale e Allineamento globale e localelocale L’algoritmo di allineamento che abbiamo L’algoritmo di allineamento che abbiamo

considerato, produce l’allineamento globale di considerato, produce l’allineamento globale di due sequenze, ovvero allinea due sequenze su due sequenze, ovvero allinea due sequenze su tutta la loro lunghezza.tutta la loro lunghezza.

Una variante dell’algoritmo di Needleman-Una variante dell’algoritmo di Needleman-Wunsch consente di eseguire l’allineamento Wunsch consente di eseguire l’allineamento locale di due sequenze;locale di due sequenze;

Questo è utile quando abbiamo a che fare con Questo è utile quando abbiamo a che fare con sequenze che non presentano un’alta similarità sequenze che non presentano un’alta similarità su tutta la loro lunghezza ma che contengono su tutta la loro lunghezza ma che contengono comunque regioni ad alta similarità (Vedi BLAST).comunque regioni ad alta similarità (Vedi BLAST).

L’algoritmo di L’algoritmo di local alignmentlocal alignment restituisce gli n restituisce gli n allineamenti di sottosequenze di S e T di massimo allineamenti di sottosequenze di S e T di massimo score.score.

L’algoritmo di allineamento che abbiamo L’algoritmo di allineamento che abbiamo considerato, produce l’allineamento globale di considerato, produce l’allineamento globale di due sequenze, ovvero allinea due sequenze su due sequenze, ovvero allinea due sequenze su tutta la loro lunghezza.tutta la loro lunghezza.

Una variante dell’algoritmo di Needleman-Una variante dell’algoritmo di Needleman-Wunsch consente di eseguire l’allineamento Wunsch consente di eseguire l’allineamento locale di due sequenze;locale di due sequenze;

Questo è utile quando abbiamo a che fare con Questo è utile quando abbiamo a che fare con sequenze che non presentano un’alta similarità sequenze che non presentano un’alta similarità su tutta la loro lunghezza ma che contengono su tutta la loro lunghezza ma che contengono comunque regioni ad alta similarità (Vedi BLAST).comunque regioni ad alta similarità (Vedi BLAST).

L’algoritmo di L’algoritmo di local alignmentlocal alignment restituisce gli n restituisce gli n allineamenti di sottosequenze di S e T di massimo allineamenti di sottosequenze di S e T di massimo score.score.

Allineamento MultiploAllineamento MultiploAllineamento MultiploAllineamento Multiplo Fino ad ora abbiamo visto come produrre Fino ad ora abbiamo visto come produrre

allineamenti di coppie di sequenze. Gli allineamenti di coppie di sequenze. Gli algoritmi visti hanno complessità algoritmi visti hanno complessità quadratica (nella lunghezza delle quadratica (nella lunghezza delle sequenze) in tempo e spazio.sequenze) in tempo e spazio.

La variante di Myers-Miller consente di La variante di Myers-Miller consente di produrre allineamenti di coppie di produrre allineamenti di coppie di sequenze in tempo quadratico e spazio sequenze in tempo quadratico e spazio lineare.lineare.

Il problema dell’allineamento di n sequenze Il problema dell’allineamento di n sequenze non è risolubile in tempo polinomiale. non è risolubile in tempo polinomiale. Occorre quindi ricorrere ad euristiche ed Occorre quindi ricorrere ad euristiche ed approssimazioni.approssimazioni.

Allineamento ProgressivoAllineamento ProgressivoAllineamento ProgressivoAllineamento Progressivo Il metodo più comune per eseguire un Il metodo più comune per eseguire un

allineamento multiplo è il cosiddetto allineamento multiplo è il cosiddetto allineamento allineamento progressivoprogressivo, basato sulla costruzione di una , basato sulla costruzione di una successione di allineamenti a coppie.successione di allineamenti a coppie.

Dato un insieme Dato un insieme SS costituito da costituito da nn sequenze da sequenze da allineare, si scelgono due sequenze s1 ed s2 e si allineare, si scelgono due sequenze s1 ed s2 e si allineano; questo allineamento rimane fissato nei allineano; questo allineamento rimane fissato nei passi successivi.passi successivi.

Si sceglie quindi una terza sequenza s3 e si Si sceglie quindi una terza sequenza s3 e si allinea al precedente allineamento, e così via.allinea al precedente allineamento, e così via.

Questo è un approccio euristico e non garantisce Questo è un approccio euristico e non garantisce di trovare l’allineamento multiplo ottimale; di trovare l’allineamento multiplo ottimale; tuttavia è efficiente e nella pratica dà dei risultati tuttavia è efficiente e nella pratica dà dei risultati ragionevoli.ragionevoli.

Il metodo più comune per eseguire un Il metodo più comune per eseguire un allineamento multiplo è il cosiddetto allineamento multiplo è il cosiddetto allineamento allineamento progressivoprogressivo, basato sulla costruzione di una , basato sulla costruzione di una successione di allineamenti a coppie.successione di allineamenti a coppie.

Dato un insieme Dato un insieme SS costituito da costituito da nn sequenze da sequenze da allineare, si scelgono due sequenze s1 ed s2 e si allineare, si scelgono due sequenze s1 ed s2 e si allineano; questo allineamento rimane fissato nei allineano; questo allineamento rimane fissato nei passi successivi.passi successivi.

Si sceglie quindi una terza sequenza s3 e si Si sceglie quindi una terza sequenza s3 e si allinea al precedente allineamento, e così via.allinea al precedente allineamento, e così via.

Questo è un approccio euristico e non garantisce Questo è un approccio euristico e non garantisce di trovare l’allineamento multiplo ottimale; di trovare l’allineamento multiplo ottimale; tuttavia è efficiente e nella pratica dà dei risultati tuttavia è efficiente e nella pratica dà dei risultati ragionevoli.ragionevoli.

Allineamento Progressivo Allineamento Progressivo (2)(2)

L’euristica più importante utilizzata negli algoritmi L’euristica più importante utilizzata negli algoritmi di allineamento progressivo prevede che le coppie di allineamento progressivo prevede che le coppie che presentano un maggior grado di similarità che presentano un maggior grado di similarità siano allineate per prime.siano allineate per prime.

Ciò è giustificato dal fatto che coppie di sequenze Ciò è giustificato dal fatto che coppie di sequenze maggiormente somiglianti hanno maggiore maggiormente somiglianti hanno maggiore probabilità di essere derivate più recentemente da probabilità di essere derivate più recentemente da un antenato comune e quindi il loro allineamento un antenato comune e quindi il loro allineamento fornisce l’informazione più affidabile che è fornisce l’informazione più affidabile che è possibile ricavare dalle sequenze.possibile ricavare dalle sequenze.

Inoltre le posizioni dei gaps in sequenze Inoltre le posizioni dei gaps in sequenze maggiormente correlate sono tipicamente più maggiormente correlate sono tipicamente più accurate rispetto a quelle relative a sequenze accurate rispetto a quelle relative a sequenze meno simili, per cui i gaps degli allineamenti meno simili, per cui i gaps degli allineamenti iniziali vanno preservati durante l’allineamento iniziali vanno preservati durante l’allineamento progressivo. progressivo.

ClustalWClustalWClustalWClustalW

ClustalW è il tool più popolare per l’allineamento ClustalW è il tool più popolare per l’allineamento multiplo di biosequenze.multiplo di biosequenze.

Dato un insiemeDato un insieme S S di di nn sequenze da allineare, sequenze da allineare, ClustalW allinea tutte le coppie di sequenze di ClustalW allinea tutte le coppie di sequenze di SS separatamente e costruisce una matrice con le separatamente e costruisce una matrice con le distanze tra ogni coppia di sequenze.distanze tra ogni coppia di sequenze.

ClustalW è il tool più popolare per l’allineamento ClustalW è il tool più popolare per l’allineamento multiplo di biosequenze.multiplo di biosequenze.

Dato un insiemeDato un insieme S S di di nn sequenze da allineare, sequenze da allineare, ClustalW allinea tutte le coppie di sequenze di ClustalW allinea tutte le coppie di sequenze di SS separatamente e costruisce una matrice con le separatamente e costruisce una matrice con le distanze tra ogni coppia di sequenze.distanze tra ogni coppia di sequenze.

Seq. Seq. AA

Seq. Seq. BB

Seq. Seq. CC

Seq. Seq. DD

Seq. Seq. AA

0.000.00

Seq. Seq. B B

0.110.11 0.000.00

Seq. Seq. CC

0.320.32 0.430.43 0.000.00

Seq. Seq. DD

0.170.17 0.180.18 0.570.57 0.000.00

ClustalW: Albero ClustalW: Albero filogeneticofilogenetico

Viene quindi costruito un albero guida filogenetico Viene quindi costruito un albero guida filogenetico utilizzando il metodo utilizzando il metodo neighbour-joiningneighbour-joining..

Si sceglie la coppia più vicina: questa andrà a Si sceglie la coppia più vicina: questa andrà a formare il primo sottoalbero:formare il primo sottoalbero:

Viene quindi costruito un albero guida filogenetico Viene quindi costruito un albero guida filogenetico utilizzando il metodo utilizzando il metodo neighbour-joiningneighbour-joining..

Si sceglie la coppia più vicina: questa andrà a Si sceglie la coppia più vicina: questa andrà a formare il primo sottoalbero:formare il primo sottoalbero:

AB

A B

Seq. Seq. AA

Seq. Seq. BB

Seq. Seq. CC

Seq. Seq. DD

Seq. Seq. AA

0.000.00

Seq. Seq. B B

0.110.11 0.000.00

Seq. Seq. CC

0.320.32 0.430.43 0.000.00

Seq. Seq. DD

0.170.17 0.180.18 0.570.57 0.000.00

ClustalW: Albero filogenetico ClustalW: Albero filogenetico (2)(2)

375.02

43.032.02

),(),(

),(

CBDCAD

CABD

• Sostituiamo nella tabella la entry AB alle singole entry A e B e calcoliamo le distanze di AB dalle sequenze rimanenti facendo una semplice media aritmetica:

Seq. Seq. ABAB

Seq. CSeq. C Seq. DSeq. D

Seq. Seq. ABAB

0.000.00

Seq. C Seq. C 0.000.00

Seq. DSeq. D 0.000.00

?

0.57?

0.375

175.02

18.017.02

),(),(

),(

DBDDAD

DABD

0.175

• Iterando il procedimento si ottiene l’albero completo.

ClustalW: Albero ClustalW: Albero filogenetico (3)filogenetico (3)

Otterremo un albero i cui rami hanno Otterremo un albero i cui rami hanno lunghezza proporzionale alla distanza tra le lunghezza proporzionale alla distanza tra le sequenze :sequenze :

Quest’albero verrà utilizzato per guidare Quest’albero verrà utilizzato per guidare l’allineamento progressivo.l’allineamento progressivo.

Nel nostro esempio verranno allineate per Nel nostro esempio verranno allineate per prime le sequenze A e B. Successivamente prime le sequenze A e B. Successivamente verrà allineata la sequenza D all’allineamento verrà allineata la sequenza D all’allineamento AB e infine verrà allineata la sequenza C AB e infine verrà allineata la sequenza C all’allineamento ABD.all’allineamento ABD.

A

B

C

D

Albero Albero filogenetico: filogenetico: un esempioun esempio

L’albero filogenetico L’albero filogenetico in figura è costruito in figura è costruito mediante ClustalW a mediante ClustalW a partire dalle partire dalle sequenze della sequenze della proteina mnSOD su proteina mnSOD su diversi organismi: il diversi organismi: il clustering ottenuto clustering ottenuto rispecchia in manierarispecchia in manieraabbastanza fedele abbastanza fedele quella che è la quella che è la filogenesi classica filogenesi classica (cioè basata su dati(cioè basata su datigeopaleontologici).geopaleontologici).

Allineamento con ClustalWAllineamento con ClustalW

Nell’allineamento di sequenze nucleotidiche è possibile Nell’allineamento di sequenze nucleotidiche è possibile trovare solo simboli * nel caso di identità della colonna al trovare solo simboli * nel caso di identità della colonna al 100%.100%.

La presenza La presenza di un simbolo di un simbolo ** in fondo ad in fondo ad una colonna una colonna indica un indica un match del match del 100%.100%.

Il simbolo Il simbolo : : indica un’alta indica un’alta similarità similarità (>75%).(>75%).

Il simbolo Il simbolo .. indica una indica una media media similarità similarità (50%-75%).(50%-75%).

La presenza La presenza di un simbolo di un simbolo ** in fondo ad in fondo ad una colonna una colonna indica un indica un match del match del 100%.100%.

Il simbolo Il simbolo : : indica un’alta indica un’alta similarità similarità (>75%).(>75%).

Il simbolo Il simbolo .. indica una indica una media media similarità similarità (50%-75%).(50%-75%).

ClustalW: Server on lineClustalW: Server on line Il server ufficiale di ClustalW si trova sul sito Il server ufficiale di ClustalW si trova sul sito

dell’EMBL:dell’EMBL:

http://www.ebi.ac.uk/clustalw/index.htmlhttp://www.ebi.ac.uk/clustalw/index.html

Vi sono comunque molti altri server di Vi sono comunque molti altri server di ClustalW; uno dei più popolari è quello dello ClustalW; uno dei più popolari è quello dello Swiss Institute of Bioinformatics:Swiss Institute of Bioinformatics:

http://www.ch.embnet.org/software/http://www.ch.embnet.org/software/ClustalW.htmlClustalW.html

Questa versione di ClustalW ha un’interfaccia Questa versione di ClustalW ha un’interfaccia semplificata rispetto a quella ufficiale su EMBL.semplificata rispetto a quella ufficiale su EMBL.

ClustalW: uso localeClustalW: uso locale

E’ anche possibile scaricare la versione E’ anche possibile scaricare la versione locale di ClustalW per ambienti Windows locale di ClustalW per ambienti Windows (DOS) e Linux:(DOS) e Linux:

ftp://ftp.ebi.ac.uk/pub/software/dos/clustalw/ftp://ftp.ebi.ac.uk/pub/software/dos/clustalw/ftp://ftp.ebi.ac.uk/pub/software/unix/ftp://ftp.ebi.ac.uk/pub/software/unix/

clustalw/clustalw/ftp://ftp-igbmc.u-strasbg.fr/pub/ClustalW/ftp://ftp-igbmc.u-strasbg.fr/pub/ClustalW/

http://www.biolinux.org/clustalw.htmlhttp://www.biolinux.org/clustalw.html

Blast2SeqBlast2Seq Blast2Seq è un tool della famiglia BLAST che permette Blast2Seq è un tool della famiglia BLAST che permette

di eseguire l’allineamento di una coppia di sequenze di eseguire l’allineamento di una coppia di sequenze utilizzando l’algoritmo di allineamento locale di BLAST.utilizzando l’algoritmo di allineamento locale di BLAST.

E’ importante sottolineare la differenza tra questo tipo E’ importante sottolineare la differenza tra questo tipo di approccio e quello mostrato nelle slides precedenti:di approccio e quello mostrato nelle slides precedenti:

L’allineamento Pairwise Globale di coppie di L’allineamento Pairwise Globale di coppie di sequenze mette in luce l’eventuale similarità sequenze mette in luce l’eventuale similarità globale tra le due sequenze. globale tra le due sequenze.

L’allineamento Pairwise effettuato da Blast2Seq L’allineamento Pairwise effettuato da Blast2Seq mette in luce le eventuali similarità locali tra le due mette in luce le eventuali similarità locali tra le due sequenze. Due sequenze possono anche essere sequenze. Due sequenze possono anche essere molto diverse nella loro interezza ma avere molto diverse nella loro interezza ma avere comunque delle regioni molto simili: a partire da comunque delle regioni molto simili: a partire da tale similarità è spesso possibile formulare tale similarità è spesso possibile formulare interessanti ipotesi sulla presenza di determinati interessanti ipotesi sulla presenza di determinati motivi e quindi sulla funzione delle molecole motivi e quindi sulla funzione delle molecole analizzate.analizzate.

Allineamento Pairwise e Multiplo di Bio-Sequenze

Documents

Transcript of Allineamento Pairwise e Multiplo di Bio-Sequenze