ALLINEAMENTI MULTIPLI
•Identificazione di siti funzionalmente
importanti
•Dimostrazione di omologia
•Filogenesi molecolare
•Ricerca di somiglianze deboli ma significative
in banche dati
•Predizione di struttura
•Predizione di funzione
Utilizzo dei colori
I file raw-text possono essere utilizzati per visualizzare le colonne,
ma è possibile associare colori diversi per residui con caratteristiche
chimico fisiche diverse. Questo facilita molto la visualizzazione dei
multiallineamenti
ESPript e PrettyPlot sono programmi dedicati a questo tipo di analisi
qualitativa disponibili in rete
ESTENSIONE DEGLI ALLINEAMENTI
GLOBALI (NW) O LOCALI (SW) ?
•L’applicazione degli algoritmi per la ricerca di
un allineamento ottimale tra due sequenze
pone problemi per l’applicazione a più di tre
sequenze contemporaneamente se L è la
lunghezza delle sequenze occorrerebbe un
tempo di O(LN) che è impraticabile
•Uso di metodi approssimati (euristici) o
progressivi che si basano sull’ipotesi che le
sequenze da allineare siano filogeneticamente
correlate
Metodi approssimati
•Allineamento progressivo (Clustal)
•Metodi iterativi (Multalin)
•Metodi basati su zone comuni di sequenza
conservate (Profili)
•Metodi statistici e modelli probabilistici (HMM)
Allineamento progressivo
• CLUSTAL (Higgins & Sharp, 1988)
– ClustalW
– ClustalX
• PILEUP (GCG)
CLUSTAL
(Higgins & Sharp, 1988)
1. Allineamento a coppie di tutte le
sequenze iniziali con:
1. Metodi approssimati (n-ple) oppure
2. algoritmo dinamico di Myers & Miller, 1988
2. Il punteggio degli allineamenti (matrice
delle distanze) è utilizzato per costruire
un albero filogenetico (neighbor-joining)
3. Allineamento delle sequenze secondo
l’ordine dell’albero (le sequenze più simili
prima)
neighbor-joining
Saitou Mol. Biol. Evol. 1986
È un algoritmo di clustering che
attraverso iterazioni successive
determina le coppie di sequenze più simili
e le restanti. Se N sono le sequenze
allora ci saranno
N(N-1)/2
Possibilità di scegliere la prima coppia di
sequenze che tra loro hanno il punteggio
di similarità più alto. La prima coppia così
costituita verrà utilizzata come consenso
e la procedura si ripete per trovare
un’altra sequenza o cluster che sia il più
vicino possibile alla coppia appena
costituita. Parlando in termini filogenetici
in cui NJ viene usato si può dire che
l’albero filogenetico si risolve
progressivamente dalla tipologia a stella
fino a che non si ottengono tutti gli N-3
rami interni.
In questo caso si ha che il nuovo nodo X, dato dall’unione di (1-2), avrà una
distanza dagli altri pari a: (m appartiene ai nodi {3,8})
Dxm
1
D1,m
2
D2,m
D1, 2
The raw data of the tree are represented by the following distance matrix:
B
B
C
A
5
4
C
D
D
7
10 7
E
6
9
6
5
F
8
11 8
9
E
7
8
We have in total 6 OTUs (N=6).
Step 1: We calculate the net divergence r (i) for each OTU from all other OTUs
r(A) = 5+4+7+6+8=30
r(B) = 42
r(C) = 32
r(D) = 38
r(E) = 34
r(F) = 44
Step 2: Now we calculate a new distance matrix using for each pair of OUTs the
formula:
M(ij)=d(ij) - [r(i) + r(j)]/(N-2) or in the case of the pair A,B:
M(AB)=d(AB) -[(r(A) + r(B)]/(N-2) = -13
B
A
-13
C
-11.5 -11.5
D
-10
-10
-10.5
E
-10
-10
-10.5 -13
F
-10.5 -10.5 -11
Now we start with a star tree:
B
C
D
E
-11.5 -11.5
A
|
B
\ | /
\ | /
\|/
/|\
/ | \
/ | \
E
|
C
D
F
Step 3: Now we choose as neighbors those two OTUs for which Mij is the smallest. These are A and B and D and
E. Let's take A and B as neighbors and we form a new node called U. Now we calculate the branch length from
the internal node U to the external OTUs A and B.
S(AU) =d(AB) / 2 + [r(A)-r(B)] / 2(N-2) = 1
S(BU) =d(AB) -S(AU) = 4
Step 4: Now we define new distances from U to each other terminal node:
d(CU) = d(AC) + d(BC) - d(AB) / 2 = 3
d(DU) = d(AD) + d(BD) - d(AB) / 2 = 6
d(EU) = d(AE) + d(BE) - d(AB) / 2 = 5
d(FU) = d(AF) + d(BF) - d(AB) / 2 = 7
and we create a new matrix:
U
C 3
D 6
E 5
F 7
C D E
7
6
8
5
9
8
The resulting tree will be the following:
C
|
\ |
\ |
A
\|____U/ 1
/|
\
/ |
\
/ |
\ 4
E
|
\
F
B
D
N= N-1 = 5
The entire prodcedure is repeated starting at step 1
1
2
3
4
5
CLUSTAL
•
•
•
•
Il contributo delle sequenze al punteggio dell’allineamento multiplo è pesato
Sistema di penalizzazione degli indels che sono favoriti tra domini
conservati.
Durante il processo di allineamento, la penalizzazione dei gap viene
abbassata nelle zone in cui sono già presenti dei gap
Si basa sul NJ che utilizza i valori di similarità dei k(k-1)/2 allineamenti a
coppie (basato sull’idea dell’algoritmo di Feng-Doolittle). Nella costruzione
dell’allineamento fa un allineamento sequenza -> profilo
Sequence weighting: ogni sequenza ha un peso associato, funzione della distribuzione
statistica delle sequenze.
• Gruppi di sequenze correlate hanno pesi diminuiti perchè contengono informazione
ridondante.
Matrix score: a seconda della distanza fra le sequenze sono usate diverse matrici di
sostituzione.
Special gap score: i punteggi associati ai gap variano in relazione a molti fattori, tra cui
la frequenza dei residui allineati con il gap e la lunghezza delle sequenze.
QUALITA’ DI UN ALLINEAMENTO MULTIPLO
N
N
i 1
WSPscore
WijQUAL( Aij )
i 2 j 1
•
CAGPHJKLCMMWERQASDF
•
CAHPHJKLCVMWERQASDF
•
CAGPHJELCVMWERRASDF
•
MAGPHJKLCVMWERFASDF
Si ottiene sommando i punteggi di similarità QUAL(A)
pesati per un peso W di ciascuna delle possibili
coppie allineate nell’allineamento multiplo (Weight
Sum of Pairs)
Dipende dai parametri scelti per calcolare match e
INDELS
Il peso W serve per “pesare” sequenze sovra o sotto
rappresentate nell’allineamento
Svantaggi dei metodi
progressivi
• Non c’è garanzia di trovare la soluzione ottimale
• Gli errori iniziali sono propagati nei passaggi successivi. Se si
introduce un errore nell’allineamento iniziale non si può più
correggere ma anzi si “fissa”
• Gli errori nell’allineamento dipendono dalla somiglianza delle
sequenze ovvero bisogna stare attenti alle sequenze in input
che siano realmente omologhe e di lunghezza paragonabile
tra loro per evitare inserzioni di troppi gap
• Gli alberi filogenetici iniziali derivano da matrici di distanza tra
coppie di sequenze allineate separatamente che sono meno
affidabili di alberi derivati da allineamenti multipli completi
• Quando le sequenze sono molto divergenti (25-30% di
identità) i metodi progressivi sono poco affidabili
Metodi iterativi
• I metodi iterativi tentano di correggere
errori iniziali riallineando iterativamente
sottogruppi di sequenze che poi vengono
riuniti in un allineamento multiplo
– MULTALIN (Corpet, 1988)
– PRRP (Gotoh, 1996)
Metodi iterativi
Negli algoritmi precedenti, una volta che un allineamento è fissato, non viene più
modificato nei passi successivi.
In particolare, la posizione dei gap non cambia (once a gap, always a gap).
In un metodo iterativo, una volta generato un allineamento iniziale, una sequenza o
un insieme di sequenze è rimosso dall’allineamento e riallineato al profilo relativo
alle rimanenti sequenze.
Si può dimostrare che, iterando su tutte le sequenze, si converge ad un massimo
locale.
Metodo di Barton-Sternberg
Trova le due sequenze con il massimo grado di somiglianza e allineale con un
algoritmo standard per il pairwise alignment.
Trova la sequenza più simile al profilo del precedente allineamento e allineala a tale
profilo. Ripeti finchè non sono state incluse tutte le sequenze.
Rimuovi la prima sequenza e riallineala al profilo delle rimanenti. Ripeti per ogni
sequenza.
Ripeti il passo precedente finchè il punteggio non converge oppure fino a quando si
raggiunge un numero massimo di iterazioni.
Punti fondamentali su allineamenti progressivi e iterativi
1) progressivi:
Idea: costruire l’allineamento multiplo aggiungendo una sequenza alla volta.
Metodo euristico: non garantisce l’ottimalità.
Occorre stabilire:
• in quale ordine aggiungere le sequenze;
• come costruire la progressione;
• come allineare una sequenza ad un allineamento.
La progressione può essere lineare
• aggiungi la sequenza all’unico allineamento;
A
B
C
D
E
oppure ad albero
• costruisci più sottoallineamenti e allineali in qualche modo tra loro
Alberi guida le cui foglie sono sequenze e i cui nodi interni rappresentano gruppi (cluster ) di sequenze.
Usati per determinare l’ordine in cui effettuare l’allineamento progressivo k(k-1)/2 confronti.
• definisci una distanza fra cluster. Ripeti i due passi seguenti fino ad ottenere un unico cluster:
• scegli i due cluster con distanza minima e fondili in un unico cluster;
• aggiorna le distanze calcolando la distanza tra il nuovo cluster e i rimanenti.
Il procedimento genera un albero con radice.
problema fondamentale è la propagazione dell’errore che si può risolvere con i metodi iterativi
2) iterativi
riallineano iterativamente sottogruppi di sequenze che poi vengono riuniti in un allineamento multiplo
T-COFFEE (Notredame, JMB 2000)
T-Coffee (Tree-based Consistency Objective Function for alignment Evaluation)
T-Coffee has two main features:
It provides a simple and flexible means of generating multiple alignments, using
heterogeneous data sources.
1. The data from these sources are provided to T-Coffee via a library of pair-wise
alignments. T-Coffee computes multiple alignments using a library that was
generated using a mixture of:
local pair-wise alignments (lalign)
global pair-wise alignments (clustalw)
2. The second main feature of T-Coffee is the optimization method, which is used to
find the multiple alignment that best fits the pair-wise alignments in the input library.
We use a so-called progressive strategy (Feng & Doolittle, 1987; Taylor, 1988;
Thompson et al., 1994), which is similar to that used in ClustalW. This has the
advantage of being fast and relatively robust. Use of a heuristic algorithm that
called library extension. The overall idea is to combine information in such a
manner that the final weight, for any pair of residues, reflects some of the
information contained in the whole library. To do so, a triplet approach is used.