Abstract
Sumar: Programele de aliniere a secvențelor multiple Clustal W și Clustal X au fost complet rescrise în C++. Acest lucru va facilita dezvoltarea ulterioară a algoritmilor de aliniere în viitor și a permis portarea corespunzătoare a programelor la cele mai recente versiuni ale sistemelor de operare Linux, Macintosh și Windows.
Contact:[email protected]
1 INTRODUCERE
Alinierile de secvențe multiple sunt acum una dintre cele mai utilizate analize bioinformatice. Ele sunt necesare în mod obișnuit ca părți ale unor analize mai complicate sau ale unor conducte de analiză și există mai multe pachete foarte utilizate, de exemplu Clustal W (Thompson et al., 1994), Clustal X (Thompson et al., 1997), T-Coffee (Notredame et al., 2000), MAFFT (Katoh et al., 2002) și MUSCLE (Edgar, 2004). Clustal este, de asemenea, cel mai vechi dintre programele cele mai utilizate în prezent, fiind distribuit pentru prima dată prin poștă pe dischete la sfârșitul anilor 1980. Inițial a fost scris în Microsoft Fortran pentru MS-DOS și a rulat inițial pe computerele personale compatibile IBM ca patru programe executabile separate, Clustal1-Clustal4 (Higgins și Sharp, 1988, 1989). Ulterior, acestea au fost rescrise în C și fuzionate într-un singur program, Clustal V (Higgins et al., 1992), care a fost distribuit pentru VAX/VMS, Unix, Apple Macintosh și PC-uri compatibile IBM. Aceste programe au fost distribuite de la serverul de fișiere EMBL (Stoehr și Omond, 1989), un server de e-mail și FTP, cu sediul la EMBL din Heidelberg, Germania.
Programele Clustal actuale derivă toate din Clustal W (Thompson et al., 1994), care a încorporat o nouă schemă de punctaj specifică poziției și o schemă de ponderare pentru reducerea ponderării grupurilor de secvențe suprareprezentate. „W” înseamnă „weights” (ponderi). Aceste programe au fost modificate și completate de mai multe ori din 1994 încoace pentru a crește funcționalitatea și pentru a spori sensibilitatea. De asemenea, ușurința de utilizare a fost mult îmbunătățită prin adăugarea, în 1997, a unei interfețe grafice complete cu utilizatorul (Thompson et al., 1997). Acest lucru a făcut ca întreținerea și dezvoltarea codului să fie complicată, deoarece interfața grafică trebuie modificată și recompilată în mod constant pentru noile sisteme de operare și medii desktop (Windows, Macintosh, VMS, Unix și Linux).
Până la sfârșitul anilor 1990, Clustal W și Clustal X erau cele mai utilizate programe de aliniere multiplă. Acestea erau capabile să alinieze foarte rapid seturi de date de dimensiuni medii și erau ușor de utilizat. Alinierile erau de o calitate suficientă pentru a nu necesita editare sau ajustare manuală foarte des. Această situație s-a schimbat foarte mult odată cu apariția primului set de teste de referință realizat la comandă pentru programele de aliniere multiplă, BAliBASE (Thompson et al., 1999). Acest lucru a fost urmat de apariția T-Coffee, care a fost capabil să realizeze alinieri foarte precise ale unor proteine foarte divergente, dar numai pentru seturi mici de secvențe, având în vedere costul său computațional ridicat. Odată cu creșterea vitezei de procesare a computerelor de birou și cu optimizarea ulterioară a codului T-Coffee, acesta din urmă este acum practic pentru utilizarea de rutină în probleme de aliniere de dimensiuni moderate. Mai recent, au apărut MAFFT și MUSCLE, care au fost, inițial, cel puțin la fel de precise ca Clustal, în ceea ce privește precizia alinierii, dar care erau, de asemenea, extrem de rapide și capabile să alinieze mai multe mii de secvențe. În ultimii 4 sau 5 ani, aceste programe au devenit, de asemenea, din ce în ce mai precise în cazul alinierilor dificile. Cu toate acestea, Clustal W și Clustal X continuă să fie utilizate pe scară foarte largă, din ce în ce mai mult pe site-uri web. Site-ul EBI Clustal, primește literalmente milioane de lucrări de aliniere multiplă pe an.
În acest context am dezvoltat Clustal W 2.0 și Clustal X 2.0. Aceste programe au fost rescrise în C++ cu un model de obiect simplu pentru a facilita întreținerea codului și, mai ales, pentru a facilita modificarea sau chiar înlocuirea unora dintre algoritmii de aliniere. Am produs două programe noi care au un aspect foarte asemănător cu cel al vechilor programe din versiunea 1.83, dar care acum pot fi gestionate mai ușor. De asemenea, am făcut câteva ajustări minore ale algoritmilor de aliniere. Am inclus un nou cod pentru arborii de ghidare UPGMA ca o alternativă la arborii de ghidare obișnuiți Neighbor-Joining. Acest lucru ajută la accelerarea alinierii unor seturi de date extrem de mari de zeci de mii de secvențe. Am inclus, de asemenea, o facilitate de aliniere iterativă pentru a crește precizia alinierii.
ClustalX 2.0 Captură de ecran pe Mac OS X.
ClustalX 2.0.0 Screenshot pe Mac OS X.
Clustal X 2.0 este noua versiune a instrumentului de aliniere grafică Clustal X. Originalul Clustal X a fost dezvoltat cu ajutorul setului de instrumente vibrante al NCBI. Cutia de instrumente vibrant nu mai este susținută, ceea ce a dus la probleme de compilare a Clustal X pe versiuni mai noi de sisteme de operare. Secțiunile de interfață grafică ale Clustal X 2.0 au fost complet rescrise utilizând caseta de instrumente Qt GUI. Qt este o trusă de instrumente GUI C++ ușor de utilizat, multi-platformă. Codul trebuie compilat doar o singură dată pe fiecare dintre platforme. Setul de instrumente Qt oferă un aspect nativ pe platformele Windows, Linux și Mac. Clustal X 2.0 are aceeași funcționalitate ca și Clustal X.
2 NOI CARACTERISTICI
Două noi opțiuni au fost incluse în Clustal W 2.0, pentru a permite o aliniere mai rapidă a seturilor de date foarte mari și pentru a crește precizia alinierii. Opțiunile implicite ale Clustal W And Clustal X 2.0 sunt aceleași ca și în cazul Clustal W 1.83 și vor da aceleași rezultate de aliniere.
Arborii de ghidare din Clustal au fost calculați folosind metoda Neighbor-Joining (NJ), în ultimii 10 ani sau cam așa ceva. În primele versiuni ale programului s-a folosit UPGMA. UPGMA este mai rapidă decât NJ, dar este predispusă să grupeze ramurile lungi împreună atunci când ratele de evoluție sunt foarte inegale în diferite neamuri. Ambii algoritmi au o complexitate de O(N2), dar UPGMA este mai rapid pentru un set de date dat, iar diferența devine pronunțată în cazul în care N este foarte mare. Pe un PC desktop standard, este posibil să se grupeze 10 000 de secvențe în mai puțin de un minut folosind UPGMA, în timp ce NJ ar dura peste o oră. Am reimplementat un algoritm foarte eficient pentru UPGMA, care poate fi apelat cu ajutorul opțiunii din linia de comandă „-clustering=UPGMA”. Este marginal mai puțin precis în cazul punctului de referință Balibase, dar în cazul alinierilor mari (de exemplu, 10 000 de secvențe de globină) acest lucru este compensat de economiile de timp de procesare (2 h față de 12 h).
Iterarea este o metodă rapidă și eficientă de rafinare a alinierilor. În această versiune a Clustal a fost inclusă o schemă de iterație „remove first”, care optimizează scorul Weighted Sum of Pairs (WSP). În timpul fiecărei etape de iterație, fiecare secvență este eliminată pe rând din aliniere și realiniată. Dacă scorul WSP este redus, atunci alinierea rezultată este păstrată. Schema de iterație poate fi utilizată fie pentru a rafina alinierea finală, fie la fiecare etapă a alinierii progresive. Iterarea în timpul alinierii progresive tinde să fie mai precisă, dar, de asemenea, consumă mult mai mult timp, deoarece există 2N-3 noduri în arborele de ghidare. Opțiunea din linia de comandă „-Iteration=Alignment” rafinează alinierea finală, în timp ce opțiunea „-Iteration=Tree” încorporează schema în alinierea progresivă. Numărul de cicluri de iterație este setat prin intermediul opțiunii de linie de comandă ‘-numiters’ (valoarea implicită este 3).
ACKNOWLEDGEMENT
Această lucrare a fost finanțată în principal de Science Foundation Ireland.
Conflict de interese: niciunul declarat.
Note ale autorului
Associate Editor: Alex Bateman
.