Clustal W i Clustal X wersja 2.0

Abstrakt

Podsumowanie: Programy do wyrównywania sekwencji wielokrotnych Clustal W i Clustal X zostały całkowicie przepisane w języku C++. Ułatwi to dalszy rozwój algorytmów wyrównywania w przyszłości oraz umożliwiło poprawne przeniesienie programów na najnowsze wersje systemów operacyjnych Linux, Macintosh i Windows.

Contact:[email protected]

1 WSTĘP

Równania sekwencji wielokrotnych są obecnie jedną z najczęściej używanych analiz bioinformatycznych. Clustal W (Thompson i in., 1994), Clustal X (Thompson i in., 1997), T-Coffee (Notredame i in., 2000), MAFFT (Katoh i in., 2002) i MUSCLE (Edgar, 2004). Clustal jest również najstarszym z obecnie najczęściej używanych programów, który po raz pierwszy został rozpowszechniony pocztą na dyskietkach pod koniec lat 80-tych. Początkowo został napisany w Microsoft Fortran dla MS-DOS i początkowo działał na komputerach osobistych kompatybilnych z IBM jako cztery oddzielne programy wykonywalne, Clustal1-Clustal4 (Higgins i Sharp, 1988, 1989). Zostały one później przepisane w języku C i połączone w jeden program, Clustal V (Higgins et al., 1992), który był rozprowadzany na VAX/VMS, Unix, Apple Macintosh i komputery osobiste kompatybilne z IBM. Programy te były dystrybuowane z serwera plików EMBL (Stoehr i Omond, 1989), e-mail i serwer FTP, z siedzibą w EMBL w Heidelbergu, Niemcy.

Obecne programy Clustal wszystkie wywodzą się z Clustal W (Thompson i in., 1994), który zawierał nowatorski schemat punktacji specyficznej dla pozycji i schemat ważenia do obniżania wagi nadreprezentowanych grup sekwencji. Litera „W” oznacza „wagi”. Programy te były wielokrotnie zmieniane i uzupełniane od 1994 roku w celu zwiększenia funkcjonalności i czułości. Przyjazność dla użytkownika została również znacznie zwiększona poprzez dodanie w 1997 r. w pełni graficznego interfejsu użytkownika (Thompson i in., 1997). To spowodowało, że kod stał się skomplikowany w utrzymaniu i rozwoju, ponieważ interfejs graficzny musi być ciągle modyfikowany i rekompilowany dla nowych systemów operacyjnych i środowisk graficznych (Windows, Macintosh, VMS, Unix i Linux).

Do końca lat 90-tych Clustal W i Clustal X były najczęściej używanymi programami do wielokrotnego wyrównywania. Umożliwiały one bardzo szybkie wyrównanie średniej wielkości zbiorów danych i były łatwe w użyciu. Wyrównania były na tyle dobrej jakości, że nie wymagały zbyt często ręcznej edycji czy poprawek. Sytuacja ta uległa znacznej zmianie wraz z pojawieniem się BAliBASE (Thompson et al., 1999) – pierwszego, wykonanego na zamówienie, wzorcowego zestawu testowego dla programów do wielokrotnego wyrównywania. Następnie pojawił się T-Coffee, który był w stanie wykonać bardzo dokładne wyrównania bardzo rozbieżnych białek, ale tylko dla małych zbiorów sekwencji, ze względu na wysoki koszt obliczeniowy. Wraz ze wzrostem szybkości przetwarzania w komputerach stacjonarnych i późniejszą optymalizacją kodu T-Coffee, jest on obecnie praktyczny do rutynowego stosowania dla umiarkowanie dużych problemów wyrównania. Niedawno pojawiły się MAFFT i MUSCLE; które początkowo były co najmniej tak dokładne jak Clustal, jeśli chodzi o dokładność wyrównania, ale które były również niezwykle szybkie i zdolne do wyrównania wielu tysięcy sekwencji. W ciągu ostatnich 4 czy 5 lat, programy te również stopniowo stawały się coraz dokładniejsze przy trudnych wyrównaniach. Mimo to, Clustal W i Clustal X są nadal bardzo szeroko stosowane, coraz częściej na stronach internetowych. Strona EBI Clustal otrzymuje dosłownie miliony zadań wielokrotnego dopasowania rocznie.

To właśnie w tym kontekście opracowaliśmy Clustal W 2.0 i Clustal X 2.0. Programy te zostały napisane od nowa w C++ z prostym modelem obiektowym, aby ułatwić utrzymanie kodu, a co ważniejsze, aby ułatwić modyfikację lub nawet zastąpienie niektórych algorytmów wyrównania. Stworzyliśmy dwa nowe programy, które są bardzo podobne w wyglądzie i działaniu do starszych programów z wersji 1.83, ale którymi można teraz łatwiej zarządzać. Wprowadziliśmy również kilka drobnych poprawek do algorytmów wyrównywania. Zamieściliśmy nowy kod dla drzew prowadzących UPGMA jako alternatywę dla zwykłych drzew prowadzących Neighbor-Joining. Pomaga to przyspieszyć wyrównanie bardzo dużych zbiorów danych zawierających dziesiątki tysięcy sekwencji. Zawarliśmy również iteracyjne wyrównanie w celu zwiększenia dokładności wyrównania.

Clustal X 2.0 jest nową wersją graficznego narzędzia wyrównującego Clustal X. Oryginalny Clustal X został opracowany przy użyciu vibrant toolbox NCBI. vibrant toolbox nie jest już wspierany, co doprowadziło do problemów z kompilacją Clustal X na nowszych wersjach systemów operacyjnych. Sekcje interfejsu graficznego w Clustal X 2.0 zostały całkowicie przepisane przy użyciu Qt GUI toolbox. Qt jest łatwym w użyciu, wieloplatformowym zestawem narzędzi GUI w języku C++. Kod musi być skompilowany tylko raz na każdej z platform. Pakiet narzędziowy Qt zapewnia natywny wygląd i działanie na platformach Windows, Linux i Mac. Clustal X 2.0 ma taką samą funkcjonalność jak Clustal X.

2 NOWE FUNKCJE

Dwie nowe opcje zostały włączone do Clustal W 2.0, aby umożliwić szybsze wyrównanie bardzo dużych zbiorów danych i zwiększyć dokładność wyrównania. Domyślne opcje w Clustal W i Clustal X 2.0 są takie same jak w Clustal W 1.83 i dają takie same wyniki wyrównania.

Drzewa przewodnie w Clustal były obliczane przy użyciu metody Neighbor-Joining (NJ), przez ostatnie 10 lat lub tak. W najwcześniejszych wersjach programu używana była metoda UPGMA. UPGMA jest szybsza niż NJ, ale ma skłonność do grupowania długich gałęzi razem, gdy tempo ewolucji jest bardzo nierówne w różnych rodach. Oba algorytmy mają złożoność O(N2), ale UPGMA jest szybsza dla danego zbioru danych, a różnica staje się wyraźna przy bardzo dużych N. Na standardowym komputerze stacjonarnym można przy pomocy UPGMA zgrupować 10 000 sekwencji w mniej niż minutę, podczas gdy NJ zajęłoby to ponad godzinę. Zaimplementowaliśmy ponownie bardzo wydajny algorytm dla UPGMA, który można wywołać za pomocą opcji wiersza poleceń ’-clustering=UPGMA’. Jest on minimalnie mniej dokładny w benchmarku Balibase, ale w przypadku dużych dopasowań (np. 10 000 sekwencji globiny) jest to równoważone przez oszczędność czasu przetwarzania (2 h w porównaniu z 12 h).

Iteracja jest szybką i efektywną metodą udoskonalania dopasowań. Schemat iteracji „najpierw usuń”, który optymalizuje wynik ważonej sumy par (WSP), został włączony do tej wersji Clustala. Podczas każdego kroku iteracji, każda sekwencja jest po kolei usuwana z dopasowania i ponownie wyrównywana. Jeśli wynik WSP jest zredukowany, wówczas wynikowe wyrównanie jest zachowywane. Schemat iteracji może być użyty zarówno do ostatecznego wyrównania, jak i w każdym kroku wyrównania progresywnego. Iteracja podczas progresywnego zrównoleglenia jest zwykle bardziej dokładna, ale też znacznie bardziej czasochłonna, gdyż w drzewie przewodników znajduje się 2N-3 węzłów. Opcja wiersza poleceń ’-Iteration=Alignment’ dopracowuje ostateczne wyrównanie, podczas gdy opcja ’-Iteration=Tree’ włącza schemat do wyrównania progresywnego. Liczba cykli iteracji jest ustawiana za pomocą opcji wiersza poleceń ’-numiters’ (domyślnie 3).

PODZIĘKOWANIA

Ta praca była głównie finansowana przez Science Foundation Ireland.

Konflikt interesów: nie zgłoszono.

Uwagi autorów

.