Cours de Bioinformatique
(la recherche de similitudes entre séquences)



II. LA RECHERCHE DE SIMILITUDES ENTRE SEQUENCES BIOLOGIQUES

  1. LES SYSTEMES DE SCORES

  2. LES ALGORITHMES ET LES PROGRAMMES DE COMPARAISON DE SEQUENCES

2.3 Les programmes de comparaison avec les banques de séquences

           La taille sans cesse croissante des banques de séquences a nécessité l'élaboration d'algorithmes spécifiques pour effectuer la comparaison d'une séquence avec une banque de données car les algorithmes standards de comparaison entre deux séquences sont généralement trop longs sur des machines classiques. La plupart de ces programmes constituent des méthodes heuristiques. Leur but est de filtrer les données de la banque en étapes successives car peu de séquences vont avoir des similitudes avec la séquence comparée. Ces méthodes heuristiques utilisent donc certaines approximations pour éliminer rapidement les situations sans intérêt et ainsi repérer les séquences de la banque susceptibles d'avoir une relation avec la séquence recherchée. Ces programmes permettent ensuite de calculer un score pour mettre en évidence les meilleures similitudes locales qu'ils ont observées. Il existe de nombreux programmes qui répondent à cette fonction avec des approches qui peuvent être très différentes. Nous nous limiterons ici à la description détaillée des deux types de programme les plus utilisés par les biologistes qui sont les logiciels FASTA (Pearson et Lipman, 1988) et BLAST (Altschul et al., 1990). Ces programmes ont une approche différente mais complémentaire pour effectuer des recherches à travers une base de données, mais sont basés tous les deux sur des méthodes très heuristiques. C'est pourquoi ils doivent être utilisés essentiellement comme logiciels permettant de repérer les séquences de la banque susceptibles d'avoir des ressemblances biologiques avec la séquence recherchée. Ils ne constituent pas des programmes optimisés pour comparer deux séquences entre elles. Très souvent, les résultats qu'ils procurent devront être confirmés ou renforcés par d'autres programmes plus spécialisés en particulier dans la recherche de caractéristiques biologiques. Actuellement, seule, l'utilisation de machines parallèles ou massivement parallèles et de machines dites câblées donnent la possibilité d'utiliser des algorithmes plus rigoureux comme celui de Smith et Waterman (1981) pour la comparaison avec une banque de données.
 

2.3.1 Le logiciel FASTA

          L'algorithme est basé sur l'identification rapide des zones d'identité entre la séquence recherchée et les séquences de la banque. Cette reconnaissance est primordiale car elle permet de considérer uniquement les séquences présentant une région de forte similitude avec la séquence recherchée. On peut ensuite, à partir de la meilleure zone de ressemblance, appliquer localement à ces séquences un algorithme d'alignement optimal. Le logiciel regroupe en fait deux programmes de recherche avec les banques de données. Le premier est le programme FASTA qui possède une version nucléique et protéique et le deuxième est le programme TFASTA qui recherche une séquence protéique avec les séquences d'une base nucléique traduite dans les 6 phases.
 

          Les différentes étapes de l'algorithme
 
          Pour chaque séquence de la banque, l'algorithme se déroule en quatre étapes sélectives distinctes qui permettent de cibler rapidement et précisément les régions intéressantes pour l'alignement optimal.
 
- La première étape consiste à repérer les régions les plus denses en identités partagées par les deux séquences. La codification numérique des séquences est ici utilisée (voir la recherche de segments identiques) avec une longueur des segments codés (k-tuple) qui est généralement de 1 ou 2 pour les protéines et de 4 à 6 pour les acides nucléiques. Cette étape confère à l'algorithme l'essentiel de sa rapidité.
 
- Dans une deuxième étape, on recalcule à l'aide d'une matrice de scores élémentaires un score pour les dix meilleurs régions d'identité trouvées dans l'étape précédente en considérant éventuellement des associations non exactes entre certains éléments des séquences. Pour les protéines, on utilisera ici une matrice de substitution comme la PAM250 de Dayhoff ou la BLOSUM50. Cette deuxième étape correspond donc à une recherche de similitudes sans insertion-délétion uniquement sur les régions de haute identité. Les scores obtenus correspondent à des régions initiales de premier ordre et l'on qualifie de score init1 celui qui représente la région de plus fort score parmi les dix analysées.
 
- La troisième étape essaie de joindre les régions définies à l'étape précédente, bien entendu s'il en existe au moins deux et si chacune de celles-ci possède un score supérieur à un score seuil prédéfini. Ce seuil correspond en fait à un score moyen attendu pour des séquences non apparentées. On réunira ces régions initiales à chaque fois que la somme de leur scores diminuée d'une pénalité de jonction est supérieure ou égale au score init1. Ce score s'il existe est appelé initn et correspond à une région initiale de deuxième ordre.
 
- La quatrième étape consiste à effectuer l'alignement optimal de la séquence recherchée avec la séquence de la banque en considérant uniquement les parties des séquences délimitées par la meilleure région initiale de score initn (qui est égale à init1 s'il n'y a pas eu de jonction à l'étape 3). On obtient alors un score optimal dénommé opt. Cet alignement est effectué uniquement pour un nombre limité de séquences fixé par l'utilisateur. Ce sont les séquences qui correspondent aux plus hauts scores initiaux initn.
 
Ces quatre étapes de l'algorithme sont résumées dans la Figure 18. Une estimation statistique est donnée en traçant l'histogramme des meilleures scores obtenus pour chaque séquence de la banque avec le calcul de la moyenne et de l'écart type liés à cette distribution. Cette estimation utilise la théorie selon laquelle les similarités locales d'une séquence comparée avec une banque de données suit une distribution de valeurs extrêmes (voir par exemple Altschul et al.,1994).
 

          Les qualités de l'algorithme
 
          L'algorithme possède une bonne sensibilité du fait qu'il prend en compte les insertions-délétions. Ceci est fait en minimisant les explorations entre les deux séquences puisqu'on ne considère que les séquences potentiellement intéressantes pour effectuer l'étape de programmation dynamique, en ciblant de plus, les régions où l'on doit effectuer la recherche d'alignement. L'étape ultime d'alignement optimal est réalisée uniquement sur la meilleure région de haute similitude même si d'autres régions possèdent un score suffisant pour l'effectuer. Cela permet d'éviter en partie le bruit de fond dû à des motifs non significatifs et intrinsèques à la séquence recherchée mais a l'inconvénient de ne pas pouvoir considérer de grandes insertions durant l'alignement des séquences. Cette lacune est maintenant évitée dans la dernière version du logiciel (Octobre 1995) pour l'alignement des séquences protéiques. En effet celle-ci considère la totalité des séquences pour effectuer l'algorithme d'alignement local de Smith et Waterman (1981) plutôt que d'effectuer l'alignement global de Needleman et Wunsch (1970) uniquement sur des portions de séquences protéiques. L'édition des résultats est maintenant triée en fonction des scores opt contrairement aux premières versions qui considéraient les scores initiaux (initn), ce qui rendait parfois difficile la détection d'un alignement dont le score optimal est bon mais dont le score initial initn est médiocre. Enfin Pearson (1990) explique que lorsque le score opt est plus faible que le score initn, alors la similitude est souvent inintéressante.

          L'estimation statistique est faite à partir des scores obtenus avec l'ensemble des séquences de la banque. Cependant, le logiciel fournit également des programmes d'estimation statistique basés sur une méthode de Monte Carlo (cf. l'évaluation des résultats) pour estimer la validité d'un score opt particulier entre une séquence de la banque et la séquence recherchée. Il s'agit des programmes PRDF et PRSS qui considèrent une distribution de valeurs extrêmes pour les scores aléatoires et qui sont directement inspirés du programme PRDF2 (Pearson, 1990) qui regroupe les séquences en courts segments pour effectuer les simulations. Le programme PRDF produit des simulations selon l'algorithme de Needleman et Wunsch appliqué localement pour l'étape d'alignement optimal alors que le programme PRSS utilise l'algorithme complet de Smith et Waterman entre deux séquences protéiques.
 


Quelques serveurs des programmes FASTA :
[EBI](Angleterre) [DISC](Japon) [IGH](France)

 

2.3.2 Le logiciel BLAST

          L'intérêt de l'algorithme est que sa conception est basée sur un modèle statistique. Celui-ci a été établi d'après les méthodes statistiques de Karlin et Altschul (1990 ; 1993) qui s'appliquent aux comparaisons de séquences sans insertion-délétion. L'unité fondamentale de BLAST est le HSP (High-scoring Segment Pair). C'est un couple de fragments identifiés sur chacune des séquences comparées, de longueur égale mais non prédéfinie, et qui possède un score significatif. En d'autres termes, un HSP correspond à un segment commun, le plus long possible, entre deux séquences qui correspond à une similitude sans insertion-délétion ayant au moins un score supérieur ou égal à un score seuil. Un deuxième score MSP (Maximal-scoring Segment Pair) a été défini comme étant le meilleur score obtenu parmi tous les couples de fragments possibles que peuvent produire deux séquences. Les méthodes statistiques de Karlin et Altschul sont appliquées pour déterminer la signification biologique des MSPs et par extrapolation la signification des scores HSPs obtenus lors de la comparaison. Ce logiciel possède en fait quatre programmes distincts de comparaison avec les bases de données. BLASTN (séquence nucléique contre base nucléique), BLASTP (séquence protéique contre base protéique), BLASTX (séquence nucléique traduite en 6 phases contre base protéique), et TBLASTN (séquence protéique contre base nucléique traduite en 6 phases).
 

          Les différentes étapes de l'algorithme
 
          La stratégie de la recherche consiste à repérer tous les HSPs (fragments similaires) entre la séquence recherchée et les séquences de la base. Pour déterminer un HSP, des mots de longueur fixe sont identifiés dans un premier temps entre la séquence recherchée et la séquence de la banque. Dans le cas des acides nucléiques, cela revient à des recherches d'identité entre les deux séquences sur des segments de longueur fixe (généralement 11). Par contre dans le cas des protéines, on effectue d'abord une liste de mots similaires pour chaque mot de longueur fixe (généralement 3) de la séquence recherchée et l'on repère ensuite dans la banque les séquences qui possèdent au moins un de ces mots. Un mot similaire est un mot qui, comparé avec un mot de la séquence recherchée, obtient un score supérieur à un score seuil lorsque l'on considère une matrice de substitution. Dans un deuxième temps, on cherche à étendre la similitude dans les deux directions le long de chaque séquence, à partir du mot commun, de manière à ce que le score cumulé puisse être amélioré.
 
L'extension s'arrêtera dans les trois cas suivants:
 
- Si le score cumulé descend d'une quantité x donné par rapport à la valeur maximale qu'il avait atteint.
- Si le score cumulé devient inférieur ou égal à zéro.
- Si la fin d'une des deux séquences est atteinte.
 
La signification des segments similaires obtenus est ensuite évaluée statistiquement. Celle-ci est faite en fonction de la longueur et de la composition de la séquence, de la taille de la banque et de la matrice de scores utilisée. Cette estimation donne en fait la probabilité que l'on a d'observer au hasard une similitude de ce score à travers la banque de séquences considérée. Lorsque plusieurs HSPs sont trouvées sur la même séquence, le programme utilise alors une méthode de "somme statistique" (Karlin et Altschul, 1993) qui considère que la signification statistique d'un ensemble de HSPs doit être plus élevée que n'importe quel HSP appartenant à cet ensemble. Les HSPs, dont la signification statistique satisfait une valeur seuil désignée par l'utilisateur sont ensuite édités.
 

          Les qualités de l'algorithme
 
          Le principal avantage est que le fondement de l'algorithme s'appuie avant tout sur des critères statistiques. Un autre point intéressant de la méthode (essentiellement pour les protéines) est que la première étape de reconnaissance des similarités ne recherche pas uniquement des zones d'identité mais accepte la présence de similitudes en considérant une matrice de scores. Ceci permet d'intégrer dès le début de la recherche les critères biologiques compris dans la matrice. De plus, les résultats peuvent être édités selon plusieurs tris possibles et en particulier selon leur signification statistique et non suivant la valeur de leur score. On retrouvera donc les segments les plus probables en début de liste. Ce logiciel a été très optimisé dans son écriture, notamment par une précodification de la banque, ce qui lui vaut d'être un des plus rapides tout en conservant une sensibilité satisfaisante. De plus, il possède des versions qui s'exécutent sur machines parallèles.

          Comme la recherche dans la banque de données est basée sur l'identification de segments, le bruit de fond est plus présent dans ce type d'approche. Il est généralement du à des qualités intrinsèques de la séquence recherchée comme la présence de régions répétées internes, ou la présence de segments de basse complexité non spécifiques d'une caractéristique biologique mais communs à plusieurs familles de protéines, par exemple les segments basiques ou acides. Des logiciels complémentaires qui opèrent comme filtres peuvent être utilisés comme paramètres dans les programmes BLAST pour remédier à ces problèmes. Ainsi, le programme SEG (Wootton et Federhen, 1993) masque des régions de faible complexité et le programme XNU (Claverie et States, 1993) cache des régions répétées de courte périodicité.
 


Quelques serveurs des programmes BLAST :
[NCBI](USA) [ExPASy](Suisse) [IGH](France)

 

2.3.3 L'utilisation de machines spécialisées

          Depuis quelques années, de nouvelles générations d'ordinateurs, avec des architectures différentes, sont nées et permettent d'accroître sensiblement la performance de certains algorithmes. On peut réunir ces super calculateurs en deux catégories.

          La première est celle des ordinateurs massivement parallèles qui possèdent de nombreux processeurs (par exemple, 4096 pour une Maspar) et qui donnent la possibilité d'effectuer une tâche simultanément sur chacun des processeurs. Il est évident que ce genre d'architecture convient tout à fait à la comparaison d'une séquence avec toutes les séquences d'une banque en utilisant un algorithme qui est répété autant de fois qu'il existe de séquences dans la banque. C'est ainsi que le serveur BLITZ à l'EMBL propose le programme MPSEARCH qui est une implantation de l'algorithme de Smith et Waterman sur une Maspar (Sturrock et Collins, 1994).

          La deuxième catégorie est celle des ordinateurs dits "câblés". Ces machines sont conçues exclusivement pour effectuer une ou plusieurs tâches précises. Autrement dit, l'algorithme est "soudé" dans la machine. Ce genre d'architecture, coûteuse et qui permet peu d'évolution, fait de plus en plus place à l'utilisation de processeurs personnalisés, c'est à dire dont la fonction peut être reprogrammée. Ainsi, BIOCCELERATOR est une carte spécialisée pour l'analyse des séquences qui peut posséder jusqu'à 16 processeurs associés à quatre modules : un pour l'algorithme de Smith et Waterman (1981), un pour le programme de recherche de motifs protéiques PROFILESEARCH (Gribskov et al., 1990), un pour le programme FASTA (Pearson et Lipman, 1998), et un pour le programme d'alignements multiples PILEUP issu de la méthode décrite par Higgins et Sharp (1989). Il est possible d'utiliser une telle carte par requête WWW.
 

2.3.4 La disponibilité des programmes à travers les réseaux informatiques

          Les programmes de comparaison avec les bases de données sont devenus aujourd'hui des outils très couramment utilisés par les biologistes. Néanmoins, il est évident que chacun ne peut pas disposer dans son laboratoire des matériels les plus sophistiqués et les plus puissants pour effectuer ces tâches rapidement. C'est pourquoi, il existe un nombre croissant de serveurs qui permettent l'utilisation gratuite de ces programmes avec des banques de données actualisées quotidiennement. On trouve principalement sur ces serveurs les programmes de comparaison qui sont des standards dans le domaine comme les logiciels FASTA et BLAST ou comme nous l'avons vu au paragraphe précédent, l'implantation de certains algorithmes sur des matériels spécialisés. Tous ces serveurs sont accessibles via les réseaux informatiques à hauts débits par l'utilisation des messageries électroniques ou de systèmes infocentres tels que WAIS, gopher ou WWW. Une liste des principaux serveurs français et étrangers en biologie et bioinformatique est donnée ici.
 

2.4 Les programmes de recherche de motifs

2.4.1 "motif" et "pattern"
 
          Dans la littérature les motifs sont qualifiés en termes anglo-saxons de "pattern" ou de "motif". Un "motif" est généralement un segment court, continu et non ambigu d'une séquence alors qu'un "pattern" a une structure plus complexe. Il est souvent composé de différents "motifs" qui peuvent être plus ou moins éloignés les uns des autres et sa définition peut comporter des exclusions ou des associations de "motifs". C'est pourquoi, il est parfois nécessaire d'utiliser implicitement ou explicitement des opérateurs logiques tels que le OU, le ET ou le NON dans sa définition. On peut considérer très souvent qu'un "motif" est une séquence exacte ou peu dégénérée et qu'un "pattern" est une séquence dégénérée et/ou composée. Dans ce mémoire nous emploierons le terme générique français motif pour désigner l'ensemble de ces définitions.
 

2.4.2 Les différents types de motifs

          Il existe plusieurs raisons de rechercher des motifs à travers les séquences car ils sont généralement impliqués dans des systèmes de régulation ou définissent des fonctions biologiques. Parmi ces raisons, on peut citer la détermination de la fonction d'une nouvelle séquence (par exemple en localisant un ou plusieurs motifs répertoriés dans des bases de motifs), l'identification dans une séquence nucléique de régions codantes (par exemple en repérant les codons d'initiation et de terminaison, les sites d'épissages et les zones de fixation des ribosomes), la recherche d'un motif particulier dans une séquence (par exemple en identifiant sur une séquence les sites de coupures d'enzymes de restriction ou des promoteurs spécifiques etc...), ou bien l'extraction à partir des banques de données (par exemple extraire des séquences possédant le même signal de régulation ou la même signature protéique pour effectuer des études comparatives ultérieures).

          Il est donc évident qu'il existe des niveaux de complexité très différents dans la définition des motifs. Certains sont précis et non ambigus comme les sites de reconnaissance des enzymes de restrictions ou comme certains motifs de protéases. D'autres peuvent être beaucoup plus flous et complexes comme les motifs consensus liés à des familles de protéines ou les facteurs de transcription. Dans ce cas, la difficulté est souvent de savoir quel motif utiliser et quelle est la pertinence de la définition. Staden (1990) a répertorié divers critères et éléments qui peuvent intervenir dans la définition d'un motif. On y trouve les critères les plus simples comme la ressemblance par rapport à un motif exact aux critères les plus complexes comme l'ensemble des acides aminés permis à une position donnée ou la composition d'un motif en plusieurs sous-motifs séparés par des régions variables. On y recense également par exemple, l'éventualité de trouver des régions répétées ou bien encore la définition d'une matrice consensus donnant la probabilité de chaque position. En fait, on peut regrouper les éléments de définition qu'il décrit en deux catégories distinctes, ceux qui sont liés à la structure primaire des séquences et ceux qui constituent des structures secondaires. Avec l'extension de la détermination de structure d'ADN ou de protéine par les méthodes de diffraction des rayons X ou de résonance magnétique nucléaire (RMN), il est possible maintenant d'ajouter de plus en plus de critères tridimensionnels dans la définition des motifs. C'est sans aucun doute une des voies de recherche les plus prometteuses des prochaines années pour caractériser des sites complexes comme ceux impliqués dans les associations ADN-protéines.
 

2.4.3 La définition des motifs

          La qualité de la définition d'un motif dépend effectivement de sa complexité, mais également du choix de la représentation des informations qui le composent. Nous décrirons ici les principales méthodes utilisées dans la définition des motifs qui constituent généralement le formalisme de base pour les représenter. Ces méthodes s'attachent à décrire la suite des résidus définissant le motif et reposent essentiellement sur des comparaisons de séquences. On ne parlera pas des méthodes plutôt statistiques comme les analyses de fréquences dans les régions promotrices ou des méthodes liées à l'apprentissage comme celles utilisées dans les réseaux neuronaux. Même si beaucoup de critères sont communs lors de la définition des motifs nucléiques et protéiques, il nous a paru intéressant de distinguer ces deux types de motifs pour mettre mieux en évidence certaines spécificités.
 

          Les motifs nucléiques
 
          La définition d'un motif nucléique commence en général par l'analyse d'un alignement multiple de toutes les séquences connues comme étant actives pour la fonction étudiée. Cela permet de connaître pour chaque position la variabilité en bases. L'alignement de ces séquences peut servir à produire une séquence consensus, une table de fréquences ou une matrice de pondération des éléments qui composent le motif. La séquence consensus rend compte de la ou des bases les plus fréquemment rencontrées pour chaque position. Dans le cas de séquences très spécifiques, cette simple séquence suffit pour décrire de manière satisfaisante une région active. Malheureusement, dans la plupart des cas comme pour les facteurs de transcription, elle ne suffit pas pour identifier les sites biologiquement actifs car elle n'est pas forcément celle qui est le plus souvent rencontrée comme signal. Au pire elle peut elle-même ne pas exister en tant que signal ! Ceci est du essentiellement au fait que l'on considère l'indépendance entre les positions durant l'établissement du consensus et que ce dernier ne représente qu'un résumé de toutes les séquences effectivement actives. Pour éviter en partie ce problème, un nombre maximum de positions pour lesquelles on tolère la non identité par rapport à la séquence consensus peut être incorporé dans la définition du motif. On parle alors d'éloignement ou de distance à la séquence consensus (Mengeritsky et Smith, 1987).

          Pour exprimer l'ambiguité et la complexité d'un motif, on peut également déduire de l'alignement des séquences une table de fréquences en comptabilisant les occurrences de chaque base à chaque position du motif. En d'autres termes, on définit à partir d'un échantillon donné, la probabilité d'apparition des bases pour chaque position du motif. Il est possible ensuite, pour augmenter la fiabilité des probabilités, de considérer des critères supplémentaires, intrinsèques aux séquences, comme la thermodynamique liée au motif étudié ou la fréquence attendue des bases selon la région où se trouve le motif. On peut ainsi, considérer que l'apparition d'une cytosine est plus significative que l'apparition d'une guanine dans une zone riche en guanine. La transformation de la table des fréquences en tenant compte éventuellement de critères supplémentaires donne naissance à une matrice de pondération (weight matrix). Celle-ci est généralement construite en prenant le logarithme de la fréquence de chaque base à chaque position pour optimiser les différences contenues dans la table des fréquences. Pour prendre en compte des critères supplémentaires comme le pourcentage des bases de la région étudiée, chacune des valeurs logarithmiques pourra être divisée par la fréquence génomique de la base observée. On trouvera dans la littérature plusieurs exemples et méthodes de génération de matrices de fréquence ou de pondération (Bucher, 1990 ; Stormo, 1990).

          Les motifs protéiques
 
          La définition des motifs protéiques se représente généralement de deux manières, soit par la détermination d'une séquence consensus qui est généralement complexe (avec des ambigu•tés à certaines positions et des sous-séquences séparées par des régions variables), soit en fournissant directement sous forme d'alignement multiple, toutes les portions de séquences qui ont servi à l'élaboration du consensus.

          Pour établir une séquence consensus, on peut réunir toutes les séquences appartenant à une même famille (par exemple, les cytochromes ou les kinases). On recherche ensuite les zones spécifiques qui peuvent être considérées comme caractéristiques de ces séquences, ceci en s'aidant des données disponibles dans la littérature et si possible d'experts de la famille considérée. Les motifs ainsi obtenus sont alors systématiquement recherchés dans une banque de séquences protéiques pour estimer leur fiabilité qui repose sur le nombre de faux positifs et de faux négatifs identifiés. Une bonne définition doit minimiser ces deux nombres. C'est une des méthodes qu'utilise Amos Bairoch pour constituer la banque de motifs protéiques PROSITE (Bairoch, 1993). On peut également utiliser pour définir un motif protéique une méthode globale qui, à partir d'un grand ensemble hétérogène de séquences, permet de regrouper des séquences possédant le même motif. Cette démarche est appliquée pour établir la base PRODOM (Sonnhammer et Kahn, 1994). Les séquences de la base Swissprot sont comparées deux à deux avec le programme BLAST pour permettre de regrouper tous les segments protéiques similaires. On parle ici de domaine protéique qui caractérise statistiquement une famille de protéines. Ces domaines peuvent être employés comme motifs spécifiques pour savoir si une nouvelle séquence s'apparente ou pas à l'un de ces domaines. Enfin, comme pour les séquences nucléiques, on peut aussi effectuer un alignement multiple des régions qui caractérisent une fonction et en déduire un motif consensus protéique.

          La deuxième manière de définir un motif protéique est de fournir l'ensemble des sous-séquences qui ont servi à établir ou à valider le motif consensus. Ainsi la base BLOCKS (Henikoff et Henikoff, 1991) donne sous forme d'alignements multiples sans insertion-délétion (ou blocs) les sous- séquences de Swissprot qui correspondent à des régions conservées. Ces régions sont des segments protéiques trouvés durant l'analyse de groupes spécifiques de protéines comme les kinases. L'intérêt d'une telle définition est qu'elle donne pour chaque position le degré de conservation ou de variabilité des acides aminés concernés. Par contre, pour certaines signatures protéiques, composées de plusieurs segments séparés par des régions de longueurs variables, elle nécessite la considération de plusieurs blocs.

          Finalement, on peut considérer qu'il existe principalement deux façons de représenter l'information contenue dans les motifs, une assez résumée qui est la séquence consensus et l'autre qui permet de considérer les variations à chaque position qui sont les matrices consensus pour les séquences nucléiques et la présentation sous forme d'alignements multiples pour les protéines.
 

2.4.4 Les algorithmes de recherche de motifs

          Comme nous l'avons décrit ci-dessus, les motifs peuvent être définis principalement de deux manières différentes. Des algorithmes ont donc été développés pour exploiter chacun de ces deux types de définition.
 

          Les algorithmes exploitant des motifs consensus
 
          Lorsque les motifs recherchés sont des motifs simples, c'est-à-dire peu dégénérés, comme les sites de coupures des enzymes de restriction ou certains signaux très conservés, les algorithmes utilisés sont généralement ceux développés pour les recherches de similitude entre deux séquences, le motif étant considéré comme une des deux séquences à comparer. Les algorithmes utilisant une matrice de points comme le programme DIAGON de Staden et les programmes de recherche d'identité sont donc assez souvent employés. Si l'on veut introduire la notion d'insertion-délétion, l'algorithme dérivé de celui de Needelman et Wunsch adapté au traitement de séquences de longueur très différente est souvent utilisé. Celui-ci est identique dans le principe à un alignement global mais permet de considérer chaque position d'une séquence longue comme étant un point de départ d'alignement avec une séquence courte (cf. la recherche d'alignements optimaux). On pourra ainsi localiser dans une grande séquence la position où le motif s'aligne le mieux.

          Si le motif recherché est beaucoup plus dégénéré et complexe, ou si la recherche s'effectue sur plusieurs séquences, alors il vaut mieux utiliser des programmes qui reprennent les algorithmes de base de comparaison de séquences mais qui ont été adaptés et optimisés pour rechercher des motifs complexes. Ces programmes considèrent généralement un motif complexe comme étant une collection de motifs simples qu'il faut rechercher sur une séquence. Il en existe de nombreux. Par exemple, pour accélérer la recherche de motifs simples dans les séquences nucléiques, le programme PATTERN (Cockwell et Giles, 1989) construit une matrice d'identité du motif recherché et le programme FASTPAT (Prunella et al., 1993) utilise une compression des caractères représentant les séquences.
 

          Les algorithmes exploitant des tables de fréquences
 
          Lorsqu'un motif nucléique est défini sous forme de table de fréquences ou de probabilités, on calcule pour chaque fragment de la séquence à analyser un score. Celui-ci est déterminé en sommant les valeurs trouvées dans la table selon les bases rencontrées dans le fragment étudié et les positions considérées (Stormo, 1990). Il existe en fait une correspondance entre ce score et la probabilité de trouver le motif recherché à la position déterminée par le fragment. Plus le score est élevé, plus le segment analysé a des chances de correspondre au motif recherché. Une estimation de la signification du score peut être faite en considérant les valeurs maximales et minimales théoriques données par la table et les valeurs maximales et minimales observées sur la séquence (Figure 19). Une visualisation graphique des résultats est souvent très représentative des potentialités qu'il existe de trouver un motif le long d'une séquence (Figure 20). En fait, l'intérêt principal de cette méthode réside dans la possibilité de prendre en compte une certaine similitude par rapport à un motif consensus. La plupart des logiciels possédant un ensemble de méthodes d'analyse de séquences proposent ce genre de programmes pour rechercher différents signaux nucléiques sur une séquence. Nous pouvons citer par exemple le programme MATRIX SEARCH (Chen et al.,1995) qui détermine des scores sur la séquence analysée en sommant des valeurs logarithmiques calculées à partir d'une matrice de pondération, du nombre de séquences utilisées pour établir la matrice, de la longueur du motif recherché et de la fréquence génomique des bases.

          Si le motif est défini par un alignement protéique, la méthode utilisée est celle dite d'une comparaison par profil (Gribskov et al., 1987 ; Gribskov et al., 1990). Elle consiste à convertir l'alignement multiple en une table qui reflète la probabilité pour chaque acide aminé de se trouver à une position particulière du motif, tout en considérant les propriétés mutationelles des acides aminés selon une matrice de substitution comme la matrice de Dayhoff. Cette table est appelée le profil du motif. Elle correspond en fait à une matrice de pondération particulière. Des méthodes basées sur une extension de l'algorithme de Smith et Waterman (1981) permettent ensuite d'aligner une séquence avec ce profil. Le principal intérêt de cette méthode est qu'elle permet l'introduction d'insertion-délétion dans la recherche tout en gardant une souplesse dans la définition du consensus. Beaucoup de programmes sont dérivés de ce type d'approche. Le programme PROFILESEARCH en est l'application direct (Gribskov et al., 1990). Nous pouvons citer également le programme SCRUTINEER (Sibbald et Argos, 1990) qui permet de combiner avec la comparaison du profil d'autres critères comme la présence de structures secondaires ou la distance qui sépare des sous-motifs, le programme PATMAT (Wallace et Henikoff, 1992) qui possède une bonne interface utilisateur mais qui ne considère pas l'introduction d'insertion-délétion durant la comparaison avec le profil, ceci pour diminuer le temps de recherche, ou encore le programme BLOCKSEARCH (Fuchs, 1993) qui recherche sur une séquence protéique l'ensemble des blocs protéiques contenus dans la base BLOCK convertis en profil.
 

2.4.5 Vers un formalisme plus complet de la caractérisation des motifs nucléiques

          La complexité des structures primaires est très inégale entre les acides nucléiques composés d'un alphabet de quatre lettres et les protéines composées d'un alphabet de vingt lettres. Cette situation engendre forcément des disparités que l'on retrouve au niveau des éléments et des méthodes de description des motifs. Par exemple, la structure primaire d'un motif protéique est souvent suffisante pour caractériser un site biologiquement actif, même si celui-ci est ambigu à certaines positions. C'est d'ailleurs pour cette raison que l'utilisation à grande échelle, de méthodes de recherche de similarité à travers les banques, donne des résultats intéressants dans l'identification de motifs protéiques conservés. Par contre, la faible complexité des motifs nucléiques conduit à une définition, en terme de structure primaire, souvent insuffisante. De ce fait, pour les séquences nucléiques, les définitions et les méthodes de repérage de motifs que nous venons de décrire constituent un formalisme de base qu'il est souvent nécessaire d'étoffer. Ceci est d'autant plus vrai pour les sites impliqués dans des systèmes de régulation complexes comme notamment les sites nucléiques de fixation protéique. D'autres critères ont donc une importance et doivent être pris en compte pour affiner la définition du motif. On peut, par exemple, considérer la localisation du site ou le degré d'affinité de la protéine régulatrice pour le site de fixation. On peut également rechercher des structures particulières qui peuvent s'associer au site comme des zones symétriques ou palindromiques. Ces éléments supplémentaires doivent non seulement être intégrés systématiquement dans les définitions et les recherches mais également dans le formalisme de base des motifs. Or ces formalismes de base ne permettent pas toujours d'intégrer tous les critères nécessaires à une bonne description. Par exemple, les tables de fréquences considèrent que les positions du motif sont indépendantes les une par rapport aux autres, empêchant ainsi des considérations de symétrie ou prenant difficilement en compte l'exclusion d'une base à une position précise. L'ensemble de ces réflexions montre qu'il est souvent nécessaire de développer des outils adaptés aux particularités des signaux étudiés, en mettant au point des protocoles qui intègrent le maximum d'informations décrites dans les définitions et qui utilisent si possible plusieurs méthodes d'analyse de séquences.

© CITI2, DSI 1997