Clustal W and Clustal X version 2.0

Abstract

Samenvatting: De Clustal W en Clustal X multiple sequence alignment programma’s zijn volledig herschreven in C++. Dit zal de verdere ontwikkeling van de alignment algoritmen in de toekomst vergemakkelijken en heeft het mogelijk gemaakt de programma’s te porten naar de laatste versies van Linux, Macintosh en Windows besturingssystemen.

Contact:[email protected]

1 INLEIDING

Multiple sequence alignments zijn nu een van de meest gebruikte bioinformatica analyses. Ze zijn routinematig nodig als onderdeel van meer gecompliceerde analyses of analysepijplijnen en er zijn verschillende zeer veel gebruikte pakketten, bijv. Clustal W (Thompson et al., 1994), Clustal X (Thompson et al., 1997), T-Coffee (Notredame et al., 2000), MAFFT (Katoh et al., 2002) en MUSCLE (Edgar, 2004). Clustal is ook het oudste van de momenteel meest gebruikte programma’s: het werd voor het eerst per post verspreid op diskettes aan het eind van de jaren 1980. Het werd aanvankelijk geschreven in Microsoft Fortran voor MS-DOS en draaide oorspronkelijk op IBM-compatibele personal computers als vier afzonderlijke uitvoerbare programma’s, Clustal1-Clustal4 (Higgins en Sharp, 1988, 1989). Deze werden later herschreven in C en samengevoegd in één enkel programma, Clustal V (Higgins et al., 1992), dat werd verspreid voor VAX/VMS, Unix, Apple Macintosh en IBM-compatibele PC’s. Deze programma’s werden verspreid vanaf de EMBL File server (Stoehr en Omond, 1989), een e-mail en FTP server, gevestigd op het EMBL in Heidelberg, Duitsland.

De huidige Clustal programma’s zijn allemaal afgeleid van Clustal W (Thompson et al., 1994), dat een nieuw positie-specifiek scoringsschema en een wegingsschema bevatte om oververtegenwoordigde sequentiegroepen naar beneden te halen. De “W” staat voor “gewichten”. Deze programma’s zijn sinds 1994 vele malen gewijzigd en aangevuld om de functionaliteit en de gevoeligheid te vergroten. De gebruikersvriendelijkheid is ook sterk verbeterd door de toevoeging, in 1997, van een volledige grafische gebruikersinterface (Thompson et al., 1997). Dit heeft het onderhoud en de ontwikkeling van de code gecompliceerd gemaakt, omdat de grafische interface voortdurend moet worden aangepast en gecompileerd voor nieuwe besturingssystemen en desktop-omgevingen (Windows, Macintosh, VMS, Unix en Linux).

Tegen het eind van de jaren negentig waren Clustal W en Clustal X de meest gebruikte meervoudige uitlijningsprogramma’s. Zij waren in staat om middelgrote datasets zeer snel uit te lijnen en waren gemakkelijk in het gebruik. De uitlijningen waren van voldoende kwaliteit om niet vaak handmatig bewerkt of aangepast te hoeven worden. Deze situatie veranderde sterk met het verschijnen van de eerste op maat gemaakte benchmark test set voor meervoudige uitlijningsprogramma’s, BAliBASE (Thompson et al., 1999). Daarna verscheen T-Coffee, dat zeer nauwkeurige uitlijningen van zeer uiteenlopende eiwitten kon maken, maar alleen voor kleine reeksen sequenties, gezien de hoge computerkosten. Met de toename van de verwerkingssnelheid van desktopcomputers, en de daaropvolgende optimalisering van de T-Coffee code, is deze nu praktisch voor routinematig gebruik op matig grote alignment problemen. Meer recentelijk verschenen MAFFT en MUSCLE, die aanvankelijk minstens even nauwkeurig waren als Clustal wat betreft de nauwkeurigheid van de alignment, maar die ook extreem snel waren en in staat om vele duizenden sequenties te aligneren. In de afgelopen 4 of 5 jaar zijn ook deze programma’s geleidelijk aan steeds nauwkeuriger geworden bij moeilijke alignments. Niettemin worden Clustal W en Clustal X nog steeds zeer veel gebruikt, steeds meer op websites. De EBI Clustal site, krijgt letterlijk miljoenen multiple alignment opdrachten per jaar.

Het is in deze context dat wij Clustal W 2.0 en Clustal X 2.0 hebben ontwikkeld. Deze programma’s zijn herschreven in C++ met een eenvoudig objectmodel om de code gemakkelijker te kunnen onderhouden en, wat nog belangrijker is, om het gemakkelijker te maken sommige uitlijningsalgoritmen te wijzigen of zelfs te vervangen. Wij hebben twee nieuwe programma’s gemaakt die qua uiterlijk en gevoel sterk lijken op de oudere versie 1.83 programma’s, maar die nu gemakkelijker kunnen worden beheerd. We hebben ook enkele kleine aanpassingen gedaan aan de uitlijningsalgoritmen. We hebben nieuwe code opgenomen voor UPGMA-geleidebomen als alternatief voor de gebruikelijke Neighbor-Joining-geleidebomen. Dit versnelt de alignment van extreem grote datasets van tienduizenden sequenties. We hebben ook een iteratieve uitlijningsfaciliteit toegevoegd om de nauwkeurigheid van de uitlijning te vergroten.

Clustal X 2.0 is de nieuwe versie van het grafische uitlijningsgereedschap Clustal X. Het oorspronkelijke Clustal X werd ontwikkeld met behulp van de vibrant toolbox van de NCBI. De vibrant toolbox wordt niet langer ondersteund, wat leidde tot problemen met het compileren van Clustal X op nieuwere versies van besturingssystemen. De grafische interface van Clustal X 2.0 is volledig herschreven met behulp van de Qt GUI toolbox. Qt is een eenvoudig te gebruiken, multi-platform C++ GUI toolkit. De code hoeft slechts eenmaal gecompileerd te worden op elk platform. De Qt toolbox biedt een native look en feel op Windows, Linux en Mac platforms. Clustal X 2.0 heeft dezelfde functionaliteit als Clustal X.

2 NIEUWE FUNCTIES

Twee nieuwe opties zijn opgenomen in Clustal W 2.0, om snellere uitlijning van zeer grote datasets mogelijk te maken en om de nauwkeurigheid van de uitlijning te vergroten. De standaard opties van Clustal W en Clustal X 2.0 zijn dezelfde als Clustal W 1.83, en zullen dezelfde alignment resultaten geven.

De guide trees in Clustal zijn berekend met de Neighbor-Joining (NJ) methode, voor de laatste 10 jaar of zo. In de vroegste versies van het programma werd UPGMA gebruikt. UPGMA is sneller dan NJ maar heeft de neiging lange takken samen te clusteren wanneer de evolutiesnelheden in de verschillende lijnen zeer ongelijk zijn. Beide algoritmen hebben een complexiteit van O(N2) maar UPGMA is sneller voor een gegeven gegevensverzameling en het verschil wordt duidelijk bij zeer grote N. Op een standaard desktop PC is het mogelijk 10 000 sequenties in minder dan een minuut te clusteren met UPGMA, terwijl NJ meer dan een uur zou vergen. Wij hebben een zeer efficiënt algoritme voor UPGMA geïmplementeerd, dat kan worden opgeroepen met de opdrachtregeloptie ‘-clustering=UPGMA’. Het is marginaal minder nauwkeurig op de Balibase benchmark, maar op grote alignments (b.v. 10 000 globin sequenties) wordt dit gecompenseerd door de besparing in verwerkingstijd (2 uur versus 12 uur).

Iteratie is een snelle en effectieve methode om alignments te verfijnen. Een ‘remove first’ iteratieschema, dat de Weighted Sum of Pairs (WSP) score optimaliseert, is in deze versie van Clustal opgenomen. Tijdens elke iteratiestap wordt elke sequentie op zijn beurt uit de uitlijning verwijderd en opnieuw uitgelijnd. Als de WSP-score wordt verlaagd, wordt de resulterende uitlijning behouden. Het iteratieschema kan worden gebruikt om de uiteindelijke uitlijning te verfijnen of bij elke stap in de progressieve uitlijning. Itereren tijdens de progressieve uitlijning is meestal nauwkeuriger, maar ook veel tijdrovender omdat er 2N-3 knooppunten in de leidraadboom zijn. De commandoregeloptie ‘-Iteration=Alignment’ verfijnt de uiteindelijke uitlijning, terwijl de optie ‘-Iteration=Tree’ het schema opneemt in de progressieve uitlijning. Het aantal iteratiecycli wordt ingesteld via de commandoregeloptie ‘-numiters’ (standaard is 3).

ACKNOWLEDGEMENT

Dit werk werd hoofdzakelijk gefinancierd door Science Foundation Ireland.

Conflict of Interest: none declared.

Author notes