Bioinformatica
Corso di Laurea Specialistica in Informatica
Allineamento Multiplo
di sequenze
01-04/04/2011
Allineamento di sequenze
• Allineamento multiplo: motivazioni e definizioni
• Soluzione esatta: Programmazione Dinamica
• Euristiche per il MSA
–
–
–
–
–
–
–
Center Star Method
Profili
Allineamento Iterativo
Allineamento Progressivo: Feng-Doolittle
ClustalW
Metodi basati su consistenza
T-Coffee
• Funzioni di scoring e Valutazione degli allineamenti
Allineamento Multiplo di Sequenze
(Multiple Sequence Alignment – MSA)
• Motivazioni
– Filogenesi molecolare
Costruzione di alberi filogenetici che illustrino le distanze ed i
rapporti evolutivi tra le molecole analizzate, a partire dai confronti
tra di esse.
– Studio dell’evoluzione dei genomi
– Caratterizzazione di geni e proteine con funzione sconosciuta
Attraverso l’individuazione di motivi ricorrenti e siti funzionalmente
importanti.
– Individuazione di elementi regolatori
Attraverso l’individuazione di pattern comuni a diversi organismi.
MSA: Definizione
• Dato un alfabeto Σ (ad es. Σ={A, C, G, T}) e le sequenze S1,
S2, …, Sk: SiΣ* per 1ik, un allineamento multiplo associa a
S1, S2, … Sk le sequenze S1’, S2’, …, Sk’: Si’(Σ{-})* per
1ik, in modo che:
• |S1’|=|S2’|=…=|Sk’|=l
lunghezza)
(le sequenze abbiano tutte la stessa
• Rimuovendo gli spazi “-” da S1’, S2’, … Sk’ si ottengano
nuovamente S1, S2, … Sk.
MSA: un esempio
1pamA
cdgt_bacli
amy_thetu
cdg2_bacma
cdg1_bacma
cdgt_bacst
cdgt_bacs2
amym_bacst
cdgt_klepn
amyb_bacpo
amy1_schpo
2aaa
amya_aspor
amy1_schoc
amy1_sacfi
ydd2_schpo
amy_bacci
1jdc
TDVIYQIFTD
TDVIYQVFTD
TDVIYQIVTD
TDTVYQIVTD
TDVIYQIVTD
SDVVYQIVVD
KDVIYQIVTD
GDVIYQIIID
KETIYFLFLD
KQSIYFIMTD
RRSIYQIITD
TQSIYFLLTD
SQSIYFLLTD
DQSIYQIVTD
SQSIYQIVTD
KQVIYQVLTD
TDVIYQIVTD
GD---EIILQ
RFSDGNPANN
RFLDGNPSNN
RFVDGNTSNN
RFVDGNSANN
RFADGDRTNN
RFVDGNTSNN
RFSDGNPGNN
RFYDGDTTNN
RFSDGDPSNN
RFSNGDPSND
RFSLEEGATE
RFGRTDNSTT
RFARTDGSTT
RFARSDGSTT
RFARTDGDTS
RFALDEDN-RFVDGNTANN
GFHWNVVREA
P---TGAAFD
P---TGAAFD
P---TGDLYD
P---TGAAFS
P---AGDAFS
P---SGALFS
P---SGAIFS
NPAKSYGLYD
A---GFNSAT
N---YGG-FN
---------R
------------------A
------------------A
---------P---AGSAYD
P---------
GSC-TNLRLY
GTC-SNLKLY
PTH-TSLKKY
SDH-SNLKLY
GDR-SNLKLY
SGC-TNLRKY
QNC-IDLHKY
PTK-SKWKMY
YDP-NNLKKY
SN-NSDQRKW
IPCDPVRFMY
ATCNTGNEIY
TC-NTADQKY
ADCLVSDRKY
SC-NTEDRLY
FYAKASGNLY
ATCSTNLKLY
----------
CGGDWQGIIN
CGGDWQGLVN
FGGDWQGIIN
FGGDWQGITN
FGGDWQGIID
CGGDWQGIIN
CGGDWQGIID
WGGDLEGVRQ
TGGDLRGLIN
HGGDFQGIIN
CGGTWNGIRN
CGGSWQGIID
CGGTWQGIID
CGGSYKGIID
CGGSFQGIIK
LGGTWKGITR
CGGDWQGIMN
--NDWYNILR
Sum-Of-Pairs Score
• Come nel caso Pairwise, l’allineamento multiplo di
sequenze consiste nel massimizzare una funzione di
scoring.
• La funzione più utilizzata è il Sum-Of-Pairs Score che è la
somma degli score degli allineamenti pairwise indotti
dall’allineamento multiplo:
 (m)   S (mk , ml )
k l
• dove S(mk,ml) è lo score dell’allineamento della coppia di
sequenze mk ed ml indotto dall’allineamento multiplo m.
• Come visto nel caso Pairwise i concetti di Score e
Distanza sono equivalenti, per cui è possibile definire la
distanza Sum-Of-Pairs.
Sum-Of-Pairs Score: un esempio
A A C T G – T - - A G
A A C – G – T A T A C
A A C T – A T A - - G
 (m)   S (mk , ml )
k l
• Se scegliamo di utilizzare una metrica di tipo crisp
che assegna 1 ad ogni match e 0 ad ogni mismatch
si ha:
 (m)  S (m1 , m2 )  S (m1 , m3 )  S (m2 , m3 )  6  6  5  17
Allineamento di sequenze
• Allineamento multiplo: motivazioni e definizioni
• Soluzione esatta: Programmazione Dinamica
• Euristiche per il MSA
–
–
–
–
–
–
–
–
Center Star Method
Profili
Allineamento Iterativo
Allineamento Progressivo: Feng-Doolittle
ClustalW
Metodi basati su consistenza
T-Coffee
MSA by HMM: Probcons
• Funzioni di scoring e Valutazione degli allineamenti
Soluzione esatta:
Programmazione Dinamica
• L’allineamento multiplo ottimale di k sequenze viene
calcolato usando un ipercubo a k dimensioni D, definendo
D(j1, j2, …, jk) come il miglior score dell’allineamento dei
prefissi di lunghezza j1, j2, …, jk delle sequenze x1, x2, …,
xk, rispettivamente.
V (i, j )  max( V (i  1, j  1)   ( S[i ], T [ j ]),
• Si ha:
D0,0,...,0  0
V (i  1, j )   ( S[i ], ),
V (i, j  1)   (, T [ j ]) )
D( j1, j 2,..., jk )  max  0,1k ,  0 {D( j1   1 , j2   2 ,..., jk   k ) 
  ( 1 x j1 ,... k x jk )}
• dove  è la scoring function ed   1 ,  2 ,...,  n   0,1
è un vettore che indica la direzione del processo di
allineamento nell’ipercubo.
n
Programmazione Dinamica: Ipercubo
• Date le sequenze S1=VSNS, S2=SNA ed S3=AS si ottiene il
seguente ipercubo a 3 dimensioni:
• L’algoritmo ha complessità spaziale e temporale O(nk), dove
n è la lunghezza delle sequenze e k il numero di sequenze. Il
problema del calcolo del MSA esatto è NP-Completo.
Allineamento di sequenze
• Allineamento multiplo: motivazioni e definizioni
• Soluzione esatta: Programmazione Dinamica
• Euristiche per il MSA
–
–
–
–
–
–
–
Center Star Method
Profili
Allineamento Iterativo
Allineamento Progressivo: Feng-Doolittle
ClustalW
Metodi basati su consistenza
T-Coffee
• Funzioni di scoring e Valutazione degli allineamenti
Center Star Method
• Il metodo Center-Star di Gusfield è un algoritmo
approssimato per il calcolo del MSA secondo il SumOf-Pairs Score (SP).
• Dato in input un insieme di sequenze S = {S1, S2, …
Sk}, vogliamo trovare l’allineamento multiplo M che
minimizzi la distanza SP (o che massimizzi lo score
SP).
Center Star Method: Definizioni
• Dato un insieme S di k sequenze, si definisce
sequenza centrale Sc  S, la sequenza che minimizza
la funzione:
 D( S , S )
S j S
c
j
• Cioè la somma delle distanze di tutte le sequenze da
Sc sia la minima possibile.
Center Star Method: Definizioni
•
Si definisce Center-Star un albero con k nodi, in cui Sc è
il nodo centrale e in cui i restanti k-1 nodi sono
etichettati da stringhe distinte in S \ {Sc}
•
Il MSA Mc dell’insieme di sequenze S è l’allineamento
multiplo consistente con tale albero.
Center Star Method: Algoritmo
• Trova la sequenza St  S che minimizza
M  St 
 D( S , S )
i t
i
t
e sia
• Aggiungi le sequenze in S\{St} ad M una ad una, secondo
la maggiore vicinanza a St, allineando ogni nuova
sequenza ad St ed aggiungendo eventuali nuovi gap alle
sequenze già allineate.
• Complessità: O(k2n2), dove k è il numero di sequenze e n
la massima lunghezza.
• La distanza SP dell’allineamento prodotto è minore del
doppio della distanza SP ottimale.
Allineamento di sequenze
• Allineamento multiplo: motivazioni e definizioni
• Soluzione esatta: Programmazione Dinamica
• Euristiche per il MSA
–
–
–
–
–
–
–
Center Star Method
Profili
Allineamento Iterativo
Allineamento Progressivo: Feng-Doolittle
ClustalW
Metodi basati su consistenza
T-Coffee
• Funzioni di scoring e Valutazione degli allineamenti
I Profili
• I profili sono strutture utili per riassumere le
proprietà comuni di gruppi di sequenze e sono alla
base di molti metodi di allineamento multiplo di
sequenze.
• Sia M un allineamento multiplo di sequenze di
lunghezza l.
• Il Profilo di M è una matrice l     dove Σ è
l’alfabeto delle sequenze di M, le cui colonne
indicano la frequenza di ciascun simbolo nella
corrispondente colonna dell’allineamento.
Profili: un esempio
A
A C A - - G – T C A
A C - - T G C T – A
- C A A T G C T G A
C
G
T
-
1
2/3 0
0
0
1/3
2
0
3/3 0
0
0
3
2/3 0
0
0
1/3
4
1/3 0
0
0
2/3
5
0
0
0
2/3 1/3
6
0
0
3/3 0
7
0
2/3 0
0
8
0
0
3/3 0
9
0
1/3 1/3 0
10
3/3 0
0
0
0
0
1/3
1/3
0
Allineamento di una sequenza ad un
profilo
• Per allineare una sequenza ad un profilo si utilizza
l’algoritmo di Needleman-Wunsch con un’opportuna
funzione di scoring.
• Sia p(i,j) un profilo, con i=1…l e j=1…|Σ|+1 e sia
S = {S1, S2, …, Sn}.
• Possiamo definire la seguente Scoring Function:
 sp :    1,2,..., l  
 sp (b, i )   pi ,a (a, b)
a
Allineamento di due profili
• Siano P1  ( pij ) e P2  ( pij'' )
profili.
'
con i=1…l e j=1…|Σ|+1 due
• In questo caso utilizziamo la seguente funzione di
scoring:
 pp : 1,2,..., l 1,2,..., l  
 1
 pp (i, j )   f  pi' ,k , p 'j' ,k 
k 1
• dove f è una funzione che assegna uno score a coppie di
colonne tenendo conto della frequenza dei singoli simboli
dell’alfabeto.
Allineamento di sequenze
• Allineamento multiplo: motivazioni e definizioni
• Soluzione esatta: Programmazione Dinamica
• Euristiche per il MSA
–
–
–
–
–
–
–
Center Star Method
Profili
Allineamento Iterativo
Allineamento Progressivo: Feng-Doolittle
ClustalW
Metodi basati su consistenza
T-Coffee
• Funzioni di scoring e Valutazione degli allineamenti
Allineamento iterativo
• Questo approccio usa gli score pairwise per
aggiungere sequenze ad un allineamento multiplo.
• Si comincia allineando la coppia di sequenze più
vicine secondo una certa nozione di distanza.
• Quindi, ad ogni passo, si prende la sequenza che ha
la distanza minima da tutte quelle già allineate e la
si allinea al profilo dell’allineamento già prodotto.
Eventuali nuovi spazi “-” sono aggiunti alle sequenze
già allineate.
Allineamento di sequenze
• Allineamento multiplo: motivazioni e definizioni
• Soluzione esatta: Programmazione Dinamica
• Euristiche per il MSA
–
–
–
–
–
–
–
Center Star Method
Profili
Allineamento Iterativo
Allineamento Progressivo: Feng-Doolittle
ClustalW
Metodi basati su consistenza
T-Coffee
• Funzioni di scoring e Valutazione degli allineamenti
Allineamento Progressivo
• L’idea
chiave
di
questo
algoritmo
è
che
l’informazione biologica più affidabile ottenibile da
un insieme di sequenze da allineare scaturisce
dall’allineamento della coppia di sequenze più vicine.
• Quindi ogni gap “-” che compare in questo
allineamento
deve
essere
preservato
nella
costruzione dell’allineamento multiplo, a differenza
di quanto accade nell’allineamento iterativo.
• Numerosi tools di MSA si basano su
approccio, tra i quali ClustalW e T-Coffee.
questo
Allineamento Progressivo:
L’algoritmo di Feng-Doolittle
k 
 
 2
• Calcola i
allineamenti pairwise e converti i loro
score in distanze.
• Costruisci un albero filogenetico.
• Allinea le sequenze nell’ordine suggerito dall’albero
iniziando dalla coppia di sequenze più vicine, e
utilizzando l’allineamento per profili per aggiungere
una sequenza all’allineamento già prodotto o per
allineare due allineamenti.
Allineamento di sequenze
• Allineamento multiplo: motivazioni e definizioni
• Soluzione esatta: Programmazione Dinamica
• Euristiche per il MSA
–
–
–
–
–
–
–
Center Star Method
Profili
Allineamento Iterativo
Allineamento Progressivo: Feng-Doolittle
ClustalW
Metodi basati su consistenza
T-Coffee
• Funzioni di scoring e Valutazione degli allineamenti
ClustalW
• ClustalW è il tool più popolare per l’allineamento
multiplo di biosequenze.
• Utilizza
l’approccio
progressivo
e
si
basa
sull’algoritmo di Feng-Doolittle.
• Dato un insieme S di n sequenze da allineare,
ClustalW allinea tutte le coppie di sequenze di S
separatamente e costruisce una matrice con le
distanze tra ogni coppia di sequenze.
Seq. A
Seq. B
Seq. C
Seq. A
0.00
Seq. B
0.11
0.00
Seq. C
0.32
0.43
0.00
Seq. D
0.17
0.18
0.57
Seq. D
0.00
ClustalW
• Viene quindi costruito un albero guida filogenetico
utilizzando il metodo neighbour-joining.
• Si sceglie la coppia più vicina: questa andrà a
formare il primo sottoalbero:
Seq. A
Seq. B
Seq. C
Seq. A
0.00
Seq. B
0.11
0.00
Seq. C
0.32
0.43
0.00
Seq. D
0.17
0.18
0.57
Seq. D
0.00
AB
A
B
ClustalW
• 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. AB Seq. C
Seq. AB
0.00
Seq. C
0.375
?
0.00
Seq. D
?
0.175
0.57
D( AB, D) 
D( A, D)  D( B, D)

2
0.17  0.18
 0.175
2
Seq. D
0.00
D( AB, C ) 
D( A, C )  D( B, C )

2
0.32  0.43
 0.375
2
• Iterando il procedimento
si ottiene l’albero completo.
ClustalW: Albero Filogenetico
• Otterremo un albero i cui rami hanno lunghezza
proporzionale alla distanza tra le sequenze :
A
B
D
C
• Quest’albero
verrà
utilizzato
per
guidare
l’allineamento progressivo.
• Nel nostro esempio verranno allineate per prime le
sequenze A e B. Successivamente verrà allineata la
sequenza D all’allineamento AB e infine verrà
allineata la sequenza C all’allineamento ABD.
Albero filogenetico: un esempio
• L’albero filogenetico in
figura è costruito
mediante ClustalW a
partire dalle sequenze
della proteina mnSOD su
diversi organismi: il
clustering ottenuto
rispecchia in maniera
abbastanza fedele quella
che è la filogenesi classica
(cioè basata su dati
geopaleontologici).
Allineamento con ClustalW
• Questo è un particolare dell’output di ClustalW.
•
•
•
La presenza di un
simbolo * in
fondo ad una
colonna indica un
match del 100%.
Il simbolo : indica
un’alta similarità
(>75%).
Il simbolo . indica
una media
similarità (50%75%).
• Nell’allineamento di sequenze nucleotidiche è possibile
trovare solo simboli * nel caso di identità della colonna al
100%.
ClustalW: Server On Line
• Il server ufficiale di ClustalW si trova sul sito
dell’EMBL:
http://www.ebi.ac.uk/clustalw/index.html
• Vi sono comunque molti altri server di ClustalW; uno
dei più popolari è quello dello Swiss Institute of
Bioinformatics:
http://www.ch.embnet.org/software/ClustalW.html
• Questa versione di ClustalW ha un’interfaccia
semplificata rispetto a quella ufficiale su EMBL.
Allineamento di sequenze
• Allineamento multiplo: motivazioni e definizioni
• Soluzione esatta: Programmazione Dinamica
• Euristiche per il MSA
–
–
–
–
–
–
–
Center Star Method
Profili
Allineamento Iterativo
Allineamento Progressivo: Feng-Doolittle
ClustalW
Metodi basati su consistenza
T-Coffee
• Funzioni di scoring e Valutazione degli allineamenti
Metodi basati su consistenza
• Il primo algoritmo di MSA consistency-based è stato
introdotto da Kececioglu nel 1993.
• Dato un insieme di sequenze S, l’allineamento
“ottimale” deve essere il più consistente possibile
con gli allineamenti pairwise ottimali delle sequenze
in S.
• Il calcolo di tale allineamento è un problema NPCompleto che può quindi essere risolto in modo
esatto solo per un piccolo numero di sequenze.
Vantaggi della consistenza
•Funzioni-obiettivo consistenti non dipendono da
specifiche matrici di sostituzione ma dai metodi per
l’allineamento pairwise.
•Gli schemi basati su consistenza dipendono dalle
posizioni dei residui negli allineamenti pairwise; ciò
significa che lo score associato all’allineamento di due
residui dipende dalla loro posizione nelle sequenze
piuttosto che dalla loro natura chimico-fisica.
Consistency-based tool
• Uno dei primi tools euristici basati su consistenza è
SAGA (1996).
• In SAGA viene utilizzata la funzione-obiettivo
COFFEE (Consistency-based Objective Function For
alignmEnt Evaluation), che riflette il livello di
consistenza tra un allineamento multiplo di sequenze
ed una libreria di allineamenti pairwise delle stesse
sequenze.
• Il COFFEE-Score viene ottimizzato utilizzando un
algoritmo genetico.
• Sebbene SAGA sia in grado di fornire risultati
interessanti, l’approccio basato su algoritmi genetici
si rivela troppo lento.
Allineamento di sequenze
• Allineamento multiplo: motivazioni e definizioni
• Soluzione esatta: Programmazione Dinamica
• Euristiche per il MSA
–
–
–
–
–
–
–
–
Center Star Method
Profili
Allineamento Iterativo
Allineamento Progressivo: Feng-Doolittle
ClustalW
Metodi basati su consistenza
T-Coffee
MSA by HMM: Probcons
• Funzioni di scoring e Valutazione degli allineamenti
T-Coffee
• T-Coffee (Tree-based COFFEE) è un’euristica per il
MSA basata sulla funzione-obiettivo COFFEE.
• L’allineamento multiplo viene calcolato a partire da
una collezione di allineamenti pairwise locali e
globali delle sequenze in input attraverso l’approccio
progressivo guidato da un albero filogenetico creato
con il metodo neighbor-joining (come in ClustalW).
• Grazie all’utilizzo degli allineamenti pairwise locali e
globali e della funzione-obiettivo consistente, TCoffee
raggiunge
una
notevole
precisione
nell’allineamento multiplo di sequenze a bassa
similarità.
L’algoritmo di T-Coffee
A
B
A
C
B
C
A
B
A
C
B
C
Libreria primaria by
ClustalW
A
B
B
C
Libreria primaria by
LAlign
Weighting
LIBRERIA
PRIMARIA
ESTENSIONE
LIBRERIA
ESTESA
Allineamento
Progressivo
A
B
C
L’algoritmo di T-Coffee
A
B
A
C
B
C
A
B
A
C
B
C
Libreria primaria by
ClustalW
A
B
B
C
Libreria primaria by
LAlign
Weighting
LIBRERIA
PRIMARIA
ESTENSIONE
LIBRERIA
ESTESA
Allineamento
Progressivo
A
B
C
Libreria primaria di allineamenti pairwise
globali
• Tutte le coppie di sequenze in input vengono allineate
mediante ClustalW.
• Per ogni allineamento pairwise viene calcolata l’identità
percentuale:
I % ( S1 , S 2 ) 
sim ( S1 , S 2 ) 100
pos
• Dove sim(S1,S2) è il numero dei match nell’allineamento e
pos il numero delle coppie allineate di residui escluse quelle
in cui compare un gap.
S1) A C A - G – T C A
S2) A G - T G C T – T
I % ( S1 , S 2 ) 
3 100
 60
5
Libreria
• Nella
libreria
ogni
allineamento
pairwise
è
rappresentato come una lista di coppie di residui
pesati (constraint list).
• Inizialmente ogni coppia di residui riceve un peso
equivalente alla sequence identity dell’allineamento
da cui proviene:
S1) A C A - G – T C A
S2) A G - T G C T – T
Seq1
S1
S1
S1
S1
S1
Seq2
S2
S2
S2
S2
S2
Res1
1
2
4
5
7
Res2
1
2
4
6
7
Weight
60
60
60
60
60
Libreria primaria di allineamenti pairwise
locali
• Viene creata una seconda libreria a partire dagli allineamenti
locali creati con LAlign, un tool del pacchetto FASTA.
• L’allineamento locale di una coppia di sequenze S1, S2 consiste
nell’allineamento di sottosequenze di S1 ed S2, al fine di mettere
in evidenza eventuali regioni ad alta similarità:
S1
S2
• LAlign restituisce i 10 migliori allineamenti locali (in termini di
similarità) della coppia di sequenze in input.
• Una volta individuato l’allineamento locale con il massimo
score, LAlign cerca il successivo escludendo dalla ricerca le due
regioni appena trovate: in questo modo gli allineamenti prodotti
non si intersecheranno.
Libreria primaria
• A partire dalle due librerie globale e locale viene creata un’unica
libreria primaria mediante una semplice operazione di addizione.
• Le coppie di residui comuni vengono sostituite da un’unica entry il cui
peso è la somma dei due pesi, mentre tutte le altre coppie vengono
trascritte così come sono:
Seq1
S1
S1
S1
S1
S1
Global Alignments by ClustalW
Seq2
Res1
Res2
S2
1
1
S2
2
2
S2
3
3
S2
5
6
S2
7
7
Seq1
S1
S1
S1
S1
S1
S1
S1
Seq2
S2
S2
S2
S2
S2
S2
S2
Weight
60
60
60
60
60
Seq1
S1
S1
S1
S1
S1
Primary Library
Res1
Res2
1
1
2
2
3
3
5
6
7
7
15
22
16
23
Local Alignments by LAlign
Seq2
Res1
Res2
S2
1
1
S2
2
2
S2
3
3
S2
15
22
S2
16
23
Weight
90
90
90
60
60
10
10
Weight
30
30
30
10
10
L’algoritmo di T-Coffee
A
B
A
C
B
C
A
B
A
C
B
C
Libreria primaria by
ClustalW
A
B
B
C
Libreria primaria by
LAlign
Weighting
LIBRERIA
PRIMARIA
ESTENSIONE
LIBRERIA
ESTESA
Allineamento
Progressivo
A
B
C
Estensione della libreria primaria
• L’idea chiave dell’estensione è di combinare le
informazioni nella libreria così che il peso finale
associato ad ogni coppia rifletta anche le
informazioni contenute nel resto della libreria.
• Questo viene realizzato prendendo tutte le
coppie di residui nella libreria e confrontando il
loro allineamento con i residui provenienti dalle
altre sequenze.
Estensione della libreria primaria
• Consideriamo, ad esempio, quattro sequenze A, B, C, D.
• Siano A(1) il primo di residuo di A e B(1) il primo residuo di B e
sia W(A(1),B(1))=60 il peso associato a tale coppia nella
libreria primaria:
A) A C A - G – T C A
B) A G - T G C T – T
• Consideriamo adesso l’allineamento delle sequenze A e B
attraverso la sequenza C:
• Vediamo che A(1) e C(1) sono allineati così come C(1) e B(1).
Concludiamo dunque che c’è un allineamento di A(1) e B(1)
attraverso la sequenza C.
A) A C A - G – T C A
C) A G - T G C A C A
B) A G - T G C T – T
Estensione della libreria primaria
A) A C A - G – T C A
C) A G – T G C A C A
B) A G - T G C T – T
• Associamo alla coppia A(1), B(1) il peso minimo tra
W(A(1),C(1))=66 e W(C(1),B(1))=71  W(A(1),B(1))=66.
• Questo peso viene sommato al valore già contenuto nella
libreria W(A(1),B(1))=60. Si ha quindi W(A(1),B(1))=126.
• L’estensione completa richiede l’analisi di tutte le restanti
triplette e chiaramente non tutte porteranno informazioni.
• Ad es. l’allineamento di A e B attraverso D non contiene
informazioni circa la coppia A(4), B(4) e quindi non influisce sul
peso di tale coppia:
A) A C A - G – T C A
D) A G A T – C – C T
B) A G - T G C T – T
Estensione della libreria primaria
• Riassumendo, il peso associato ad ogni coppia di
residui nella libreria sarà pari alla somma dei pesi
ottenuti dall’analisi delle triplette.
• Quante più sequenze intermedie supportano
l’allineamento di una certa coppia di residui, tanto
più alto sarà il peso di tale coppia nella libreria.
• L’operazione di estensione viene eseguita per tutte
le coppie di residui di tutte le coppie di sequenze in
input contenute nella libreria primaria.
L’algoritmo di T-Coffee
A
B
A
C
B
C
A
B
A
C
B
C
Libreria primaria by
ClustalW
A
B
B
C
Libreria primaria by
LAlign
Weighting
LIBRERIA
PRIMARIA
ESTENSIONE
LIBRERIA
ESTESA
Allineamento
Progressivo
A
B
C
Allineamento progressivo in T-Coffee
• Una volta costruita la libreria, vengono allineate tutte le
coppie e gli score di similarità vengono convertiti in
distanze come in ClustalW.
• E come in ClustalW viene costruito un albero guida con il
metodo neighbor-joining.
• Le sequenze vengono allineate nell’ordine suggerito
dall’albero ma vengono utilizzati i pesi contenuti nella
libreria estesa anziché gli score delle matrici di
sostituzione.
• Questo rende l’allineamento più preciso dato che vengono
utilizzate informazioni precise sui residui delle sequenze
in esame e su come questi vengono allineati tra loro,
piuttosto che informazioni generiche sulla natura degli
aminoacidi come quelle contenute nelle matrici.
Allineamento di sequenze
• Allineamento multiplo: motivazioni e definizioni
• Soluzione esatta: Programmazione Dinamica
• Euristiche per il MSA
–
–
–
–
–
–
–
–
Center Star Method
Profili
Allineamento Iterativo
Allineamento Progressivo: Feng-Doolittle
ClustalW
Metodi basati su consistenza
T-Coffee
MSA by HMM: Probcons
• Funzioni di scoring e Valutazione degli allineamenti
Funzioni di scoring e
Valutazione degli allineamenti
• Esistono numerose funzioni di scoring oltre al SumOf-Pairs, utilizzate dai tools di MSA come funzioni
obiettivo da massimizzare e per valutare gli
allineamenti prodotti. Ne consideriamo due:
– Entropia
– Circular-Sum
• La scelta della scoring function “giusta” è
fondamentale nella progettazione di un buon
algoritmo di allineamento.
• Sfortunatamente non esistono ancora funzioni
universali in grado di catturare pienamente il
significato biologico del confronto tra residui.
Entropia
• Entropia E ( A)   E (C )
CA


• dove C sono le colonne dell’allineamento: E (C )    p X log p X 
X 

• e pX è la frequenza del simbolo X nella colonna C. 
A A C T G – T - - A G
A A C – G – T A T A C
A A C T – A T A - - T


3
3


E (1)  
p
log
p
 0  0  0  0  0

X
X    p A log p A  pC log pC  pG log pG  pT log pT  p log p     log
3
3

 X ( A,C ,G ,T , )

1 1
1 1
1 
 1
E (11)   0  log  log  log  0   0  0,15  0,15  0,15  0  0,45
3
3 3
3 3
3 

E ( A)  0  0  0  0,11  0,11  0,16  0  0,11  0,16  0,11  0,45  1,21
• Una colonna altamente conservata ha una bassa variabilità e
un alto contenuto informativo. Tanto più è “buono”
l’allineamento tanto più bassa sarà l’entropia.
Circular Sum
1 n
• Circular-Sum: CS ( A)   MPA(aCi , aCi1 )
2 i 1
• dove MPA(ai , a j )   S ai [m], a j [m] e Cn1  c1
è lo score del
m 1
pairwise-alignment indotto dal MSA.
k
A A C T G – T - - A G
A A C – G – T A T A C
A A C T – A T A - - T
11
MPA(a1 , a2 )   S (a1[m]  a2 [m])  1  1  1  0  1  0  1  0  0  1  0  6
m 1
11
MPA(a2 , a3 )   S (a2 [m]  a3[m])  1  1  1  0  0  0  1  1  0  0  0  5
m 1
11
MPA(a3 , a1 )   S (a3[m]  a1[m])  1  1  1  1  0  0  1  0  0  0  0  5
m 1
CS ( A)  6  5  5  16