Brevet FR2776091A1 — publié le 19990917

Procédé et dispositif de traitement des résultats d'une comparaison de deux séquences d'éléments de données, réseau systolique, processeur de réseau systolique correspondants. Le domaine de l'invention est celui de la comparaison de séquences d'éléments de données. Plus précisément, I'invention concerne notamment la détermination du meilleur alignement local entre deux séquences. L'invention trouve des applications dans de nombreux domaines, et en particulier dans le domaine de la biologie moléculaire. On sait que cette discipline, en pleine expansion, produit une quantité de données (les séquences génétiques) qu'il est impossible de traiter manuellement, et qui croît exponentiellement. On estime en effet que la taille des banques de données dans lesquelles sont stockées les séquences est multipliée par 2 chaque année. Les traitements associés à ces données sont multiples : la reconstruction de cosmides à partir des informations fournies par les séquenceurs automatiques (ou "shotgun" en anglais), l'exploration des banques de séquences, la construction de bases de données génomiques, la phylogénie (recherche d'ancêtre commun)... I1 existe également de nombreuses autres applications dans d'autres domaines techniques, tels que le traitement de texte, la reconnaissance d'images ou de son,... Les algorithmes de comparaison étant coûteux en calculs, et le volume des séquences s'accroissant de manière exponentielle, les temps de traitement deviennent de plus en plus importants, malgré l'évolution continue de la puissance des ordinateurs. Deux grandes méthodes existent pour réduire fortement et à faible coût les temps de calcul: I'inclusion d'heuristiques dans les algorithmes de comparaison ou l'intégration des algorithmes sur silicium. L'inconvénient majeur des heuristiques est de détériorer la qualité des résultats. Cela n'est pas le cas, en revanche, des accélérateurs matériels. De tels accélérateurs matériels sont généralement basés sur des réseaux systoliques. Les documents suivants présentent trois exemples de réseaux systoliques développés pour la comparaison des séquences génétiques: - "A Systolic Array for Rapid String Comparison " par R.J. Lipton D.Lopresti (conference on Very Large Scale Integration, 1985); - "Biological Information Signal Processor" par E. Chow, T. Hunkapiller, J. Peterson, M.S. Waterman (int. Conf. on Application Specific Array Processors, 1991); - "BioSCAN : A Network Sharable Computational Resource for Shearing Biosequence Database" R.K. Singh, D.L. Hoffman, S.G. Tell, C.T. White, (CABIO, vol 12, n"3, 1996). Le principe général consiste à mettre en série des processeurs (par exemple 128) fonctionnant en pipeline et à la même cadence. On introduit une première séquence dans le réseau, puis on fait défiler la seconde séquence. On récupère en sortie le résultat de la comparaison, c'est-à-dire la valeur du meilleur alignement local. En revanche, dans un réseau systolique classique, on ne connaît pas l'emplacement de ce meilleur alignement local, car on ne connaît pas le processeur qui l'a identifié. En effet, on a accès uniquement aux deux extrémités du réseau. Pour pallier ce problème, il a été proposé d'affecter une sortie spécifique à chaque processeur. Un traitement en parallèle est effectué pour chacune de ces sorties. Cette technique présente clairement de nombreux inconvénients. Elle est lourde et complexe: elle suppose une augmentation de la complexité de chaque processeur, et un traitement important de très nombreuses sortie s. Elle est de plus peu évolutive: le changement du nombre de processeurs impose de modifier le traitement des sorties. En d'autres termes, les structures de ce type induisent plus de calculs pour traiter les résultats, exigent une surface de silicium importante, et sont figées. L'invention a notamment pour objectif de pallier ces différents inconvénients de l'état de l'art. Plus précisément, un premier objectif de la présente invention est de fournir un procédé et des moyens de traitement correspondants, permettant de simplifier le traitement des résultats de comparaison de deux séquences d'éléments de données. Un autre objectif de l'invention est de fournir un tel procédé et de tels moyens permettant d'être plus rapides et plus efficaces que les techniques connues. En d'autres termes, un objectif de l'invention est de fournir un tel procédé et de tels moyens permettant d'accélérer le traitement des résultats de la comparaison de séquences de données, et donc d'obtenir un gain conséquent en temps d'exécution, en particulier dans le cas de banques de données de taille très importante. Un autre objectif de l'invention est de fournir un tel procédé permettant de réduire la surface de silicium nécessaire. Encore un objectif de l'invention est de fournir un tel procédé et de tels moyens permettant d'optimiser les coûts de fabrication, de mise en oeuvre et d'adaptabilité de moyens de comparaison. Un autre objectif de l'invention est de fournir un tel procédé et de tels moyens permettant d'adapter aisément le nombre de processeurs mis en oeuvre. Plus généralement, un objectif de l'invention est de fournir un tel procédé et de tels moyens permettant une meilleure souplesse et une plus grande adaptabilité. Ces différents objectifs, ainsi que d'autres qui apparaîtront par la suite, sont atteints selon l'invention à l'aide d'un procédé de traitement des résultats d'une comparaison de deux séquences d'éléments de données, mettant en oeuvre un réseau systolique linéaire de processeurs, ledit réseau systolique comprenant au moins deux processeurs effectuant chacun, à chaque instant de traitement, une comparaison entre deux éléments desdites séquences, et produisant une information représentative de ladite comparaison, dite score partiel, chacun desdits processeurs transmettant au processeur suivant une information dite meilleur score partiel, résultant de la comparaison entre le score partiel courant et le meilleur score partiel reçu du processeur précédent, procédé selon lequel chacun desdits processeurs transmet également au processeur suivant dans ledit réseau systolique une information de localisation, permettant d'identifier le processeur qui a détecté ledit meilleur score partiel. Le principe général de l'invention est donc de faire propager dans la chaîne de processeurs au moins une information concernant l'identification du processeur ayant décelé le meilleur score partiel, c'est-à-dire le meilleur alignement local. Le dernier processeur connaît ainsi le processeur qui a détecté cet alignement, et peut donc aisément le retrouver. n n'est alors plus nécessaire d'analyser en parallèle des sorties spécifiques de chaque processeur. L'invention propose ainsi une technique qui permet de simplifier la récupération des résultats de comparaison. De plus, du fait que l'exploitation des résultats est gérée par des moyens supplémentaires indépendants, la taille du réseau de processeurs peut être modifiée sans adaptation complexe. De tels moyens supplémentaires forment des moyens d'analyse des informations transmises par le dernier processeur du réseau, permettant la reconstitution du meilleur alignement local. Fol est clair que ces moyens supplémentaires indépendants peuvent être compris dans un processeur supplémentaire connecté au dernier processeur du réseau systolique ou ils peuvent encore être intégrés dans le dernier processeur. Dans un mode de réalisation préférentiel de l'invention, ladite information de localisation est un identifiant dudit processeur ayant détecté ledit meilleur score partiel. Une telle caractéristique de localisation permet de retrouver aisément le meilleur score partiel. Avantageusement, on mesure le temps de propagation dudit meilleur score partiel jusqu'au dernier processeur. Une telle caractéristique d'information sur le temps de propagation permet également de localiser le processeur ayant détecté le meilleur alignement local. Avantageusement, ledit traitement étant représenté sous la forme d'une matrice formée de lignes et de colonnes, l'emplacement du meilleur alignement local dans ladite matrice est déterminé par: - une indication de colonne, correspondant au processeur qui a repéré ledit meilleur alignement local, et - une indication de ligne, déterminée par une analyse du temps de propagation du score partiel associé audit meilleur alignement local. En d'autres termes, chaque processeur compare le score partiel qu'il a obtenu avec ceux déjà obtenus par ces prédécesseurs, et, s'il est supérieur, le transmet, en précisant que c'est lui qui a identifié le score partiel maximum. Dans un mode de réalisation préférentiel de l'invention, le dernier processeur dudit réseau systolique délivre à une unité de traitement externe ledit meilleur score partiel et ladite information de localisation pour un lot de séquences d'éléments de données comparées à une séquence de référence, et ladite unité de traitement externe détermine le plus élevé desdits meilleurs scores partiels, dit score global, et la position dans la séquence de référence de l'alignement local correspondant audit score global. I1 est clair que la séquence de référence peut correspondre à une séquence d'éléments de données d'interrogation. Ainsi, on cherche à retrouver dans une base de données comprenant une liste de séquences d'éléments de données, qui peut être conséquente, celle qui comporte un maximum d'éléments de données proches ou communs. Ainsi, le score global est donc déterminé via le dernier processeur par une unité de traitement externe comprenant les moyens supplémentaires indépendants, et non par un élément indépendant comparant les sorties de tous les processeurs. De façon avantageuse, ledit procédé comprend une étape de reconstitution de l'alignement local correspondant audit score global, à partir de ladite information de localisation. Préférentiellement, ladite unité de traitement externe réitère le calcul effectué par ledit réseau systolique pour le meilleur alignement local identifié. Cette opération peut être effectuée par logiciel, sur un ordinateur hôte. Le fait qu'un tel traitement soit relativement long n'a que peu d'importance, car il est rare. L'invention permet d'optimiser les opérations systématiques, par une simplification des comparaisons de séquences. Lorsqu'un cas favorable est détecté (classiquement un sur plusieurs millions), un traitement spécifique long est acceptable. L'invention concerne également un réseau systolique de processeurs mettant en oeuvre ce procédé. Un tel réseau systolique prévoit que chacun desdits processeurs comprend des moyens de transmission au processeur suivant dans ledit réseau systolique d'une information de localisation, permettant d'identifier le processeur qui a détecté ledit meilleur score partiel. L'invention porte également sur les processeurs mis en oeuvre dans un tel réseau systolique. Un tel processeur comprend également des moyens de transmission à un processeur suivant dans ledit réseau systolique d'une information de localisation, permettant d'identifier le processeur qui a détecté ledit meilleur score partiel. L'invention concerne encore un dispositif de traitement des résultats de comparaison de deux séquences d'éléments de données. Un tel dispositif reçoit du dernier processeur dudit réseau systolique: - une première information, dite meilleur score partiel, permettant de déterminer un score global, une information de localisation de l'alignement local correspondant audit meilleur score partiel permettant d'identifier le processeur qui a détecté ledit meilleur score partiel, de façon à déterminer la position du meilleur alignement local correspondant audit score global; et comprend: des moyens de détermination d'un score global à partir d'au moins un meilleur score partiel, permettant de déterminer le meilleur desdits scores partiels pour retrouver ledit meilleur alignement local desdites séquences d'éléments de données traitées; - des moyens de détermination de la position de l'alignement local correspondant audit score global permettant d'identifier le processeur qui a détecté ledit score global. Ainsi, ce dispositif peut délivrer les informations concernant le numéro de la colonne et le numéro de la ligne correspondant aux coordonnées de l'emplacement du meilleur alignement local. Préférentiellement, lesdits moyens de détermination dudit score global comprennent: - des moyens de comparaison permettant de calculer ledit score global, et alimentant - des premiers moyens de multiplexage permettant d'initialiser la valeur dudit score global, à chaque premier élément de donnée d'une nouvelle séquence d'éléments de données, et alimentant - des premiers moyens de mémorisation permettant de sauvegarder le dernier score global calculé et rebouclant sur lesdits moyens de comparaison. L'invention peut notamment s'appliquer à au moins l'un des domaines appartenant au groupe comprenant: - la comparaison de séquences génétiques; - la reconnaissance de la parole; - la reconnaissance de textes; - la recherche de texte; - la correction orthographique; - la recherche d'empreintes; - la comparaison d'images. D'autres caractéristiques et avantages de l'invention apparaîtront à la lecture de la description suivante d'un mode de réalisation préférentiel de l'invention, donné à titre de simple exemple illustratif et non limitatif, et des dessins annexés, dans lesquels: - la figure 1 présente un schéma simplifié d'un réseau systolique mis en oeuvre par le procédé de comparaison de deux séquences d'éléments de données selon l'invention; - la figure 2 présente un organigramme simplifié d'un mode de réalisation particulier du procédé selon l'invention; - la figure 3 présente un schéma simplifié d'un réseau systolique linéaire de processeurs mis en oeuvre par le procédé de la figure 2; - la figure 4 présente un schéma simplifié d'un processeur utilisé par le réseau systolique linéaire de processeurs de la figure 3; - la figure 5 présente un mode de réalisation détaillé d'un processeur de la figure 4; - la figure 6 présente un mode de réalisation d'une unité de traitement externe selon l'invention. I - La machine "SAMBA": 1. Introduction L'invention s'applique à tout type de comparaison de séquences de données. Le mode préférentiel décrit par la suite concerne la machine dénommée "SAMBA" ("Systolic Accelerator for Molecular Biological Applications" en anglais, pour accélérateur systolique pour applications en biologie moléculaire). Cette machine est un accélérateur matériel destiné à accélérer les algorithmes impliqués dans la comparaison de séquences de données biologiques. Ainsi, les calculs qui exigent plusieurs heures sur des stations de travail classiques peuvent être réalisées en quelques dizaines de secondes sur la machine "SAMBA". La machine "SAMBA" met en oeuvre un algorithme de Smith et Waterman. Le principe de cet algorithme est rappelé en annexe I. 2. Parallélisation La machine "SAMBA" utilise l'architecture illustrée en figure 1. Cette machine comprend une série de processeurs identiques, disposés linéairement, qui réalisent chacun une étape du calcul de la matrice décrite plus bas. Le caractère présenté se déplace de la gauche vers la droite. La comparaison parallèle de deux séquences s'effectue donc selon les étapes successives suivantes: 1. le tableau mémorise une séquence (appelée séquence d'interrogation) à la vitesse d'un caractère par processeur; 2. l'autre séquence est introduite par la gauche du tableau et progresse à chaque cycle systolique vers la droite à travers ce tableau; 3. le résultat est disponible sur le processeur le plus à droite lorsque le dernier caractère de la séquence qui circule est sorti. Ainsi, si 1q représente la longueur de la séquence d'interrogation et lb est la longueur d'une séquence provenant d'une banque, le calcul est réalisé en (lq+ 1b -1) étapes systoliques. Un tel calcul entraîne une accélération S1 par rapport aux machines dites 1q * 1b séquentielles donnée par la formule suivante : S1 = 1q + 1b - 1 Dans le cas de la comparaison d'une séquence à une banque de séquences, la vitesse peut être accélérée en mettant bout à bout les séquences devant traverser le réseau: quand le dernier caractère d'une séquence entre dans le réseau, le premier caractère de la séquence suivante peut être introduit dans le prochain cycle systolique. Pour k séquences, (lq + k * lb - 1) étapes systoliques sont nécessaires. L'accélération (Sk) s'exprime alors parlaformulesuivante: K * 1q * 1b Sk = . 1q + K * 1b - 1 Lors du balayage de la base de données, le nombre k de séquences est généralement élevé et l'accélération Sk peut être approchée par 1q (longueur de la séquence d'interrogation). Ce dernier cas représente un domaine d'application où la machine "SAMBA" excelle. 3. Récupération des données Dans un réseau systolique, seuls les processeurs de bord communiquent avec le monde extérieur. Les résultats doivent donc nécessairement progresser jusqu'au bord pour pouvoir sortir. Les opérations consistent à calculer une matrice dans laquelle les valeurs intéressantes peuvent apparaître n'importe où à l'intérieur de la matrice. Selon l'invention, la transmission des valeurs aux extrémités du réseau nécessite des calculs additionnels. Selon l'invention, I'algorithme de la machine "SAMBA" est complété par la gestion de deux termes: - MaxLigne(i, j), correspondant au score partiel maximum de la matrice H(i, j) calculé sur la iième ligne de la matrice H; IdxCol(i, j), un indice spécifiant la colonne où MaxLigne est modifié. Ces deux termes sont calculés en utilisant les deux équations récurrentes suivantes: - MaxLigne(i,j) = Max{MaxLigne(i, j-1) ; ; H(i, j)); (4) - Si (MaxLigne(i,j-l) > H(i, j)) alors IdxCol(i, j) = IdxCol(i,j-1) sinon IdxCol(i, j)= j. Soit N la taille du réseau et i le nombre d'étapes systoliques, à chaque étape systolique, le processeur le plus à droite du réseau délivre le MaxLigne(i,N) et IdxCol(i,N). Ces informations permettent la localisation directe des coordonnées des maxima locaux de la matrice H. 4. Construction Comme mentionné plus haut, la machine "SAMBA" comprend une station de travail, une interface et un réseau systolique connu. La station de travail est par exemple une station DEC (marque déposée) modèle 5000, comprenant une unité processeur de commande de type R3000A RISC. L'interface hôte/réseau systolique met en oeuvre des mémoires actives programmables (ou PAM). Cette mémoire active programmable est connectée, via deux liaisons (entrée et sortie) au processeur hôte. Une troisième connexion permet à un flux de bits de configuration d'être envoyés sur la voie descendante dans la mémoire active programmable. La machine "SAMBA" utilise le mode mixte, selon lequel la mémoire active programmable est commandée par l'ordinateur hôte et connectée à quelques matériels spécifiques : les liaisons externes sont connectées au réseau systolique. Le rôle majeur de la mémoire active programmable est d'alimenter rapidement le réseau, et de filtrer au vol la sortie de donnée par le réseau. Le réseau systolique est un réseau linéaire comprenant 32 circuits intégrés distribués sur deux circuits imprimés. Chaque circuit intégré (conçu dans la technologie CMOS 1 micron) comprend 4 processeurs, menant à un réseau systolique de 128 processeurs. Chaque processeur calcule l'équation de récurrence (1), ainsi que les deux équations auxiliaires utilisées pour localiser les résultats (4). Une mesure de performance utilisée traditionnellement est le nombre de millions d'opérations par cellule par seconde (ou " MCOPS " pour "Million Cell Operation Per Second" en anglais). Cela représente le calcul complet d'un score de matrice H(i,j), incluant toutes les comparaisons, additions et calculs de maxima qui donnent une valeur à ce noeud. La machine "SAMBA" réalise ceci en une étape systolique (soit 100 ns) menant à une performance Pp, s'exprimant par le nombre de processeurs multiplié par la fréquence: PP=Nbproc * freq soit, avec Nbproc = 128 et freq = 107, Pp = 1280 MCOPS. En outre, un processeur contient une mémoire statique interne de 32 mots pour mémoriser les coûts de substitution. II- Principe de l'invention 1- Propagation d'une ou des information(s) d'identification et des résultats partiels Chaque processeur d'un réseau systolique de processeurs permet de détecter la présence d'un élément de donnée similaire ou commun aux deux séquences comparées et de calculer le score partiel du meilleur alignement local. Le résultat établi par chaque processeur est comparé avec le résultat précédent et remplace celui-ci s'il est meilleur, c'est-à-dire par exemple plus grand. Ainsi, le meilleur résultat (meilleur score partiel) se propage dans le réseau. Parallèlement, et selon la caractéristique principale de l'invention, se propage des informations d'identification du processeur ayant repéré ce meilleur résultat. 2. Calcul par l'unité de traitement externe L'unité de traitement externe comprend des moyens supplémentaires indépendants de détermination d'un score global pour une pluralité de séquences comparées. Ces moyens supplémentaires peuvent être externes au réseau systolique ou intégrés dans le dernier processeur du réseau systolique. Ils déterminent le score global (meilleur des meilleurs scores partiels) par la comparaison des différents meilleurs scores partiels du dernier processeur délivre à chaque nouveau cycle. Le score global correspond donc au meilleur alignement local. Parallèlement, I'unité de traitement externe détermine l'emplacement de ce meilleur alignement local. Elle mémorise pour cela également l'indication de la colonne correspondant au processeur ayant décelé le score global, propagée selon l'invention. Pour repérer de façon complète l'emplacement du score global dans la matrice (tableau I), il reste à déterminer la ligne sur laquelle ce score global se situe. A cette fin, on analyse le temps de propagation du score global. En effet, le numéro de la ligne du score global correspond au numéro du cycle systolique de la première apparition du score partiel associé diminué de la taille de la séquence comparée. Le score global et l'emplacement de ce dernier sont ainsi entièrement déterminés et disponibles en sortie de l'unité de traitement externe. 3. Recalcul du meilleur alignement local Connaissant cet emplacement, un ordinateur centralisé peut reconstituer le meilleur alignement local. Cette reconstitution peut être effectuée à partir d'un cheminement inverse en récupérant élément de donnée par élément de donnée. Ainsi, la reconstitution se réalise en partant de la fin de la sous-séquence la plus grande grâce à ses coordonnées puis en récupérant les éléments de données jusqu'à la tête de cette sous-séquence. 4. Remarques Les étapes des paragraphes 2 et 3 ci-dessus sont facultatives dans certaines applications. En effet, certaines applications ne nécessitent pas la détermination de l'emplacement du score global et/ou de la reconstitution de l'alignement local. Dans certains cas, la simple connaissance du score global et/ou d'une information permettant d'identifier le processeur l'ayant détecté peut être suffisant. Selon une caractéristique optionnelle, on peut prévoir la possibilité d'insérer, entre deux éléments de données, des "trous" correspondant à des cases vides (retraits des éléments de données) dans la séquence d'éléments de données relative à la base de données de recherche. Ces trous sont en conséquence introduits en regard des éléments de données différents. Cela permet de faire coïncider deux sous-séquences identiques ou similaires, de manière à créer le meilleur alignement local possible. m- lllustration du fonctionnement Afin de mieux préciser le principe de l'invention, on donne ci-dessous un exemple simplifié, purement illustratif. On se propose de comparer par exemple les deux séquences d'éléments de données suivantes ACGTTCG et TCGTAGA dont on cherche à trouver le meilleur alignement local. fl est à noter que l'on ne considère pas ici les trous insérés dans les séquences d'éléments de données. Ces deux séquences peuvent être placées dans une matrice (tableau I). La séquence d'éléments de données d'interrogation ACGTTCG est par exemple insérée sur la première ligne du tableau I suivant et la séquence d'éléments de données extraite d'une base de données à comparer dans la première colonne. A C G T T C G T 0 0 0 2 2 0 0 C 0 2 0 0 1 4 0 G 0 0 4 0 0 0 6 T 0 0 0 6 2 0 0 A 2 0 0 0 5 I 1 0 G 0 1 2 0 0 4 2 A 2 0 0 1 0 0 3 Tableau I La matrice est remplie de scores partiels de la façon suivante : à chaque intersection, on ajoute la valeur 2 à la valeur précédente dans la diagonale si les éléments de données contenus dans la colonne et la ligne correspondantes sont identiques, et on retranche une seule unité dans le cas contraire. Dans tout autre cas, la valeur du score partiel est fixée au minimum à 0. Un exemple plus réaliste est présenté en annexe 1. L'opération suivante consiste à repérer les maxima locaux. Dans l'exemple représenté, ces maxima locaux correspondent à la valeur 6, que l'on trouve en deux positions distinctes (au croisement de la ligne 3 et de la colonne 8, et au croisement de la ligne 4 et de la colonne 4). Dans la pratique, on transforme une matrice N*N en un réseau linéaire systolique à N processeurs, dans lequel la seconde séquence est introduite progressivement. A chaque processeur est affecté un élément de donnée de la séquence d'éléments de données d'interrogation. A un instant donné, on ne traite donc qu'une diagonale de la matrice sur la ligne de processeurs. On insère donc les éléments de données de la seconde séquence dans l'ordre (du premier élément de donnée au dernier). Cette insertion se fait au rythme du cycle systolique du réseau et met en oeuvre une propagation des éléments de données de la seconde séquence d'éléments de données à travers chaque processeur du réseau systolique linéaire. Le tableau II suivant illustre les situations obtenues au cours des différents cycles systoliques de propagation lors d'un passage d'une séquence d'éléments de données dans un réseau systolique linéaire selon l'invention. Ce tableau est construit à partir des deux exemples de séquences d'éléments de données précédentes ACGTTCG et TCGTAGA. A C G T T C G Score Cycle global 1 T 0 ; 0 ; 1 - 2 C 0 ; 0 ; 1 T 0 ; 0; 1 n 3 G 0 ; 0 ; 1 C 2 ; 2 ; 2 T0;0; 1 4 T 0 ; 0 ; 1 G 0 ; 0 ; 1 C 0 ; 2 ; 2 T 2 ; 2 ; 4 - - 5 A 2 ; 2 ; 1 T 0 ; 0 ; 1 G 4 ; 4 ; 3 C 0 ; 2 ; 2 T 2 ; 2 ; 4 - 6 G 0 ; 2 ; 1 A 0 ; 2 ; 1 T 0 ; 0 ; 1 G 0 ; 4 ; 3 C 1 ; 2 ; 2 T 0 ; 2 ; 4 - 7 A 2 ; 2 ; 1 G 1 ; 2 ; 1 A 0 ; 2 ; 1 T 6 ; 6 ; 4 G 0 ; 4 ; 3 C 4 ; 4 ; 6 T 0 ; 2 ; 4 T 2 ; 4 (8) n 8 A0;2; 1 G 2 ; 2 ; 3 A0;2;1 T2;6;4 G de la valeur 2 le score partiel calculé deux cycles systoliques auparavant sur le processeur précédent, - sinon, c'est-à-dire lorsque les éléments de données sont différents, le processeur concerné affecte soit la valeur 0 au score partiel courant, soit un score partiel courant diminué d'une valeur d'une unité par rapport à celui calculé deux cycles systoliques auparavant sur le processeur précédent (le score partiel courant affecté ne peut être inférieur à zéro). Ainsi, lors du premier cycle systolique, la valeur T est insérée dans le premier processeur de la chaîne, qui compare l'élément de donnée qui lui est associé (A) à l'élément de donnée T. Le score partiel courant est donc 0. C'est également le meilleur score partiel. Il a bien été trouvé par le premier processeur. Ces deux informations sont transmises au processeur suivant (colonne n02, cycle ne2). Ensuite, au cycle systolique suivant, l'élément de donnée qui vient d'être traité, est transmis au processeur suivant (colonne n02), tandis que l'élément de donnée suivant (C) est traité par le premier processeur courant (colonne n 1), et ainsi de suite... Le processus se termine lorsque tous les éléments de données d'une même séquence à comparer avec la séquence d'interrogation ont été traités par la chaîne de processeurs. Au cycle nO 2, il n'y a aucune concordance de détectée. Au cycle nO 3, en revanche, le deuxième processeur détecte la valeur "C" dans les deux séquences. Le score partiel courant devient alors 2(=0 + 2). C'est également, bien sûr, le score partiel maximum correspondant au meilleur score partiel, puisque ce dernier valait 0. L'indice 2 est transmis pour indiquer que ce meilleur score partiel courant a été repéré par le 2e processeur et est associé à l'élément de donnée C. Au cycle nO 4, le troisième processeur ne détecte pas de concordance (G*C). I1 affecte la valeur 0 au score partiel courant. Le meilleur score partiel reste bien sûr égal à 2. Le quatrième processeur détecte une concordance (T=T), et effectue donc les mêmes opérations que le deuxième cycle nO 3. Au cycle nO 5, le troisième processeur obtient un résultat de comparaison positif (G=G). n s'agit du deuxième élément d'une sous-séquence commune (CG). Le score partiel courant (2, processeur n03, cycle n"3) est donc augmenté de la valeur 2 (2 + 2 = 4). 11 devient le meilleur score partiel courant. A nouveau, au cycle nO 7, on détecte une égalité (T=T) dans le quatrième processeur. On a identifié une sous-séquence de 3 éléments (CGT). Le meilleur score partiel vaut alors 6 (=4 + 2), et l'indice du processeur ayant identifié cette sous-séquence est 4. Une situation similaire se retrouve aux cycles 5 à 9, dans les processeurs 5 à 7 on repère la sous-séquence commune (TCG). L'unité de traitement externe (cf dernière colonne du tableau II) détermine donc successivement les informations suivantes: - cycle 8: la sous-séquence la plus longue vaut 2. Elle a été identifiée par le 4e processeur; - cycle 9: la sous-séquence la plus longue vaut 4. Elle a été identifiée par le 6e processeur; - cycle 10 et suivants: la sous-séquence la plus longue vaut 6. Elle a été identifiée par le 7e processeur. L'unité de traitement externe permet de repérer complètement la position de la sous-séquence dans la matrice (tableau I). Pour cela, elle mémorise le numéro du cycle ayant produit le score global (entre parenthèses dans le tableau II, dernière colonne). L'unité de traitement externe conserve donc le meilleur de tous les meilleurs scores partiels (6), qui est reconnu comme le score global, à la fin de la comparaison. I1 est à noter que les doublons (deux scores meilleurs partiels identiques) ne peuvent pas être repérés directement. Selon les besoins, on peut décider de conserver soit le dernier meilleur score partiel calculé, soit le premier meilleur score partiel calculé. Dans l'exemple illustré ci-dessus, on retient le premier meilleur score partiel rencontré au cours de la comparaison en tant que score global. fi est bien sûr possible d'adapter le processus de façon que l'on repère le dernier meilleur score partiel. Comme les séquences à comparer peuvent se visualiser sous la forme d'une matrice (voir tableau I), l'emplacement du meilleur alignement local dans la matrice est déterminé par une indication de colonne, correspondant au processeur qui a repéré le meilleur alignement local et une indication de ligne déterminée par une analyse du temps de propagation du score partiel associé au meilleur alignement local. La colonne correspond au numéro du processeur qui a repéré le meilleur alignement local ainsi qu'une indication de la ligne correspondante. L'indication de la ligne correspondante est déterminée par une analyse du temps de propagation du meilleur score partiel correspondant jusqu'au dernier processeur. Cette analyse peut par exemple reposer sur le calcul de la formule suivante donnant la ligne sur laquelle on peut retrouver le meilleur score partiel: ligne = cycle systolique - taille de la séquence comparée. Dans cette formule, le numéro de la ligne repérant le meilleur score partiel est dans notre exemple celui du tableau I, le numéro du cycle systolique est celui du tableau II et la taille de la séquence comparée est de 7. Soit pour l'exemple G(6 ; 7), le numéro de la ligne du meilleur score partiel est égal à 3 (cycle systolique = 10 ; taille de la séquence comparée = 7). Ainsi, on connaît les coordonnées repérant le meilleur score partiel: - colonne numéro 7; - ligne numéro 3. IV- Procédé de l'invention Après avoir exposé un exemple de fonctionnement de l'invention, on présente maintenant, le procédé général de l'invention, sous la forme d'un organigramme simplifié, en relation avec la figure 2. Le procédé commence classiquement par une étape d'initialisation 21, pendant laquelle on charge dans les processeurs du réseau systolique les différentes valeurs de la séquence d'origine à comparer. Les différents compteurs, moyens de multiplexage et moyens de mémorisation utilisés sont également initialisés aux valeurs de départ adéquates. Chaque processeur du réseau systolique effectue ensuite, à chaque cycle, l'ensemble des opérations 22 décrites ci-dessous. On effectue tout d'abord la comparaison 221 de l'élément de donnée de la séquence d'origine mémorisée par le processeur avec l'élément de donnée qu'il vient de recevoir. Si le résultat de cette comparaison est négatif, c'est-à-dire lorsque les éléments de données respectifs sont différents, on passe directement à l'étape suivante (226). Dans le cas contraire, on modifie (222) ce score partiel courant par exemple en augmentant sa valeur de 2 (par exemple) par rapport à celle du processeur précédent au cycle systolique précédent. On compare (223) ensuite le score partiel courant avec le meilleur score partiel, transmis par le processeur précédent. Si le score partiel courant est inférieur au meilleur score partiel, ce dernier reste inchangé et on passe à l'étape suivante 226 de transmission du meilleur score partiel et du numéro du processeur correspondant. Dans le cas contraire, en revanche, on met à jour (224) le meilleur score partiel en lui affectant pour valeur le score partiel courant. Dans ce dernier cas, on met également à jour (225) le numéro du processeur (information de localisation) ayant identifié le nouveau meilleur score partiel. Selon l'invention, le meilleur score partiel et le numéro du processeur identificateur correspondant sont ensuite transmis (226) au processeur suivant dans le réseau systolique. Le numéro du processeur identificateur est un identifiant du processeur ayant détecté le meilleur alignement local. Le dernier processeur du réseau systolique délivre à une unité de traitement externe le meilleur score partiel et l'information de localisation pour un lot de séquences d'éléments de données comparées à une séquence de référence (ou séquence d'interrogation). Cette unité de traitement remplit selon l'invention les fonctions supplémentaires 23 suivants. Elle détermine le plus élevé des meilleurs scores partiels, c'est-à-dire le score global, et la position dans la séquence de référence de l'alignement local correspondant au score global. Ainsi, si elle reçoit un nouveau meilleur score partiel supérieur au dernier score global (231) mémorisé, elle met à jour (232) le score global. De plus, dans ce dernier cas, elle met à jour (233) le numéro du processeur ayant identifié le score global. Par ailleurs, on mesure (234) le temps de propagation. En d'autres termes, on détermine le numéro du cycle systolique de traitement correspondant lors duquel ce nouveau score global est apparu. n est déterminé à partir d'une mesure du temps de propagation du meilleur score partiel associé au score global jusqu'au dernier processeur. Dans le cas contraire, c'est-à-dire lorsque le nouveau meilleur score partiel est inférieur au dernier score global, on passe à l'étape suivante 24 de calcul de la position du score global. Lorsque la comparaison des deux séquences est terminée, l'unité de traitement externe peut (si cela est nécessaire) recalculer (24) la position du score global identifié. En effet, la position du score global identifié correspond aux coordonnées du meilleur alignement local associé à la séquence d'éléments de données d'interrogation et peut être requise pour une nouvelle utilisation de ce meilleur alignement local. Connaissant la position de ce score global, il est possible, par exemple, par logiciel, de reconstituer (25) l'alignement local correspondant à ce score global. V- Structure du réseau systolique linéaire de processeurs et des processeurs le constituant 1. Principe L'invention est mise en oeuvre sur un réseau systolique linéaire de processeurs (par exemple 128). Le schéma simplifié de la figure 3 présente un tel réseau systolique linéaire de processeurs. Ce réseau systolique linéaire de processeurs comprend: un premier processeur 31, recevant la séquence d'éléments de données à comparer avec une séquence d'origine; - une série d'au moins un processeur 32, 33 (127 dans l'exemple). De façon classique, chaque processeur délivre au suivant la valeur à comparer 311, 321. Selon l'invention, chaque processeur transmet au processeur suivant dans le réseau systolique le meilleur score partiel 312, 322, repérant le meilleur alignement local associé, ainsi qu'une information de localisation permettant d'identifier le processeur ayant détecté le meilleur alignement local. Cette information de localisation correspond au numéro du processeur 313, 323 ayant trouvé ce meilleur score partiel. Une telle transmission s'effectue au rythme des cycles systoliques. Tous les processeurs 31, 32 et 33 sont donc identiques. Le dernier processeur 33 du réseau systolique est connecté à une unité de traitement externe 34. Cette unité de traitement externe 34 reçoit également la valeur à comparer 331, le meilleur score partiel 332 et le numéro du processeur 333 ayant détecté le meilleur alignement local. L'unité de traitement externe 34 délivre également certaines données, à savoir, la valeur comparée 341 le score global 342 et le numéro du processeur 343 ayant détecté le meilleur alignement local. Ce numéro 343 du processeur correspond à un indice de la colonne ayant détecté le meilleur alignement local. En outre, elle dispose de fonctions supplémentaires. Elle mémorise de plus le cycle ayant délivré le meilleur score partiel. Elle fournit par conséquent une mesure 344 du temps de propagation du meilleur score partiel associé à travers le réseau systolique. Cette mesure 344 correspond à un indice de la ligne repérant le meilleur alignement local. Le réseau systolique linéaire est connecté via l'unité de traitement externe 34 à un ordinateur centralisé 35. Cet ordinateur centralisé 35 peut reconstituer le meilleur alignement local, grâce à un calcul retraçant le cheminement inverse par rapport au calcul de ce score global. Cette reconstitution est possible à partir des données 34 l s 342, 343 et 344 délivrées par l'unité de traitement externe 34 pour repérer cet alignement local. 2. Processeur utilisé dans un tel réseau Le schéma de la figure 4 présente le principe d'un processeur utilisé dans le réseau systolique de la figure 3. Ce processeur est identique aux processeurs 31 à 33 (cf figure 3). Un tel processeur comprend tout d'abord des moyens 41 de traitement, qui effectue les opérations classiques effectuées par tout processeur d'un réseau systolique. Ces moyens peuvent mettre en oeuvre, par exemple, l'algorithme de Smith et Waterman brièvement présenté en annexe 1. Pour cela, ces moyens 41 de traitement reçoivent d'une part la valeur à comparer Eh (ou élément de donnée), et d'autre part le score partiel courant Hh. n délivre au processeur suivant, pour le cycle systolique suivant les valeurs E et H qu'il traite. Selon l'invention, le processeur comprend en plus des moyens 42 de comparaison, qui délivrent la valeur M correspondant au maximum de la valeur H déterminée par les moyens 41 de traitement et de la valeur Mh délivrée par le processeur précédent. Cette valeur Mh correspond au meilleur score partiel délivré par le processeur précédent et la valeur M correspond au nouveau meilleur score partiel. Cette valeur M est délivrée au processeur suivant ou à l'unité de traitement externe. Lorsque les moyens 42 de comparaison modifient la valeur Mh, ils envoient une commande 43 associée à cette modification à des moyens 44 de multiplexage, alimentés d'une part par la valeur Ch délivrée par le processeur précédent, et d'autre part par le numéro du processeur courant. Ces moyens 44 de multiplexage délivrent la valeur actualisée C au processeur suivant. La valeur Ch correspond au numéro de la colonne de la matrice ayant détecté le meilleur score partiel associé Mh et délivré par le processeur précédent. La valeur C correspond, bien entendu, au nouveau numéro de la colonne associé au nouveau meilleur score partiel M. En d'autres termes, les moyens 42 de comparaison effectuent l'opération 224 (cf figure 2) et les moyens 44 de multiplexage effectuent l'opération 225 (cf figure 2). 3. Schéma détaillé A titre d'exemple particulier, on présente en figure 5 un mode de réalisation détaillé du processeur de la figure 4. L'homme du métier retrouvera aisément le rôle et la fonction de chaque composant. Ces composants ne sont donc pas commentés en détail. On notera en particulier la présence de bascules permettant la synchronisation des opérations, et de moyens permettant l'initialisation du processeur. Les éléments discutés en figure 4 conservent les mêmes références. Les principaux éléments nouveaux, selon l'invention, sont marqués en gras. VIt L'unité de traitement externe On présente maintenant, en relation avec le schéma simplifié de la figure 6, une unité de traitement externe selon l'invention. L'unité de traitement externe comprend, selon l'invention, des moyens 60a de détermination d'un score global et des moyens 60b de détermination de la position de l'alignement local correspondant. Les moyens 60a de détermination d'un score global permettent, à partir d'au moins un meilleur score partiel délivré par le dernier processeur 33 (cf figure 4), de déterminer le meilleur des meilleurs scores partiels calculés pour une série de comparaisons. Ces moyens 60a de détermination d'un score global comprennent des moyens 61 de comparaison permettant de repérer le score global. Ces moyens 61 de comparaison sont alimentés d'une part par le dernier meilleur score partiel M délivré par le dernier processeur du réseau systolique, et d'autre part par le dernier score global calculé Msg et délivrent la valeur la plus grande représentant le nouveau score global. Des moyens 62 de multiplexage sont alimentés par ce nouveau score global ou par une valeur 0 d'initialisation selon la valeur d'une commande Init 621. Les moyens 62 de multiplexage alimentent un registre 63 qui contient donc la valeur du dernier score global calculé. n est contrôlé par l'horloge Clk 631. Une telle horloge 631 permet que le dernier score global Msg calculé soit présent en entrée des moyens 61 de comparaison en même temps que le nouveau meilleur score partiel M. Les moyens 60b de détermination de la position de l'alignement local permettent d'identifier le processeur ayant calculé le score global, c'est-à-dire la position du meilleur alignement local. Ces moyens comprennent des moyens de détermination de la colonne et des moyens de détermination de la ligne du meilleur alignement local dans la matrice (cf tableau I). Les moyens de détermination de la colonne comprennent des seconds moyens 64 de multiplexage, alimentés d'une part par un indice de la colonne du meilleur score partiel courant délivré par le dernier processeur du réseau systolique, et d'autre part par l'indice de la colonne du dernier score global. Selon la valeur de la commande 641 issue des moyens 61 de comparaison, les moyens 64 de multiplexage délivrent à un deuxième registre 65 soit l'indice de la colonne repérant le meilleur score partiel (si ce dernier est supérieur au dernier score global calculé), soit l'indice de la colonne repérant le dernier score global calculé (si celui-ci est supérieur au meilleur score partiel). Les moyens 65 de mémorisation sont ainsi alimentés par l'indice de la colonne repérant le meilleur alignement local. Ils délivrent cette information au rythme imposé par l'horloge Clk 631, de façon que le dernier indice de la colonne Csg, repérant le dernier score global Msg calculé, soit présent en entrée des moyens 64 de multiplexage en même temps que le nouvel indice de la colonne associée au nouveau meilleur score partiel M. Les moyens de détermination de la ligne comprennent un compteur 66. Ce compteur 66 est initialisé à zéro à chaque premier élément de donnée d'une nouvelle séquence d'éléments de données. Il est incrémenté d'une unité à une cadence correspondant au rythme des cycles systoliques du réseau. fi permet de mesurer le temps de propagation du meilleur score partiel associé jusqu'au dernier processeur du réseau systolique, et donc de déterminer l'indice de la ligne repérant le meilleur score M. Le compteur 66 alimente des troisièmes moyens 67 de multiplexage. Ces moyens 67 de multiplexage sont alimentés d'une part par l'indice de la ligne repérant le nouveau meilleur score partiel délivré par le dernier processeur, et d'autre part par l'indice de la ligne associé au dernier score global calculé. Selon la valeur de la commande 641 (fonction de la comparaison effectuée par les moyens 61 de comparaison), les moyens 67 de multiplexage délivrent à un troisième registre 68 soit l'indice de la ligne repérant le meilleur score partiel (si ce dernier est supérieur au dernier score global calculé), soit l'indice de la ligne repérant le dernier score global calculé (si celui-ci est supérieur au dernier meilleur score partiel). Le registre 68 contient donc l'indice de la ligne repérant le meilleur alignement local. I1 délivre cette information repérant le dernier score global calculé au rythme imposé par l'horloge Clk 631. Ainsi, le dernier indice de ligne Lsg repérant le dernier score global Msg calculé est présent en entrée des moyens 67 de multiplexage en même temps que le nouvel indice de la ligne associé au nouveau meilleur score partiel M. L'unité de traitement externe peut donc ainsi délivrer, par exemple à un ordinateur central, le score global M sg associé au meilleur alignement local et les informations de position de ce meilleur alignement local (Csg : colonne ; Lsg: ligne). L'ordinateur centralisé peut alors effectuer à nouveau le calcul réalisé par le réseau systolique linéaire mais dans le sens inverse, afin de reconstituer l'alignement local à partir de ses coordonnées dans le tableau I. Cette opération permet de récupérer un à un les éléments de données par la fin de la plus grande sous-séquence commune. Ce calcul est long, mais cela ne présente pas d'inconvénient, car il est rare (de l'ordre d'un pour un million de séquences d'éléments de données en pratique). VII - Résultats Le tableau suivant présente l'apport de la machine "SAMBA" selon l'invention pour explorer une banque de séquences d'éléments de données par rapport à une station classique de travail rapide (par exemple DEC Alpha (marque déposée), fréquence de fonctionnement: 150 MHz). Ce tableau donne, pour différentes longueurs de la séquence étudiée (dite séquence d'interrogation), le temps d'exploration d'une banque protéique (par exemple SWISS-PROT- version 31 marque déposée) et l'accélération résultante. Longueur de la séquence d'interrogation 100 300 1000 3000 Temps d'exécution de la machine SAMBA 26 sec 30 sec O sec 77 sec temps d'exécution sur une station Dec Alpha 6min 17min 58min 190min Facteur accélérateur 13 34 87 148 Tableau m fl est à noter que plus la séquence étudiée est longue, plus le facteur accélérateur est important, et donc plus l'invention est performante. Cela est essentiellement dû au fait que l'accès aux données devient prépondérant par rapport au volume de calculs à effectuer, lorsque la puissance de calcul requise est faible (petite séquence d' interrogation). L'invention est donc encore plus performante pour des traitements qui exigent des comparaisons intensives, comme la comparaison de génomes entiers. Par exemple, la comparaison de la portion 3 du génome d'Haemophilus Influenza par rapport à la banque virale de GENBANK (marque déposée) prend quelques minutes sur la machine "SAMBA" alors que sur une station de travail classique, il faut 35 heures de calcul pour obtenir des résultats équivalents. Enfin, des traitements qui impliquent des comparaisons banque à banque exploitent au maximum les caractéristiques de l'invention. Une expérimentation menée en collaboration avec une équipe de biologistes de Versailles a consisté à confronter une banque de 814 séquences spécifiques (séquences orphelines de la levure) contre une banque de plus de 50 000 séquences (SWISS-PROT, version 33 marque déposée) pour mettre en évidence des homologies par le biais d'un algorithme réputé très efficace, mais énormément coûteux en calculs. Ce calcul a été réalisé en 1 heure et 45 minutes sur la machine "SAMBA" selon l'invention alors qu'il aurait fallu 327 heures sur une station de travail classique. vm. Autres applications Les applications possibles de la présente invention sont très variées. Elle concerne en effet toute application ayant besoin d'une comparaison ou d'une reconnaissance d'éléments de données. On peut, par exemple, citer: - la comparaison de séquences génétiques; - la reconnaissance de la parole; - la reconnaissance de textes; - la recherche de texte; - la correction orthographique; - la recherche d'empreintes; - la comparaison d'images. ANNEXE I 1. Principe Cet algorithme appartient à la classe des programmes dynamiques. Ce modèle permet aux biologistes de comparer des séquences de données biologiques à l'aide de deux opérations de base de mise en forme: - la substitution de caractères; - l'insertion et l'omission de caractères (cette dernière situation est appelée "trou"). Ainsi, en pratiquant une série de telles opérations de mise en forme, une séquence quelconque peut être transformée en n'importe quelle autre séquence. Le plus petit nombre d'opérations de mise en forme requises pour changer une séquence en une autre est donc une mesure de distance entre elles. Le calcul de la distance de mise en forme est réalisée par programmation dynamique, qui consiste à calculer récursivement une matrice NxN, où N représente la longueur des séquences. L'équation récurrente mise en oeuvre par la machine "SAMBA" vient de l'algorithme connu de Smith et Waterman. 2. Algorithme de Smith et Waterman Cet algorithme se rapporte généralement à l'identification de sous-séquences similaires utilisant le procédé de programmation dynamique. On présente ci-dessous un exemple de mise en oeuvre: Soit les deux séquences suivantes S1 et S2: S = AGTCCGAGGGCTACTCTACTGAAC S2 = CCAATCTACTACTGCTTGCAGTAC On peut vérifier que la sous-séquence CTACTCTACT de S1 est similaire à la sous-séquence CCAATCTACT de S2: S1 AGTCCGAGGG CTACTCTACT GAAC 1:1:111111 S2 CCAATCTACT ACTGCTTGCAGTAC Où "I" représente une correspondance entre les caractères respectifs pointés de chaque séquence d'éléments de données, et ":" signifie que les caractères respectifs pointés de chaque séquence d'éléments de données sont différents. Selon un autre calcul, on peut aussi trouver que la même sous-séquence CTACTCTACT de S1 est similaire à une autre sous-séquence CTACTACTGCT de S2: S 1 AGTCCGAGGG CTACT. CTACT GAAC | | | | | | | : | | S2 CCAAT CTACTACTGCT TGCAGTAC Pour identifier les sous-séquences communes, l' algorithme recherche la similarité entre deux sous-séquences se terminant aux positions Sli et S2j des deux séquences S1 et S2 (respectivement de longueur 11 et 12). L'équation récurrente de base est donnée par la formule suivante : H(i,j) = Max{#; E(i,j) ; F(i,j) ; H(i - 1, j - 1) + Sbt(S1i,S2j)} (1) avec 0 E(i, j) = Max{H(i,j - 1) - &alpha;; E(i, j - 1)- ss} F(i,j) = Max{H(i-1,j) - &alpha;;F(i-1,j) - ss} Initialisations H(i,O) = E(i,O) = hi(i); 6 = 0; H(O,j) = F(O,j)=vi(j); Où "i" représente l'indice de la ligne de la matrice; "j" représente l'indice de la colonne de la matrice; Sbt représente la table de coût de substitution de caractère. Les paramètres pris en compte pour sélectionner différentes variantes de l'algorithme de Smith et Waterman, sont: "a" représente le coût du premier trou; "ss" représente le coût des trous suivantes ; "#" représente une variable d'initialisation. La fonction coût total des trous G(k) est donnée par la formule suivante : G(k) = &alpha;+ss*(k-1) avec (ss#&alpha;). Il est à noter que le coût du trou peut être plus simple (comme dans l'exemple 1 donné plus bas) en donnant à a et ss les mêmes valeurs. Par exemple, si l'on choisit les valeurs de paramètres: a=20; ss = 10; l1 = l2 = 24; hi(i) = vi(j) = O; Sbt (x,y) = (10 si (x=y) ; -9 sinon) où x et y représentent le caractère courant de chaque séquence respectivement S1 et S2; On obtient, après le calcul effectué par l'algorithme de Smith et Waterman, la matrice suivante avec pour chaque position (S1i, S2j), une valeur de similarité H(i, j): S2 C C A A T C T A C T A C T G C T T G C A G T A C S1 A 0 0 10 10 0 0 0 10 0 0 10 0 0 0 0 0 0 0 0 10 0 0 10 0 G 0 0 0 1 1 0 0 0 1 0 0 1 0 10 0 0 0 10 0 0 20 0 0 1 T 0 0 0 0 11 0 10 0 0 11 0 0 11 0 1 10 10 0 1 0 0 30 10 0 C 10 10 0 0 0 21 1 1 10 0 2 10 0 2 10 0 1 1 10 0 0 10 21 20 C 10 20 1 0 0 10 12 0 11 1 0 12 1 0 12 1 0 0 11 1 0 0 1 31 G 0 1 11 0 0 0 1 3 0 2 0 0 3 11 0 3 0 10 0 2 11 0 0 11 A 0 0 11 21 1 0 0 11 0 0 12 0 0 0 2 0 0 0 l 10 0 2 10 1 G 0 0 0 2 12 0 0 0 2 0 0 3 0 10 0 0 0 10 0 0 20 0 0 1 G 0 0 0 0 0 3 0 0 0 0 0 0 0 10 1 0 0 10 1 0 10 11 0 0 G 0 0 0 0 0 0 0 0 0 0 0 0 0 10 1 0 0 10 1 0 10 1 2 0 C 10 10 0 0 0 10 0 0 10 0 0 10 0 0 20 0 0 0 20 0 0 1 0 12 T O 1 1 0 10 0 20 0 0 20 0 0 20 0 0 30 10 0 0 11 0 10 0 0 A 0 0 11 11 0 1 0 30 10 0 30 10 0 11 0 10 21 1 0 10 2 0 20 0 C 10 10 0 2 2 10 0 10 40 20 10 40 20 10 21 1 1 12 11 0 1 0 0 30 T O 1 1 0 120 20 0 20 50 30 20 50 30 20 31 11 1 3 2 0 11 0 10 C 10 10 0 0 0 22 2 11 10 30 41 40 30 41 40 20 22 2 11 0 0 0 2 10 T 0 1 1 0 10 2 32 12 2 20 21 32 50 3 Ainsi, dans cet exemple, le meilleur score obtenu est 62. A partir de ce meilleur score et de ses coordonnées, l'ordinateur hôte exécute une procédure de restitution inverse (pour "backtrack" en anglais) qui consiste à recalculer les valeurs précédentes de similarité prises lors de la récurrence. Cette procédure permet grâce aux coordonnées de ces dernières de reconstituer les sous-séquences respectives de S1 et S2 correspondantes. Cela donne les sous-séquences CTACTCTACT et CCAATCTACT respectives de S1 et S2. 3. Exemple 1: alignement de deux séquences: On considère ici deux séquences S1 et S2 de longueur respective 11 et 12. L'objectif est de trouver l'alignement de S1 et S2 qui maximise la valeur de la similarité à l'aide du coût simple de trou. La valeur de la similarité est donnée par H(11, 12) calculée par l'équation donnée plus haut (1) avec les paramètres prenant comme valeur: 8=-oo; a = = g (coût du trou); hi(i) = vi(i) = - g * i; En donnant pour valeur - oo à o, le premier terme de l'équation (1) donnée plus haut est annulé. L'équation résultante devient: H(i,j) = Max {H(i, j-l) - g ; H(i-l, j) - g ; H(i-l, j-l) + Sbt (S1i, 52j)J ; (2) Les initialisations deviennent: H(i,0) = E(i,0) = -g * i; Le coût de k trous multiples gk devient une simple fonction du coût d'un trou: gk = g*k; 4. Exemple 2: identification de segments similaires L'objectif est de localiser les sous-séquences similaires entre deux séquences. Cela représente probablement l'algorithme le plus utile pour la recherche courante, puisque deux séquences biologiques qui présentent une petite similarité d'ensemble peuvent partager des relations surprenantes sur des segments courts. Les paramètres prennent comme valeurs: 8=0; &alpha; = &alpha; ; ss = ss ; hi(i) = vi(i) = 0 ; La matrice de similarité H comprend des maxima locaux qui peuvent être interprétés comme des zones où les similarités apparaissent entre deux sequences. Des coûts multiples de trou sont pris en compte comme suit: (a) est le coût du premier trou; (ss) est le coût des trous suivants. La fonction de coût total de "trou" G(k) est donnée par l'équation suivante : G(k) = &alpha; + ss * (k-1) avec (ss # &alpha;). Des outils logiciels trouvent des alignements locaux sans trou. Ce type d'alignement peut être calculé sur la machine "SAMBA" en donnant aux paramètres les valeurs suivantes : 8=0; &alpha; = ss = - # ; hi(i) = vi(i) = 0 ; Il en résulte pour l'équation récurrente (1) exprimant la matrice de similarité la formule suivante : H(i, j) = Max (O ; H(i-1, j-1) + Sbt (S1i, S2j)} (3) REVENDICATIONS 1. Procédé de traitement des résultats d'une comparaison de deux séquences d'éléments de données, mettant en oeuvre un réseau systolique linéaire de processeurs, ledit réseau systolique comprenant au moins deux processeurs (31 à 33) effectuant chacun, à chaque instant de traitement, une comparaison (221) entre deux éléments desdites séquences, et produisant une information représentative de ladite comparaison, dite score partiel, chacun desdits processeurs (31 à 33) transmettant (226) au processeur suivant une information dite meilleur score partiel (312, 322, 332) résultant de la comparaison (223) entre le score partiel courant et le meilleur score partiel reçu du processeur précédent, caractérisé en ce que chacun desdits processeurs (31 à 33) transmet (226) également au processeur suivant dans ledit réseau systolique une information de localisation (313, 323, 333), permettant d'identifier le processeur (31 à 33) qui a détecté ledit meilleur score partiel (312, 322. 332)- 2. Procédé selon la revendication 1, caractérisé en ce que ladite information de localisation (313, 323, 333) est un identifiant dudit processeur (31 à 33) ayant détecté ledit meilleur score partiel (312, 322. 332)- 3. Procédé selon l'une quelconque des revendications 1 et 2, caractérisé en ce que l'on mesure (234) le temps de propagation dudit meilleur score partiel (342) jusqu'au dernier processeur (33). 4. Procédé selon la revendication 3, caractérisé en ce que ledit traitement étant représenté sous la forme d'une matrice formée de lignes et de colonnes, l'emplacement du meilleur alignement local dans ladite matrice est déterminé par: - une indication de colonne, correspondant au processeur qui a repéré ledit meilleur alignement local, et - une indication de ligne, déterminée par une analyse du temps de propaga tion du score partiel associé audit meilleur alignement local. 5. Procédé selon l'une quelconque des revendications 1 à 4, caractérisé en ce que le dernier processeur (33) dudit réseau systolique délivre à une unité de traitement externe (34) ledit meilleur score partiel (332) et ladite information de localisation (333) pour un lot de séquences d'éléments de données comparées à une séquence de référence, et en ce que ladite unité de traitement externe (342) détermine le plus élevé desdits meilleurs scores partiels (312, 322, 332) dit score global (342) et la position (343, 344) dans la séquence de référence de l'alignement local correspondant audit score global (342). 6. Procédé selon la revendication 5, caractérisé en ce qu'il comprend une étape (25) de reconstitution de l'alignement local correspondant audit score global (342) à partir de ladite information de localisation (333). 7. Procédé selon la revendication 6, caractérisé en ce que ladite unité de traitement externe (34) réitère (24) le calcul effectué par ledit réseau systolique pour le meilleur alignement local identifié. 8. Réseau systolique linéaire de processeurs, destiné à traiter des résultats d'une comparaison de deux séquences d'éléments de données, ledit réseau systolique étant du type comprenant au moins deux processeurs (31 à 33) effectuant chacun, à chaque instant de traitement, une comparaison (221) entre deux éléments desdites séquences, et produisant une information représentative de ladite comparaison, dite score partiel, chacun desdits processeurs (31 à 33) transmettant au processeur suivant une information dite meilleur score partiel (312, 322, 332) résultant de la comparaison (223) entre le score partiel courant et le meilleur score partiel reçu du processeur précédent, caractérisé en ce que chacun desdits processeurs (31 à 33) comprend des moyens (44) de transmission au processeur suivant dans ledit réseau systolique d'une information de localisation (313, 323, 333), permettant d'identifier le processeur (31 à 33) qui a détecté ledit meilleur score partiel (312, 322, 332)- 9. Processeur destiné à être mis en oeuvre dans un réseau systolique linéaire de processeurs comprenant au moins deux processeurs (31 à 33) effectuant chacun, à chaque instant de traitement, une comparaison (221) entre deux éléments desdites séquences, et produisant une information représentative de ladite comparaison, dite score partiel, ledit processeur (31 à 33) transmettant au processeur suivant une information dite meilleur score partiel (312, 322, 332) résultant de la comparaison (223) entre le score partiel courant et le meilleur score partiel reçu du processeur précédent, caractérisé en ce que ledit processeur (31 à 33) comprend également des moyens (44) de transmission à un processeur suivant dans ledit réseau systolique d'une information de localisation (313, 323, 333), permettant d'identifier le processeur (31 à 33) qui a détecté ledit meilleur score partiel (312, 322, 332). 10. Dispositif de traitement des résultats de comparaison de deux séquences d'éléments de données, du type comprenant un réseau systolique linéaire de processeurs comprenant au moins deux processeurs (31 à 33) effectuant chacun, à chaque instant de traitement, une comparaison (221) entre deux éléments desdites séquences, et produisant une information représentative de ladite comparaison, dite score partiel, chacun desdits processeurs (31 à 33) transmettant (226) au processeur suivant une information dite meilleur score partiel (312, 322, 332) résultant de la comparaison (223) entre le score partiel courant et le meilleur score partiel reçu du processeur précédent, caractérisé en ce que ledit dispositif reçoit du dernier processeur (33) dudit réseau systolique: - une première information, dite meilleur score partiel (332) permettant de déterminer un score global (342) - une information de localisation de l'alignement local (333) correspondant audit meilleur score partiel (332) permettant d'identifier le processeur (31 à 33) qui a détecté ledit meilleur score partiel (33 , de façon à déterminer la position (343, 344) du meilleur alignement local correspondant audit score global (34 ; et en ce que ledit dispositif comprend: - des moyens (60a) de détermination d'un score global à partir d'au moins un meilleur score partiel (33 , permettant de déterminer le meilleur desdits scores partiels (342) pour retrouver ledit meilleur alignement local (343, 344) desdites séquences d'éléments de données traitées; - des moyens (60b) de détermination de la position de l'alignement local (343, 344) correspondant audit score global (342) permettant d'identifier le processeur (31 à 33) qui a détecté ledit score global (342)- i 1. Dispositif selon la revendication 10, caractérisé en ce que lesdits moyens (60a) de détermination dudit score global comprennent: - des moyens (61) de comparaison permettant de calculer ledit score global (34 , et alimentant - des premiers moyens (62) de multiplexage permettant d'initialiser la valeur dudit score global (342) à chaque premier élément de donnée d'une nouvelle séquence d'éléments de données, et alimentant - des premiers moyens (63) de mémorisation permettant de sauvegarder le dernier score global (342) calculé et rebouclant sur lesdits moyens (61) de comparaison. 12. Application du procédé selon l'une quelconque des revendications 1 à 7, et/ou du dispositif de l'une quelconque des revendications 10 à 11, à au moins l'un des domaines appartenant au groupe comprenant les domaines suivants: - la comparaison de séquences génétiques; - la reconnaissance de la parole; - la reconnaissance de textes; - la recherche de texte; - la correction orthographique; - la recherche d'empreintes; - la comparaison d'image.