5 Clustal W

GLI ALLINEAMENTI MULTIPLI

Uno dei problemi principali di FASTA e BLAST è che effettuano soltanto allineamenti

pair-wise (tra coppie di sequenze). Tuttavia, se si vogliono fare studi che permettano di

relazionare più sequenze omologhe e spiegarne l’evoluzione ritornano utili gli

allineamenti multipli. Essi possono essere utilizzati per la costruzione di alberi

filogenetici, per identificare motivi di sequenza comuni e conservati, per prevedere la

struttura secondaria delle proteine, e così via. Possono inoltre essere utilizzati per

codificare le caratteristiche strutturali di una superfamiglia proteica, in modo tale da

ottenere una “impronta digitale” che può essere utilizzata per cercare nelle banche

dati altri membri evolutivamente distanti appartenenti alla medesima famiglia,

altrimenti difficilmente individuabili. Il problema principale degli MSA (Multiple

Sequences Alignment) è come tener conto allo stesso tempo di tutti i matches,

mismatches, gaps e del grado di variazione. Per gli allineamenti multipli non è

possibile usare algoritmi di programmazione dinamica: impiegherebbero troppo

tempo. La grande utilità pratica degli allineamenti multipli ha stimolato lo sviluppo di

tecniche di calcolo in grado di risolvere almeno in parte le difficoltà intrinseche alla

costruzione di questi allineamenti. Il primo tentativo più ovvio è stato estendere gli

algoritmi dinamici per l’allineamento di due sequenze al caso di allineamenti multipli.

In questo modo, si potrebbe ottenere l’allineamento multiplo ottimale che massimizza

la somiglianza tra tutte le coppie di sequenze ivi contenute. Purtroppo gli algoritmi

dinamici non possono essere semplicemente estesi all’allineamento di più sequenze, a

causa della complessità dell’algoritmo. Per esempio, date N sequenze di lunghezza M,

la quantità di memoria e il numero di passi di calcolo necessari per elaborare

N

l’allineamento crescono come M . quindi già per numeri relativamente piccoli, il

problema diviene intrattabile. Di fatto, gli algoritmi dinamici sono stati applicati solo al

caso dell’allineamento di poche sequenze. Per allineare efficientemente decine e

decine di sequenze, è stato necessario ricorrere ad algoritmi euristici. Questi

algoritmi forniscono una soluzione approssimata ma molto vicina a quella ottimale.

Negli anni sono state proposte diverse strategie euristiche, ma forse quella che ha

dato i maggiori risultati è l’allineamento progressivo di coppie di sequenze.

W

CLUSTAL

Uno dei programmi oggi più diffusi di allineamento multiplo che utilizza una strategia

di tipo progressivo è ClustalW. Questo programma applica progressivamente

l’algoritmo di allineamento dinamico a coppie di sequenze. Descriviamo i passaggi

chiave di cui consiste la versione base del metodo.

FASE 1

Nella prima fase, vengono allineate tutte le sequenze (proteiche o nucleotidiche) con

tutte le sequenze. Per esempio, supponiamo di avere 6 sequenze (A, B, C, D, E, F). Si

allinea la sequenza A con la sequenza B, poi con la s