Clustal W a Clustal X verze 2.0

Abstrakt

Shrnutí: Programy pro zarovnávání vícenásobných sekvencí Clustal W a Clustal X byly kompletně přepsány do jazyka C++. To usnadní další vývoj algoritmů zarovnávání v budoucnu a umožnilo řádné přenesení programů na nejnovější verze operačních systémů Linux, Macintosh a Windows.

Contact:[email protected]

1 ÚVOD

Zarovnávání vícenásobných sekvencí je v současnosti jednou z nejpoužívanějších bioinformatických analýz. Jsou rutinně potřebné jako součást složitějších analýz nebo analytických pipeline a existuje několik velmi rozšířených balíčků, například Clustal W (Thompson et al., 1994), Clustal X (Thompson et al., 1997), T-Coffee (Notredame et al., 2000), MAFFT (Katoh et al., 2002) a MUSCLE (Edgar, 2004). Clustal je také nejstarším ze současných nejpoužívanějších programů, který byl poprvé distribuován poštou na disketách koncem 80. let 20. století. Původně byl napsán v jazyce Microsoft Fortran pro MS-DOS a původně běžel na osobních počítačích kompatibilních s IBM jako čtyři samostatné spustitelné programy Clustal1-Clustal4 (Higgins a Sharp, 1988, 1989). Ty byly později přepsány do jazyka C a sloučeny do jediného programu Clustal V (Higgins a kol., 1992), který byl distribuován pro VAX/VMS, Unix, Apple Macintosh a IBM kompatibilní osobní počítače. Tyto programy byly distribuovány z EMBL File serveru (Stoehr a Omond, 1989), e-mailového a FTP serveru, který sídlí v EMBL v Heidelbergu v Německu.

Všechny současné programy Clustal jsou odvozeny od programu Clustal W (Thompson et al., 1994), který zahrnoval nové skórovací schéma specifické pro jednotlivé pozice a váhové schéma pro snížení váhy nadměrně zastoupených skupin sekvencí. Písmeno „W“ znamená „váhy“. Tyto programy byly od roku 1994 mnohokrát pozměněny a doplněny s cílem zvýšit funkčnost a citlivost. Uživatelská přívětivost byla rovněž výrazně zvýšena přidáním plného grafického uživatelského rozhraní v roce 1997 (Thompson et al., 1997). To zkomplikovalo údržbu a vývoj kódu, protože grafické rozhraní musí být neustále upravováno a překompilováváno pro nové operační systémy a desktopová prostředí (Windows, Macintosh, VMS, Unix a Linux).

Koncem devadesátých let byly programy Clustal W a Clustal X nejpoužívanějšími programy pro vícenásobné zarovnávání. Dokázaly velmi rychle zarovnávat středně velké soubory dat a snadno se používaly. Zarovnání byla dostatečně kvalitní, takže nevyžadovala příliš časté ruční úpravy nebo přizpůsobení. Tato situace se výrazně změnila s příchodem první vlastní srovnávací testovací sady pro programy pro vícenásobné zarovnávání, BAliBASE (Thompson et al., 1999). Následoval výskyt programu T-Coffee, který byl schopen provádět velmi přesná zarovnání velmi odlišných proteinů, ale vzhledem k vysokým výpočetním nákladům pouze pro malé soubory sekvencí. S nárůstem výpočetní rychlosti stolních počítačů a následnou optimalizací kódu T-Coffee je nyní tento program praktický pro rutinní použití u středně velkých zarovnávacích problémů. Nedávno se objevily MAFFT a MUSCLE, které byly zpočátku přinejmenším stejně přesné jako Clustal, pokud jde o přesnost zarovnání, ale které byly také extrémně rychlé a dokázaly zarovnat mnoho tisíc sekvencí. Během posledních 4 nebo 5 let se tyto programy postupně stávaly stále přesnějšími i v případě obtížných zarovnání. Přesto jsou programy Clustal W a Clustal X nadále velmi široce používány, stále častěji na webových stránkách. Na stránky EBI Clustal, přicházejí doslova miliony úloh vícenásobného zarovnávání ročně.

V této souvislosti jsme vyvinuli Clustal W 2.0 a Clustal X 2.0. Tyto programy byly přepsány v jazyce C++ s jednoduchým objektovým modelem, aby se usnadnila údržba kódu, a co je důležitější, aby bylo snazší upravit nebo dokonce nahradit některé algoritmy zarovnávání. Vytvořili jsme dva nové programy, které jsou svým vzhledem velmi podobné starším programům verze 1.83, ale nyní je lze snadněji spravovat. Provedli jsme také několik drobných úprav zarovnávacích algoritmů. Zahrnuli jsme nový kód pro vodicí stromy UPGMA jako alternativu k obvyklým vodicím stromům Neighbor-Joining. To pomáhá urychlit zarovnávání extrémně velkých datových souborů o desítkách tisíc sekvencí. Zahrnuli jsme také možnost iterativního zarovnání pro zvýšení přesnosti zarovnání.

. Původní Clustal X byl vyvinut pomocí vibračního toolboxu NCBI. Vibrant toolbox již není podporován, což vedlo k problémům s kompilací Clustal X na novějších verzích operačních systémů. Části grafického rozhraní programu Clustal X 2.0 byly kompletně přepsány pomocí Qt GUI toolboxu. Qt je snadno použitelná multiplatformní sada nástrojů grafického uživatelského rozhraní v jazyce C++. Kód stačí na každé z platforem zkompilovat pouze jednou. Qt toolbox poskytuje nativní vzhled na platformách Windows, Linux a Mac. Clustal X 2.0 má stejné funkce jako Clustal X.

2 NOVÉ FUNKCE

Dvě nové možnosti byly zahrnuty do Clustal W 2.0, aby umožnily rychlejší zarovnání velmi rozsáhlých souborů dat a zvýšily přesnost zarovnání. Výchozí možnosti Clustal W A Clustal X 2.0 jsou stejné jako u Clustal W 1.83 a poskytnou stejné výsledky zarovnání.

Vodicí stromy v programu Clustal byly v posledních přibližně 10 letech počítány metodou Neighbor-Joining (NJ). V prvních verzích programu se používala metoda UPGMA. UPGMA je rychlejší než NJ, ale má sklon shlukovat dlouhé větve dohromady, pokud je rychlost evoluce v různých liniích velmi nerovnoměrná. Oba algoritmy mají složitost O(N2), ale UPGMA je pro daný soubor dat rychlejší a rozdíl se projeví při velmi velkém N. Na standardním stolním počítači je možné pomocí UPGMA shlukovat 10 000 sekvencí za méně než minutu, zatímco NJ by to trvalo více než hodinu. Reimplementovali jsme velmi efektivní algoritmus pro UPGMA, který lze vyvolat pomocí volby příkazového řádku ‚-clustering=UPGMA‘. V benchmarku Balibase je nepatrně méně přesný, ale u velkých zarovnání (např. 10 000 globinových sekvencí) je to kompenzováno úsporou času zpracování (2 h oproti 12 h).

Iterace je rychlá a účinná metoda zpřesňování zarovnání. Do této verze programu Clustal bylo zahrnuto iterační schéma „remove first“, které optimalizuje skóre WSP (Weighted Sum of Pairs). Během každého kroku iterace je každá sekvence postupně odstraněna ze zarovnání a znovu zarovnána. Pokud se skóre WSP sníží, výsledné zarovnání se zachová. Iterační schéma lze použít buď ke zpřesnění konečného zarovnání, nebo v každém kroku postupného zarovnávání. Iterace během postupného zarovnávání bývá přesnější, ale také mnohem časově náročnější, protože ve vodicím stromě je 2N-3 uzlů. Volba příkazového řádku ‚-Iteration=Alignment‘ zpřesňuje konečné zarovnání, zatímco volba ‚-Iteration=Tree‘ začleňuje schéma do postupného zarovnání. Počet iteračních cyklů se nastavuje pomocí volby příkazového řádku ‚-numiters‘ (výchozí hodnota je 3).

PODĚKOVÁNÍ

Tato práce byla převážně financována z prostředků Science Foundation Ireland.

Střet zájmů: není deklarován.

Poznámky pro autory

.