Abstract
Sommario: I programmi di allineamento di sequenze multiple Clustal W e Clustal X sono stati completamente riscritti in C++. Questo faciliterà l’ulteriore sviluppo degli algoritmi di allineamento in futuro e ha permesso un adeguato porting dei programmi alle ultime versioni dei sistemi operativi Linux, Macintosh e Windows.
Contact:[email protected]
1 INTRODUZIONE
Gli allineamenti di sequenze multiple sono ora una delle analisi bioinformatiche più usate. Sono necessari di routine come parti di analisi più complicate o pipeline di analisi e ci sono diversi pacchetti molto usati, per esempio Clustal W (Thompson et al., 1994), Clustal X (Thompson et al., 1997), T-Coffee (Notredame et al., 2000), MAFFT (Katoh et al., 2002) e MUSCLE (Edgar, 2004). Clustal è anche il più vecchio dei programmi attualmente più usati, essendo stato distribuito per la prima volta per posta su floppy disk alla fine degli anni ’80. Fu inizialmente scritto in Microsoft Fortran per MS-DOS e originariamente girava su personal computer IBM compatibili come quattro programmi eseguibili separati, Clustal1-Clustal4 (Higgins e Sharp, 1988, 1989). Questi furono successivamente riscritti in C e fusi in un unico programma, Clustal V (Higgins et al., 1992), che fu distribuito per VAX/VMS, Unix, Apple Macintosh e PC IBM compatibili. Questi programmi sono stati distribuiti dall’EMBL File server (Stoehr e Omond, 1989), un server e-mail e FTP, basato presso l’EMBL di Heidelberg, Germania.
Gli attuali programmi Clustal derivano tutti da Clustal W (Thompson et al., 1994), che ha incorporato un nuovo schema di punteggio specifico per la posizione e uno schema di ponderazione per ridurre i gruppi di sequenze sovra-rappresentati. La “W” sta per “pesi”. Questi programmi sono stati modificati e aggiunti molte volte dal 1994 per aumentare la funzionalità e la sensibilità. La facilità d’uso è stata notevolmente migliorata dall’aggiunta, nel 1997, di un’interfaccia grafica completa (Thompson et al., 1997). Questo ha reso il codice complicato da mantenere e sviluppare, poiché l’interfaccia grafica deve essere costantemente modificata e ricompilata per i nuovi sistemi operativi e ambienti desktop (Windows, Macintosh, VMS, Unix e Linux).
Entro la fine degli anni 90, Clustal W e Clustal X erano i programmi di allineamento multiplo più usati. Erano in grado di allineare serie di dati di medie dimensioni molto rapidamente ed erano facili da usare. Gli allineamenti erano di qualità sufficiente da non richiedere molto spesso modifiche o aggiustamenti manuali. Questa situazione è cambiata notevolmente con la comparsa del primo set di test di riferimento personalizzato per i programmi di allineamento multiplo, BAliBASE (Thompson et al., 1999). Questo fu seguito dalla comparsa di T-Coffee che era in grado di fare allineamenti molto accurati di proteine molto divergenti ma solo per piccoli insiemi di sequenze, dato il suo alto costo computazionale. Con l’aumento della velocità di elaborazione dei computer desktop, e la successiva ottimizzazione del codice di T-Coffee, quest’ultimo è ora pratico per l’uso di routine su problemi di allineamento di dimensioni moderate. Più recentemente sono apparsi MAFFT e MUSCLE, che inizialmente erano accurati almeno quanto Clustal, in termini di precisione di allineamento, ma che erano anche estremamente veloci e in grado di allineare molte migliaia di sequenze. Negli ultimi 4 o 5 anni, anche questi programmi sono diventati gradualmente sempre più accurati con allineamenti difficili. Ciononostante, Clustal W e Clustal X continuano ad essere molto usati, sempre più spesso su siti web. Il sito EBI Clustal riceve letteralmente milioni di lavori di allineamento multiplo all’anno.
È in questo contesto che abbiamo sviluppato Clustal W 2.0 e Clustal X 2.0. Questi programmi sono stati riscritti in C++ con un semplice modello a oggetti per rendere più facile la manutenzione del codice e, cosa più importante, per rendere più facile modificare o addirittura sostituire alcuni degli algoritmi di allineamento. Abbiamo prodotto due nuovi programmi che sono molto simili nell’aspetto ai vecchi programmi della versione 1.83 ma che ora possono essere gestiti più facilmente. Abbiamo anche fatto alcuni aggiustamenti minori agli algoritmi di allineamento. Abbiamo incluso un nuovo codice per gli alberi guida UPGMA come alternativa ai soliti alberi guida Neighbor-Joining. Questo aiuta a velocizzare l’allineamento di serie di dati estremamente grandi di decine di migliaia di sequenze. Abbiamo anche incluso una funzione di allineamento iterativo per aumentare la precisione dell’allineamento.
ClustalX 2.0 Screenshot su Mac OS X.
ClustalX 2.0 su Mac OS X.
Clustal X 2.0 è la nuova versione dello strumento di allineamento grafico Clustal X. L’originale Clustal X è stato sviluppato usando il vibrant toolbox dell’NCBI. Il vibrant toolbox non è più supportato, il che ha portato a problemi di compilazione di Clustal X sulle nuove versioni dei sistemi operativi. Le sezioni dell’interfaccia grafica di Clustal X 2.0 sono state completamente riscritte usando il toolbox Qt GUI. Qt è un toolkit GUI C++ multipiattaforma e facile da usare. Il codice deve essere compilato solo una volta su ogni piattaforma. Il toolbox Qt fornisce un look and feel nativo sulle piattaforme Windows, Linux e Mac. Clustal X 2.0 ha la stessa funzionalità di Clustal X.
2 NUOVE CARATTERISTICHE
Due nuove opzioni sono state incluse in Clustal W 2.0, per permettere un allineamento più veloce di serie di dati molto grandi e per aumentare la precisione dell’allineamento. Le opzioni di default di Clustal W e Clustal X 2.0 sono le stesse di Clustal W 1.83, e daranno gli stessi risultati di allineamento.
Gli alberi guida in Clustal sono stati calcolati usando il metodo Neighbor-Joining (NJ), negli ultimi 10 anni circa. Nelle prime versioni del programma veniva usato UPGMA. UPGMA è più veloce di NJ ma tende a raggruppare lunghi rami insieme quando i tassi evolutivi sono molto disuguali nei diversi lignaggi. Entrambi gli algoritmi hanno una complessità di O(N2) ma UPGMA è più veloce per un dato set di dati e la differenza diventa pronunciata con N molto grande. Su un PC desktop standard, è possibile raggruppare 10 000 sequenze in meno di un minuto usando UPGMA, mentre NJ richiederebbe più di un’ora. Abbiamo reimplementato un algoritmo molto efficiente per UPGMA che può essere chiamato usando l’opzione della linea di comando ‘-clustering=UPGMA’. E’ marginalmente meno accurato sul benchmark Balibase, ma su grandi allineamenti (ad esempio 10 000 sequenze di globina) questo è compensato dal risparmio nel tempo di elaborazione (2 ore contro 12 ore).
L’iterazione è un metodo rapido ed efficace per raffinare gli allineamenti. Uno schema di iterazione “rimuovi prima”, che ottimizza il punteggio Weighted Sum of Pairs (WSP), è stato incluso in questa versione di Clustal. Durante ogni passo di iterazione, ogni sequenza viene rimossa dall’allineamento a turno e riallineata. Se il punteggio WSP è ridotto, l’allineamento risultante viene mantenuto. Lo schema di iterazione può essere usato sia per raffinare l’allineamento finale che ad ogni passo dell’allineamento progressivo. L’iterazione durante l’allineamento progressivo tende ad essere più accurata ma anche molto più lunga, dato che ci sono 2N-3 nodi nell’albero guida. L’opzione della linea di comando ‘-Iteration=Alignment’ perfeziona l’allineamento finale, mentre l’opzione ‘-Iteration=Tree’ incorpora lo schema nell’allineamento progressivo. Il numero di cicli di iterazione è impostato tramite l’opzione della riga di comando ‘-numiters’ (il default è 3).
ACKNOWLEDGEMENT
Questo lavoro è stato finanziato principalmente dalla Science Foundation Ireland.
Conflitto di interessi: nessuno dichiarato.
Note dell’autore
Associate Editor: Alex Bateman