Clustal W et Clustal X version 2.0

Abstract

Résumé : Les programmes d’alignement de séquences multiples Clustal W et Clustal X ont été complètement réécrits en C++. Cela facilitera le développement ultérieur des algorithmes d’alignement dans le futur et a permis un portage correct des programmes vers les dernières versions des systèmes d’exploitation Linux, Macintosh et Windows.

Contact:[email protected]

1 INTRODUCTION

Les alignements de séquences multiples sont maintenant l’une des analyses bioinformatiques les plus utilisées. Ils sont nécessaires de façon routinière comme parties d’analyses plus compliquées ou de pipelines d’analyse et il existe plusieurs paquets très largement utilisés, par exemple Clustal W (Thompson et al., 1994), Clustal X (Thompson et al., 1997), T-Coffee (Notredame et al., 2000), MAFFT (Katoh et al., 2002) et MUSCLE (Edgar, 2004). Clustal est également le plus ancien des programmes actuellement les plus utilisés, ayant été distribué pour la première fois par courrier sur des disquettes à la fin des années 1980. Il était initialement écrit en Microsoft Fortran pour MS-DOS et fonctionnait sur des ordinateurs personnels compatibles IBM sous la forme de quatre programmes exécutables distincts, Clustal1-Clustal4 (Higgins et Sharp, 1988, 1989). Ils ont ensuite été réécrits en C et fusionnés en un seul programme, Clustal V (Higgins et al., 1992), qui a été distribué pour VAX/VMS, Unix, Apple Macintosh et les PC compatibles IBM. Ces programmes ont été distribués à partir du serveur de fichiers EMBL (Stoehr et Omond, 1989), un serveur de courrier électronique et FTP, basé à l’EMBL à Heidelberg, en Allemagne.

Les programmes Clustal actuels dérivent tous de Clustal W (Thompson et al., 1994), qui a incorporé un nouveau schéma de notation spécifique à la position et un schéma de pondération pour pondérer à la baisse les groupes de séquences surreprésentés. Le « W » signifie « poids ». Ces programmes ont été modifiés et complétés à de nombreuses reprises depuis 1994 afin d’accroître leur fonctionnalité et leur sensibilité. La convivialité a également été grandement améliorée par l’ajout, en 1997, d’une interface utilisateur graphique complète (Thompson et al., 1997). Cela a rendu le code compliqué à maintenir et à développer, car l’interface graphique doit être constamment modifiée et recompilée pour de nouveaux systèmes d’exploitation et environnements de bureau (Windows, Macintosh, VMS, Unix et Linux).

À la fin des années 1990, Clustal W et Clustal X étaient les programmes d’alignement multiple les plus utilisés. Ils étaient capables d’aligner très rapidement des ensembles de données de taille moyenne et étaient faciles à utiliser. Les alignements étaient de qualité suffisante pour ne pas nécessiter d’édition ou d’ajustement manuel très souvent. Cette situation a beaucoup changé avec l’apparition du premier ensemble de tests de référence fait sur mesure pour les programmes d’alignement multiple, BAliBASE (Thompson et al., 1999). Cette apparition a été suivie par celle de T-Coffee, qui était capable de faire des alignements très précis de protéines très divergentes, mais seulement pour de petits ensembles de séquences, étant donné son coût de calcul élevé. Avec l’augmentation de la vitesse de traitement des ordinateurs de bureau, et l’optimisation ultérieure du code de T-Coffee, ce dernier est maintenant pratique pour une utilisation de routine sur des problèmes d’alignement de taille modérée. Plus récemment, sont apparus MAFFT et MUSCLE, qui étaient, au départ, au moins aussi précis que Clustal, en termes de précision d’alignement, mais qui étaient aussi extrêmement rapides et capables d’aligner plusieurs milliers de séquences. Au cours des 4 ou 5 dernières années, ces programmes sont également devenus progressivement de plus en plus précis pour les alignements difficiles. Néanmoins, Clustal W et Clustal X continuent à être très largement utilisés, de plus en plus sur des sites web. Le site Clustal de l’EBI, reçoit littéralement des millions de travaux d’alignement multiple par an.

C’est dans ce contexte que nous avons développé Clustal W 2.0 et Clustal X 2.0. Ces programmes ont été réécrits en C++ avec un modèle objet simple afin de faciliter la maintenance du code et surtout de faciliter la modification voire le remplacement de certains algorithmes d’alignement. Nous avons produit deux nouveaux programmes dont l’aspect et la convivialité sont très similaires à ceux des anciens programmes de la version 1.83, mais qui peuvent maintenant être gérés plus facilement. Nous avons également fait quelques ajustements mineurs aux algorithmes d’alignement. Nous avons inclus un nouveau code pour les arbres guides UPGMA comme alternative aux arbres guides habituels de type Neighbor-Joining. Cela permet d’accélérer l’alignement d’ensembles de données extrêmement volumineux comprenant des dizaines de milliers de séquences. Nous avons également inclus une facilité d’alignement itérative pour augmenter la précision de l’alignement.

Clustal X 2.0 est la nouvelle version de l’outil d’alignement graphique Clustal X. Le Clustal X original a été développé en utilisant la boîte à outils vibrante du NCBI. La boîte à outils vibrante n’est plus prise en charge, ce qui a entraîné des problèmes de compilation de Clustal X sur les nouvelles versions des systèmes d’exploitation. Les sections de l’interface graphique de Clustal X 2.0 ont été entièrement réécrites en utilisant la boîte à outils Qt GUI. Qt est une boîte à outils GUI C++ facile à utiliser et multiplateforme. Le code ne doit être compilé qu’une seule fois sur chacune des plateformes. La boîte à outils Qt offre un aspect et une sensation natifs sur les plateformes Windows, Linux et Mac. Clustal X 2.0 a les mêmes fonctionnalités que Clustal X.

2 NOUVELLES FONCTIONS

Deux nouvelles options ont été incluses dans Clustal W 2.0, pour permettre un alignement plus rapide de très grands ensembles de données et pour augmenter la précision de l’alignement. Les options par défaut de Clustal W et Clustal X 2.0 sont les mêmes que Clustal W 1.83, et donneront les mêmes résultats d’alignement.

Les arbres guides de Clustal ont été calculés en utilisant la méthode Neighbor-Joining (NJ), depuis une dizaine d’années. Dans les premières versions du programme, la méthode UPGMA était utilisée. UPGMA est plus rapide que NJ mais a tendance à regrouper les longues branches lorsque les taux d’évolution sont très inégaux dans les différentes lignées. Les deux algorithmes ont une complexité de O(N2) mais UPGMA est plus rapide pour un ensemble de données donné et la différence devient prononcée avec un très grand N. Sur un PC de bureau standard, il est possible de regrouper 10 000 séquences en moins d’une minute en utilisant UPGMA, alors que NJ prendrait plus d’une heure. Nous avons réimplémenté un algorithme très efficace pour UPGMA qui peut être appelé en utilisant l’option de ligne de commande ‘-clustering=UPGMA’. Il est marginalement moins précis sur le benchmark Balibase, mais sur les grands alignements (par exemple 10 000 séquences de globine), cela est compensé par les économies de temps de traitement (2 h contre 12 h).

L’itération est une méthode rapide et efficace pour affiner les alignements. Un schéma d’itération  » supprimer d’abord « , qui optimise le score de la somme pondérée des paires (WSP), a été inclus dans cette version de Clustal. Au cours de chaque étape d’itération, chaque séquence est retirée de l’alignement à son tour et réalignée. Si le score WSP est réduit, l’alignement résultant est conservé. Le schéma d’itération peut être utilisé pour affiner l’alignement final ou à chaque étape de l’alignement progressif. L’itération pendant l’alignement progressif a tendance à être plus précise, mais elle est aussi beaucoup plus longue car il y a 2N-3 nœuds dans l’arbre guide. L’option de ligne de commande ‘-Iteration=Alignment’ affine l’alignement final, tandis que l’option ‘-Iteration=Tree’ incorpore le schéma dans l’alignement progressif. Le nombre de cycles d’itération est défini via l’option de ligne de commande ‘-numiters’ (par défaut, 3).

ACKNOWLEDGEMENT

Ce travail a été principalement financé par la Science Foundation Ireland.

Conflit d’intérêt : aucun déclaré.

Notes de l’auteur

.