15/06/97
Pour des informations complémentaires,
contacter les chercheurs
L'analyse des séquences génomiques est confrontée à l'accroissement exponentiel des données biologiques (les banques de séquences d'ADN ou de protéines). Malgré des ordinateurs toujours plus puissants, les temps de traitement s'allongent inexorablement. L'équipe API (Architectures Parallèles Intégrées) de l'IRISA (1), à Rennes, a conçu et développé un accélérateur matériel, SAMBA (2), qui, connecté à un ordinateur personnel ou à une station de travail standard, multiplie les performances de ces machines par un facteur 100 pour certains traitements de la biologie moléculaire coûteux en calcul : exploration fine des banques de séquences biologiques, comparaison inter-banque avec les meilleurs algorithmes connus, décryptage et assemblage de grandes molécules d'ADN, etc. L'accélérateur est constitué d'un réseau de 128 processeurs dédiés, encapsulés dans quelques puces de silicium. Avec la technologie actuelle, l'accélérateur peut être mis en oeuvre sur une carte d'extension enfichable dans n'importe quel ordinateur type PC. Une version commerciale de SAMBA est actuellement en cours d'étude.
La comparaison de séquences est un traitement de base en biologie moléculaire. Il a essentiellement pour but de mettre en évidence des ressemblances entre séquences, que ce soit pour repérer des signaux de régulation, analyser des gènes, étudier une phylogénie, construire un alignement multiple, etc.
Ce traitement peut être très long et dépend principalement de trois paramètres : le volume de données à traiter, la puissance de calcul des ordinateurs et les algorithmes de comparaison. Réduire le temps de calcul revient à intervenir sur ces trois paramètres.
La taille des banques de séquences est incompressible et croît exponentiellement (plus de +50 % par an). Dans le même temps, la puissance de calcul des machines informatiques ne cesse d'augmenter, mais à un rythme inférieur à celui des banques. Dans les années futures, la durée des traitements sur ces machines aura donc plutôt tendance à s'allonger.
Le troisième paramètre sur lequel on peut intervenir est l'algorithmique. La complexité des algorithmes de comparaison est quadratique par rapport à la taille des séquences. Aussi, l'implémentation de certains algorithmes s'accompagne d'heuristiques visant à limiter cette complexité. Les méthodes sont extrêmement efficaces pour limiter le temps de calcul mais possèdent l'inconvénient majeur de détériorer, dans certains cas, la qualité des résultats.
Dans le cas présent, la solution retenue pour réduire les temps de calcul, et maintenir une qualité maximale, est basée sur la parallélisation des algorithmes de comparaison sur une architecture matérielle spécialisée. Cette solution supprime les inconvénients liés aux heuristiques et garantit une exécution rapide.
La mise en oeuvre est un accélérateur matériel de faible encombrement qui, connecté à un ordinateur standard, multiplie les performances de la machine par un facteur supérieur à 100. Un prototype, baptisé SAMBA (Systolic Accelerator for Molecular Biological Applications) a été mis au point par Dominique Lavenier, chercheur CNRS, dans l'équipe API de l'IRISA (1) et est fonctionnel depuis la fin de l'année 1995. Le coeur est un réseau linéaire de 128 processeurs spécialisés, mais paramétrables pour couvrir toute la gamme des algorithmes de comparaison usuels. Cette réalisation a demandé l'élaboration d'une puce de silicium qui intègre 4 processeurs. Une puce délivre une puissance crête de 400 MOPS (Million d'opérations par seconde). L'assemblage de 32 puces (128 processeurs) procure alors une puissance de 12 800 MOPS.
Le but de SAMBA est d'équiper, à coût réduit, les laboratoires qui manipulent des séquences biologiques. Une étude de faisabilité a montré qu'une nouvelle puce réalisée en une technologie plus agressive (CMOS 0,5 micron, par exemple) contiendrait maintenant 16 processeurs, fonctionnant 2 fois plus vite. Ainsi, une carte d'extension standard (au format PCI, par exemple) pourrait aisément contenir 4 puces qui délivreraient la même puissance de calcul que le prototype. D'autre part, une étude de marché est en cours. Elle devrait à la fois déterminer les configurations intéressantes pour les laboratoires, préciser la gamme d'applications, quantifier le marché, etc.
Les performances de cet accélérateur ont été appréciées sur diverses applications. La première est l'exploration des banques de séquences. Cette opération recherche toutes les séquences (d'une banque) qui présentent des ressemblances avec une séquence particulière. Il existe plusieurs algorithmes pour détecter des zones de ressemblances, et suivant leur complexité et la taille de la séquence test, l'accélération par rapport à une station de travail performante (une Dec Alpha à 150 MHz) varie de 30 (1 minute contre 1/2 heure) à 180 (1 minute contre 3 heures). Dans tous les cas, la qualité des résultats est excellente.
D'autres applications, encore plus coûteuses en terme de volume de calculs, sont possibles. Par exemple, une étude menée en collaboration avec une équipe de biologistes pour rechercher des « parents » à des séquences « orphelines » du génome de la levure met bien en évidence l'apport d'un tel accélérateur. D'un point de vue purement informatique, il s'agissait de comparer 814 séquences biologiques contre une banque de 43 000 éléments, et ce plusieurs fois avec différents paramètres en utilisant un algorithme très coûteux. Le temps de traitement sur une station Dec Alpha (150 MHz) a été estimé à plus de 2 000 heures (soit trois mois de calcul intensif sans interruption). Avec le prototype SAMBA l'ensemble du calcul a été réalisé en 12 heures.
Référence :
- Guerdoux-Jamet P., Lavenier D., Wagner C., Quinton P., " Design and implementation of a parallel architecture for biological sequence comparison ", EURO-PAR'96 parallel processing, LNCS 1123 (1996), pp. 11-24.
(1) IRISA : Institut de recherches en informatique et systèmes aléatoires (CNRS-INRIA-Université Rennes 1-INSA Rennes).
(2) Le Prix Seymour Cray France " Algorithmes, architecture ou micro-électronique " a été obtenu en 1996 par Dominique LAVENIER de l'équipe API de l'IRISA pour ses travaux " Accélérateur parallèle pour l'analyse des séquences génomiques ".