Des algorithmes de recherche ont été développés pour exploiter chacun des types de représentations des motifs. La diversité des besoins et des représentations des motifs impliquent un grand choix d'outils de recherche de motifs.
Les algorithmes de recherche exploitant des consensus ou des expressions régulières
Avec la représentation du motif sous la forme d'une expression régulière ou d'un consensus, la méthode de recherche est simple car énumérative (effectuée par avec la recherche d'un ensemble de motifs exacts dans une séquence). La similarité entre deux patterns peut être donnée par la distance de Hamming (nombre de positions qui diffèrent) ou de Levenshtein (nombre de substitution, insertion, délétion nécessaires pour transformer une lettre en une autre).
Lorsque les motifs recherchés sont des motifs simples, c'est-à-dire peu dégénérés et nucléiques (comme les sites de coupures des enzymes de restriction ou les codons stop), l'algorithme de Needleman et Wunsh, basé sur la distance de Hamming peut être utilisé. Il a été développé pour les recherches de similitude entre deux séquences. Dans ce cas le motif est alors considéré comme une des deux séquences à comparer.
Par contre, si l'on veut introduire la notion d'insertion-délétion, l'algorithme de Smith et Waterman basé sur la distance de Levenshtein, est parfois utilisé.
Ces deux algorithmes permettent de considérer ainsi chaque position de la séquence longue et de détecter où le motif s'aligne le mieux.
En revanche, dans la plupart des cas les motifs sont long et/ou ambigûs et la recherche s'effectue dans plus de trois séquences. Ces deux méthodes sont trop coûteuses en ressource informatique. en effet ces algorithmes permettant un cacul exact souffrent d'un temps de calcul très important. C'est pourquoi, des heuristiques (méthodes plus rapides mais conduisant à des résultats approchés) ont été développées.
Il est également possible de prétraiter les données en ajoutant des structures de données efficaces comme par exemple l'arbre des suffixes (ex : STAN, RISOTTO). Cela permet de chercher des motifs dans de très longues séquences.
Les algorithmes de recherche exploitant des tables de fréquences ou probabilités et les HMM
Lorsqu'un motif est défini sous la forme d'une table de fréquences, d'une table de probabilités ou d'un modèle de Markov caché, on calcule un score pour chaque fragment de la séquence à analyser. 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 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é.
La façon dont est réalisé le calcul d'un score évaluant une séquence par rapport un motif représenté sous la forme de matrice est présenté ci dessous avec l'exemple de la séquence TACGGATACG:
source : Hélène Touzet,LIFL, Lille
La façon dont est réalisé le calcul d'un score évaluant une séquence par rapport un motif représenté sous la forme de HMM est présenté ci dessous avec l'exemple de la séquence AGT:
source : Hélène Touzet,LIFL, Lille
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. Une visualisation graphique des résultats est très représentative des potentialités qu'il existe de trouver un motif le long d'une séquence.
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.
Les algorithmes de recherche exploitant des alignements multiples
Si le motif est défini par un alignement, 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 profile 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 profile. 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.
Les outils de recherche de motifs
La plateforme Genouest a sélectionné quelques outils parmi les nombreux logiciels existants. Voir les outils >>
<< lien vers l'introduction
Les algorithmes de recherche exploitant des consensus ou des expressions régulières
Avec la représentation du motif sous la forme d'une expression régulière ou d'un consensus, la méthode de recherche est simple car énumérative (effectuée par avec la recherche d'un ensemble de motifs exacts dans une séquence). La similarité entre deux patterns peut être donnée par la distance de Hamming (nombre de positions qui diffèrent) ou de Levenshtein (nombre de substitution, insertion, délétion nécessaires pour transformer une lettre en une autre).
Lorsque les motifs recherchés sont des motifs simples, c'est-à-dire peu dégénérés et nucléiques (comme les sites de coupures des enzymes de restriction ou les codons stop), l'algorithme de Needleman et Wunsh, basé sur la distance de Hamming peut être utilisé. Il a été développé pour les recherches de similitude entre deux séquences. Dans ce cas le motif est alors considéré comme une des deux séquences à comparer.
Par contre, si l'on veut introduire la notion d'insertion-délétion, l'algorithme de Smith et Waterman basé sur la distance de Levenshtein, est parfois utilisé.
Ces deux algorithmes permettent de considérer ainsi chaque position de la séquence longue et de détecter où le motif s'aligne le mieux.
En revanche, dans la plupart des cas les motifs sont long et/ou ambigûs et la recherche s'effectue dans plus de trois séquences. Ces deux méthodes sont trop coûteuses en ressource informatique. en effet ces algorithmes permettant un cacul exact souffrent d'un temps de calcul très important. C'est pourquoi, des heuristiques (méthodes plus rapides mais conduisant à des résultats approchés) ont été développées.
Il est également possible de prétraiter les données en ajoutant des structures de données efficaces comme par exemple l'arbre des suffixes (ex : STAN, RISOTTO). Cela permet de chercher des motifs dans de très longues séquences.
Les algorithmes de recherche exploitant des tables de fréquences ou probabilités et les HMM
Lorsqu'un motif est défini sous la forme d'une table de fréquences, d'une table de probabilités ou d'un modèle de Markov caché, on calcule un score pour chaque fragment de la séquence à analyser. 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 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é.
La façon dont est réalisé le calcul d'un score évaluant une séquence par rapport un motif représenté sous la forme de matrice est présenté ci dessous avec l'exemple de la séquence TACGGATACG:
source : Hélène Touzet,LIFL, Lille
La façon dont est réalisé le calcul d'un score évaluant une séquence par rapport un motif représenté sous la forme de HMM est présenté ci dessous avec l'exemple de la séquence AGT:
source : Hélène Touzet,LIFL, Lille
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. Une visualisation graphique des résultats est très représentative des potentialités qu'il existe de trouver un motif le long d'une séquence.
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.
Les algorithmes de recherche exploitant des alignements multiples
Si le motif est défini par un alignement, 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 profile 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 profile. 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.
Les outils de recherche de motifs
La plateforme Genouest a sélectionné quelques outils parmi les nombreux logiciels existants. Voir les outils >>
<< lien vers l'introduction