Algorithmes et programmes de comparaison de séquences

Interprétation des résultats : E-value, P-value

 

1. Définitions

2. Algorithme de Needleman & Wunsch et algorithme de Smith & Waterman

3. Alignement local

a. Préambule

b. Programme FASTA

c. Programme BLAST (Basic Local Alignment Search Tool)

4. Alignement multiple progressif : programme Clustal W

5. Modèle de Markov caché (Hidden Markov Model - HMM)

6. Interprétation des résultats : E-value, P-value

7. Liens Internet et références bibliographiques

1. Définitions

Il existe 3 grandes classes d'algorithmes de comparaison de séquences :

• méthode de programmation dynamique
• méthode heuristique
• méthode d'apprentissage machine

• alignement local : alignement des séquences sur une partie de leur longueur
• alignement global : alignement des séquences sur toute leur longueur
• alignement optimal : alignement des séquences qui produit le plus haut score possible
• alignement multiple : alignement global de trois séquences ou plus
• brèches ou "gap" : espace artificiel introduit dans une séquence pour contre-balancer et matérialiser une insertion dans une autre séquence. Il permet d'optimiser l'alignement entre les séquences.

• "in" = insertion
• "del" = délétion

similarité : c'est le pourcentage d'identités et/ou de substitutions conservatives entre des séquences. Le degré de similarité est quantifié par un score. Le résultat de la recherche d'une similarité peut être utilisé pour inférer l'homologie de séquences.

homologie : 2 séquences sont homologues si elles ont un ancêtre commun. L'homologie se mesure par la similarité : une similarité significative est signe d'homologie sauf si les séquences présentent une faible complexité.

faible complexité ("low-complexity regions") : régions qui contiennent peu de caractères différents. Exemples : (a) FFFPPPPPVVV, 3 acides aminés différents seulement (région riche en proline) - queue poly-A des ARN. Ces régions posent des problémes dans l'analyse des séquences car elles génèrent un score biaisé.

Exemple de programme qui analyse ce type de régions : "SEG".

mésappariement : non correspondance entre deux lettres. Un mésappariement peut être :

score : un score global permet de quantifier l'homologie. Il résulte de la somme des scores élémentaires calculés sur chacune des positions en vis à vis des deux séquences dans leur appariement optimal. C'est le nombre total de "bons appariements" pénalisé par le nombre de mésappariements.

score élémentaire :

• ADN : la valeur du score élémentaire est de 1 (les deux bases sont identiques, bon appariement) ou de 0 (les deux bases sont différentes, mauvais appariement).
• protéines : cette valeur est extraite d'une matrice de substitution.

2. Algorithme de Needleman & Wunsch et algorithme de Smith & Waterman

Tous deux sont des algorithmes de programmation dynamique utilisés pour obtenir l'alignement global ou local (respectivement) optimal de deux séquences protéiques ou d'acides nucléiques.

La programmation dynamique est une méthode développée par R. Bellman (1955) qui permet de résoudre de nombreux problèmes dont la solution directe n'est pas possible puisque de complexité exponentielle. Exemple : calcul de la distance d'édition entre deux chaînes de caractères (séquences protéiques ou d'acides nucléiques).

La programmation dynamique une méthode de résolution ascendante qui détermine une solution optimale du problème à partir des solutions de tous les sous-problèmes.

L'algorithme de Needleman & Wunsch et l'algorithme de Smith & Waterman se déroulent globalement en deux étapes :

• la construction, ou descente, qui permet de calculer le meilleur score, c'est à dire le coût de la transformation de la première séquence en la seconde (étape de programmation dynamique)
• la construction de l'alignement lui-même, ou remontée

Ces algorithmes n'utilisent pas d'heuristique : il sont donc sensibles mais longs.

La ligne i = 0 et la colonne j = 0 sont initialisées aux valeurs de pénalité des gaps.

La fonction de récurrence ne réinitialise pas la valeur à 0 si aucune valeur positive n'est présente.

La ligne i = 0 et la colonne j = 0 sont initialisées à 0.

N'importe quelle case de la matrice de comparaison peut être un point de départ pour le cacul des scores finaux. Si ce score devient inférieur à zéro, la fonction de récurrence réinitialise la valeur à 0 et la case peut être utilisée comme un nouveau point de départ.

F(i,j) : valeur à la position (i,j) de la matrice.

s(x_i,y_j) : valeur obtenue à partir de la matrice de substitution pour les nucléotides ou les acides aminés (x_i,y_j) correspondant à la position (i,j) de la matrice. C'est donc le score correspondant à l'alignement des lettres x_i et y_j.

Ce score prend, par exemple, les valeurs suivantes :

• identité : +3
• non identité : -1
• s(x_i,-) et s(-,y_j) est la fonction simple de pénalité de l'alignement d'un résidu avec un gap : -5

Remarque : si on opte pour d'autres valeurs, on obtient d'autres alignements optimaux, d'où le choix crucial de la meilleure matrice de substitution lors des alignements.

La fonction de pénalité d'un gap est définie par : f(n) = d + [e . (n-1)], où :

• n = longueur du gap
• d = pénalité d'ouverture d'un gap
• e = pénalité d'extension d'un gap

Exemple : un gap de longueur n = 3, avec une pénalité d'ouverture d = -10 et d'extension e = -2, aura un score de f(3) = -10 + (-2 x 2) = -14

On remplit la 1ère ligne et la 1ère colonne de la matrice qui correspondent à un gap à la 1ère position :

• l'alignement du A de la séquence 2 avec l'insertion d'un gap dans la séquence 1 coûte : -5
• celui du C de la séquence 2 avec l'insertion d'un second gap de la séquence 1 coûte : -5 + -5 = -10
• et ainsi de suite ...

F(1,1) aura pour valeur la valeur maximale de l'une des possibilités suivantes :

• F(0,0) + s(A,A) = 0 + 3 = 3
• F(0,1) + s(A,-) = -5 + -5 = -10
• F(1,0) + s(-,A) = -5 + -5 = -10

F(2,1) aura pour valeur la valeur maximale de l'une des possibilités suivantes :

• F(1,0) + s(C,A) = -5 + -1 = -6
• F(1,1) + s(C,-) = 3 + -5 = -2
• F(2,0) + s(-,A) = -10 + -5 = -15

Et ainsi de suite.

Pour reconstituer l'alignement, on démarre de la dernière case (5,3) et on détermine la case à partir de laquelle cette case a été atteinte :

a. la valeur -1 de la case (5,3) ne peut-être obtenue qu'en ajoutant +3 (soit une identité) à la valeur -4 [(case (4,2)]. Celà correspond à l'alignement du "T" de la séquence 1 avec le "T" de la séquence 2.

b. la valeur -4 de la case (4,2) peut être obtenue de 2 manières :

• en ajoutant +3 (soit une identité) à la valeur -7 [(case (3,1)]. Celà correspond à l'alignement du "C" de la séquence 1 avec le "C" de la séquence 2.
• en ajoutant -5 (soit un gap) à la valeur 1 [(case (3,2)]. Celà correspond à l'alignement du "C" de la séquence 1 avec un gap dans la séquence 2.

c. Et ainsi de suite.

Dés lors, on obtient 2 alignements optimaux qui ont le même score de +1.

a. Préambule

Les méthodes de programmation dynamique permettent de calculer, sous un système de scores donné, l'alignement optimal, global ou local, entre deux séquences en un temps proportionnel au produit des longueurs des deux séquences. Appliquées à une banque de séquences, le temps de calculs de ces méthodes augmente linéairement avec la taille de la banque.

On définit 2 caractéristiques pour une méthode de comparaison de séquences :

• la sensibilité : c'est l'aptitude à détecter toutes les similarités considérées comme significatives et donc à générer le minimum de faux-négatifs.
• la sélectivité : c'est l'aptitude à ne sélectionner que des similarités considérées comme significatives et donc à générer le minimum de faux-positifs.

Les programmes des familles Fasta et BLAST sont des heuristiques qui réduisent le facteur temps en "sacrifiant" un peu de sensibilité. L'un et l'autre simplifient le problème :

• en pré-sélectionnant les séquences de la banque susceptibles de présenter une similarité significative avec la séquence requête
• et en localisant les régions potentiellement similaires dans les séquences

Ces étapes sélectives permettent :

• de n'appliquer les méthodes de comparaison, coûteuses en temps, qu'à un sous-ensemble des séquences de la banque
• et de restreindre le calcul de l'alignement optimal à des parties des séquences

Cette logique de recherche plus rapide dans son exécution, comporte donc le risque d'éliminer des séquences qui ont une similarité plus difficile à détecter ou d'aboutir à des alignements sub-optimaux.

La sensibilité et la sélectivité se réfèrent à une notion de résultat significatif ou non. Les programmes mesurent une signification statistique des résultats par rapport à un modèle aléatoire : un résultat est considéré comme significatif si la probabilité de l'obtenir par hasard est trés faible.

Les systèmes de score partent du postulat que les résultats les plus significatifs du point de vue statistique soient aussi les plus pertinents du point de vue biologique. Or ce n'est pas toujours le cas car des résultats biologiquement intéressants peuvent être non significatfs sur un plan statistique.

En d'autres termes, la signification biologique d'une similarité entre des séquences n'est pas forcément estimable sur la seule valeur d'un score.

• analyse de génomes ou assemblage d'EST en contigs
• construction d'arbres phylogénétiques
• détection de SNP ("Single Nucleotide Polymorphism")
  
• recherche dans des banques généralistes ou spécialisées
• paramètres physico-chimiques
• séquences consensus conservées ("pattern") - PHI-Blast ("Pattern Hit Initiated BLAST")
• existence de motifs structuraux
• homologie et superposition de structures tridimensionnelle ("homology modeling"- "protein threading" - ESyPred3D) ...

Le programme ne considère que les séquences présentant une région de forte similitude avec la séquence recherchée. Il applique ensuite localement à chacune de ces meilleures zones de ressemblance un algorithme d'alignement optimal.

La codification numérique des séquences, c'est-à-dire la décomposition de la séquence en courts motifs (nommés uplets) transcodés en entiers, confère à l'algorithme l'essentiel de sa rapidité.

Etape 1 (figure ci-contre)

• Les régions les plus denses en identités entre les deux séquences sont recherchées. Ces régions sont appelés points chauds ou "hot spots".
• C'est le paramètre "ktup" qui détermine le nombre minimum de résidus consécutifs identiques. Généralement : ktup = 2 pour les protéines - ktup = 6 pour l'ADN.
• Recherche des meilleures diagonales : plusieurs "hot spots" dans une même région génère des diagonales de similarité sans insertion ni délétions. Ces diagonales sont les régions ayant le plus de similarité. Elles sont représentées par un graphique de points ou "dotplot".

Lorsqu'une séquence est comparée à une base de données, la première étape est effectuée pour chaque séquence présente dans cette base de données.

Etape 2

• Les dix meilleures diagonales sont réévaluées à l'aide d'une matrice de substitution et les extrémités de ces diagonales sont coupées afin de conserver les régions ayant les plus hauts scores seulement. Cette recherche de similitude est faite sans insertions ni délétions.
• Le score le plus élevé obtenu est appelé le score "init1". Il est attribué à la région ayant le plus fort score parmi les 10 analysées.

Etape 3

• Les diagonales trouvées à l'étape 1 dont le score dépasse un certain seuil ("cutoff"), sont reliées entre elles pour étendre la meilleure similarité.
• Ces nouvelles régions contiennent des insertions et/ou des délétions
• Le score des nouvelles régions est calculé en combinant le score des diagonales reliées diminué d'un score de pénalité de jonction des diagonales.
• Le score le plus élevé obtenu à cette étape s'appelle le score "initn".
• Cette étape permet d'éliminer les segments peu probables parmi ceux définis à l'étape précédente.

Etape 4 (figure ci-contre)

• La région initiale qui a généré le score"init1" est de nouveau évaluée avec un algorithme de programmation dynamique sur une fenêtre de résidus dont la largeur est déterminée par le paramètre "ktup". Le nouveau score est "opt".
• Les séquences de la base de données sont classées selon leurs scores "initn" ou "opt".
• Les séquences sont alignées avec la séquence cible à l'aide de l'algorithme de Smith & Waterman : le score final est le score Smith & Waterman.

Interprétation des résultats

La sortie de FASTA se décompose en trois parties : Histogramme

• colonne 1 : échelle de valeurs
• colonne 2 : nombre de séquences dans la banque donnant un "z-score" = valeur
• colonne 3 : nombre de séquences dans la banque donnant une "E-value" = valeur

• "init1" = "initn" = "opt" : 100% de similarité
• "initn" > "init1" : plusieurs régions de similarité reliées par des gaps
• "initn" > "opt" : pas de similarité

Méthode heuristique qui utilise la méthode de Smith & Waterman.

C'est un programme qui effectue un alignement local entre deux séquences nucléiques ou protéiques. La rapidité de BLAST permet la recherche des similarités entre une séquence requête et toutes les séquences d'une base de données.

Voir une description de l'algorithme de BLAST

Acides nucléiques

• 1. "MEGABLAST" est l'outil de choix pour identifier une séquence.

• 2. "Standard nucleotide BLAST" est mieux adapté à la recherche de séquences similaires mais pas identiques à la séquence requête.

• 3. L'option "Search for short and near exact matches" de "Nucleotide BLAST" est adapté à la recherche d'amorces ("primer") ou de courts motifs nucléotidiques.

Protéines

• 1. Il n'y a pas d'équivalent de "MEGABLAST" pour les requêtes protéiques.

• 2. "Standard protein BLAST" est le mieux adapté à la recherche de séquences protéiques.

• 3. "PSI-BLAST (Position-Specific Iterated-BLAST)" est adapté à la recherche de similarité fine entre séquences protéiques. A utiliser quand une recherche BLAST a échoué ou renvoyé des résultats tels que : "hypothetical protein" or "similar to...".

• 4. "PHI-BLAST (Pattern-Hit Initiated-BLAST)" est adapté à la recherche de séquences protéiques qui contiennent un motif spécifié par l'utilisateur ET sont similaires à la séquence requête dans le voisinage proche du motif.

• 5. "Search for short nearly exact matches" de "Protein BLAST" est adapté à la recherche de similarité dans le cas de courtes séquences peptidiques. Les valeurs des paramètres "Expect value cutoff" et "word size" sont modifiés la matrice PAM30 (plus stringente) remplace la matrice BLOSUM62. Une séquence requête inférieure à 5 acides aminés est déconseillée.

• 6. "Nucleotide query - Protein db [blastx]" est adapté pour trouver des séquences protéiques similaires à celles codées par une séquence requête nucléotidique. Trés utile pour l'analyse massive de séquence d'EST ("Expressed Sequence Tags").

• 7. "Protein query - Translated db [tblastn]" est adapté pour trouver des régions codantes des protéines homologues dans un ensemble de séquences nucléotidique non-annotées. Trés utile pour l'analyse de séquence d'EST et de brouillons de génomes (HTG).

• 8. "Conserved Domain Database (CDD)": ce service utilise le programme "Reverse Position Specific BLAST (RPS-BLAST)" pour identifier des domaines protéiques conservés en comparant la séquence requête contre des bases d'alignements de domaines conservés obtenues avec des matrices de scores de position spécifiques "Position specific scoring matrices (PSSMs)". Les bases de données sont : "SMART", "PFAM" et "LOAD" ("Library Of Ancient Domains").

• 9 "Conserved Domain Architecture Retrieval Tool (CDART)" permet d'examiner la structure en domaine de toutes les protéines de la base de données BLAST. Plus sensible qu'une recherche BLAST classique car CDART est lié au programme RPS-BLAST ("Reverse Position-Specific BLAST") qui est lui-même une "variation" du programme "PSI-BLAST ".

• 10. "BLAST 2 Sequences" permet la comparaison de 2 séquences requête. Ne recquiert pas de format particiliers des séquences. La séquence entrée en second est considérée comme la "base de donnée" contre laquelle est effectuée la comparaison.

Les programmes FASTA et BLAST suivants sont équivalents :

• Comparaison de séquence nucléique / banque nucléique : FASTA - BLASTN
• Comparaison de séquence protéique / banque protéique : FASTA - BLASTP
• Comparaison de séquence protéique / banque nucléique (traduite dans les 6 phases) : TFASTA - TBLASTN

Complément sur PSI-Blast

Altschul S. F. et al. (1997) "Gapped BLAST and PSI-BLAST: a new generation of protein database search programs" Nucleic Acids Res. 25, 3389 - 3402
Naumoff D.G. and Carreras M. (2009) "PSI Protein Classifier: a new program automating PSI-BLAST search results" Molecular Biology (Engl Transl) 43, 652 - 664

PSI-Blast est adapté :

• à la recherche de similarité fine entre séquences protéiques
• la détection de membres éloignés d'une famille protéique
• l'étude de la fonction de protéines inconnues

PSI-Blast construit un profil à partir de l'alignement multiple des séquences qui ont obtenu les meilleurs scores avec la séquence requête.
Ce profil est comparé à la banque interrogée et est raffiné au fur et à mesure des itérations. Ainsi, la sensibilité du programme est augmentée.

Un profil est un tableau des fréquences observées des acides aminés (ou nucléotides) à chaque position dans un alignement multiple.
Exemple (très simple) d'alignement multiple de 2 séquences de 4 acides aminés :

      DWKD
      DWNG

Le profil correspondant (en probabilités) :

            1      2      3      4
      D    1.0    0.0    0.0    0.5
      G    0.0    0.0    0.0    0.5
      K    0.0    0.0    0.5    0.0
      N    0.0    0.0    0.5    0.0
      W    0.0    1.0    0.0    0.0

Ce qui ce signifie :
- probabilité de trouver D en position 1 = 1.0 (un D en première position de chaque séquence)
- probabilité de trouver G en position 1 = 0.0 (aucun G en première position)
- etc ...

L'utilisation d'un profil permet une recherche beaucoup plus sensible de séquences homologues « éloignées » que l'utilisation d'une séquence seule car le profil contient de l'information sur la variabilité des différentes positions parmi les protéines connues. En contrepartie un profil est moins spécifique qu'une simple séquence seule.

Si on utilise PSI-Blast sur un sous ensemble particulier de séquences, il est probable que l'on ne trouve pas tous les homologues, surtout si leur séquence est peu conservée par rapport à la séquence requête. Pour améliorer la sensibilité de la détection des homologues « éloignées », il est préférable d'effectuer un alignement avec PSI-Blast sur une banque de séquences plus grande.

Mais la sensibilité est diminuée si la banque de données est trop grande puisque la fréquence d'observation d'un score particulier (la "E-value") augmente avec la taille de la banque de données. Or, pour un alignement de 2 séquences, plus le score est petit, plus la probabilité que ces 2 séquences soient homologues est grande.

Il est donc préférable de chercher d'abord dans une banque "nettoyée" ("curated") comme la base de données non-redondante ("nr") où toutes les séquences identiques ont été éliminées sauf un exemplaire. Si plusieurs séquences sont dans cette banque, on peut calculer un profil et l'utiliser pour effectuer une nouvelle recherche dans ce sous ensemble. On augmente ainsi la sensibilité de la recherche d'homologues.

Complément sur PHI-Blast

Ce programme prend en entrée une séquence requête protéique et un motif défini par une expression régulière.

PHI-Blast est adapté à la recherche de séquences protéiques qui contiennent un motif spécifié par l'utilisateur (fenêtre "PHI pattern" de la section "Algorithm") ET sont similaires à la séquence requête (fenêtre "Search") dans le voisinage proche du motif.

La syntaxe du motif doit suivre la syntaxe de PROSITE.

• Exemple 1 de syntaxe de motif : [KR]-[LIM]-K-[DE]-K-[LIM]-P-G
• Exemple 2 de syntaxe de motif : S(4)-[SD]-[DE]-x-[DE]-[GVE]-x(1,7)-[GE]-x(0,2)-[KR](4)

Un nouveau programme : CS-BLAST ("context-specific BLAST")

Pour chaque acide aminé, CS-BLAST tient compte de l'influence de la séquence en acides aminés qui l'entoure, sur la probabilité de mutation de l'acide aminé en question.

En 2 itérations de recherche, CS-BLAST donne un résultat plus sensible que 5 itérations avec PSI-Blast.

Biegert A. and Soding J. (2009) "Sequence context-specific profiles for homology searching" Proc Natl Acad Sci USA 106, 3770 - 3775

4. Alignement multiple progressif : programme Clustal W

La complexité des algorithmes de programmation dynamique croit de façon exponentielle avec le nombre de séquences à traiter, ce qui rend difficile leur utilisation pour plusieurs séquences.

Pour contourner ce problème, plusieurs heuristiques ont été proposées. Le programme ClustalW utilise un algorithme d'alignement multiple progressif.

• La similarité de chaque séquence est évaluée par rapport à toutes les séquences.
• Un score de similitude est calculé pour chaque paire de séquences selon un alignement approximatif global rapide : seuls les fragments exactements appariés et les diagonales avec un grand nombre d'appariements sont pris en compte.
• On obtient ainsi une matrice de distances.

Etape 2

• Un dendrogramme ("guide tree") est construit : il s'agit d'un arrangement traduisant les relations globales de parenté entre les séquences. Cet arbre phylogénique est construit selon la méthode "Neighbour-Joining".
• Il indique l'ordre à partir duquel l'alignement multiple graduel sera établi.

Etape 3

• Le programme construit un premier alignement multiple (par programmation dynamique ou par une méthode semblable à celle de FASTA): les 2 séquences les plus similaires servent de base pour l'élaboration de cet alignement multiple primaire.
• On obtient une première séquence consensus qui est alignée avec la 3e séquence la plus similaire.
• Toutes les séquences (des plus proches aux plus distantes) sont ainsi progressivement ajoutées par construction de consensus successifs jusqu'à l'alignement multiple final.

Le risque le plus important en ce qui concerne les alignements multiples progressifs est qu'un alignement erroné à l'étape initiale engendre une erreur qui est amplifiée dans l'alignement multiple global.

Le programme ClustalW comporte des particularités qui minimisent ce risque :

• le poids des séquences est ajusté
• des matrices de substitution appropriées sont utilisées selon l'étape de l'alignement et la divergence des séquences
• l'introduction de gap est favorisée à des endroits spécifiques

Aller à "Sequence Manipulation Suite".

Générer 10 séquences ADN aléatoires de 20 paires de base.

Faire un copier-coller des 2 premières dans un éditeur de texte.

Item : "Random Sequences".

Choisir : "-Random DNA Sequence"

Aller à "Clustal W" - EBI et coller les 2 séquences dans la fenêtre de soumission.

Lancer l'application. Quel est le résultat et pourquoi ?

Modifier le nom des séquences dans l'éditeur de texte et coller les 2 séquences dans la fenêtre de soumission.

Modifier les paramètres des gap et le choix des matrices. et relancer l'application.

Voir l'alignement : "Alignment file" - Lien "clustalw - xxxxxxxxx.aln"

Voir le score :"Output file" - Lien : "clustalw - xxxxxxxxxxx.output"

5. Modèle de Markov caché (Hidden Markov Model - HMM)

L'apprentissage machine est un processus par lequel un ordinateur accroît ses connaissances et modifie son comportement à la suite de ses expériences et de ses actes passés. L'ordinateur apprend.

Plusieurs méthodes d'apprentissage machine :

• les réseaux de neurones
• les "support vector machine"
• les k plus proches voisins
• l'algorithme "Expectation Maximisation" ...
• le modèle de Markov caché

Le modèle de Markov caché est un processus stochastique. Il est apparenté aux automates probabilistes. Un tel automate est composé :

• d'états
• de transitions entre états. A chaque transition est associé un symbole d'un alphabet fini. Ce symbole est généré à chaque fois que la transition est empruntée.
• de probabilités de transitions

Une séquence d'événements consécutifs est donc caractérisée par le fait que la probabilité pour chaque événement de se produire ne dépend que du résultat de l'événement qui le précède.

Exemple : probabilité d'observer un "U" après avoir observé "CCAAU".

Le terme caché signifie que l'on observe des lettres générées par le modèle mais pas la séquence des états qui génére ces lettres.

Le système nécessite une phase d'apprentissage sur un ensemble initial de séquences afin de calculer les probabilités de transitions.

On applique ensuite ce système sur une nouvelle séquence et on détermine son appartenance à l'ensemble de départ.

Une probabilité est associée à chaque caractère pour l'état [appariement - mésappariement]. C'est la partie cachée de ce modèle puisque l'état dans lequel est le modèle ne définit pas la sortie (END).

Source : La Base de Connaissances en Bio-informatique

La base de données PFAM est un recueil de domaines complets de protéines (motifs conservés mais aussi moins conservés et insertions / délétions, figure ci-contre) obtenus à partir :

• de profils basés sur des modèles de Markov cachés (HMM - profiles)
• d'alignements multiples générés à partir de ces profils

Les autres logiciels utilisant les HMM - profiles : PSI-Blast, SAM, HMMER, BLOCKS - Meta-MEME, ...

6. Interprétation des résultats : E-value, P-value

La signification des alignements est un point capital. Elle repose sur des valeurs spécifiques mais aussi et (peut-être surtout ?) sur une inspection visuelle du résultat par l'expérimentateur et donc sur son expertise quant aux séquences sur lesquelles il travaille.

Cette signification est évaluée statistiquement 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.

"Sequences producing a significant alignment" : séquences ayant un alignement significatif. A chacune de ces séquences sont attribués plusieurs valeurs spécifiques qui sont une indication de la qualité de l'alignement.

"High-Scoring Segment Pairs" ou "HSP" : les couples de séquences les plus longues dont les scores ne peuvent être améliorés après extension d'un segment initial (Voir une description de l'algorithme de BLAST).

a. "E-Value" pour un score S (E = Expected)

Pour des séquence de longueurs m et m, la statistique d'un score HSP est caractérisée par 2 paramètres de la distribution des valeurs extrêmes produites par l'algorithme de Smith-Waterman :

"E-Value" est le nombre d'alignements différents que l'on peut espérer trouver dans les banques avec un score supérieur ou égal à S.

C'est donc la probabilité d'observer au hasard ce score dans les banques de séquences considérées.

"bit score S'" : ce score est dérivé du score brut S de l'alignement après normalisation.

Il est utilisé pour comparer des scores provenant de recherches différentes :

b. "P-Value" pour un score S

Le nombre d'HSP avec un score supérieur ou égal à S et obtenus par hasard suit une distribution selon la loi de Poisson.

La probabilité de ne trouver aucun HSP avec un score supérieur ou égal à S est :

E est la "E-Value" pour le score S calculée avec l'équation (1).

Donc, la probabilité de trouver au moins 1 HSP avec un score supérieur ou égal à S est :

En effet, il est plus facile de comprendre la différence entre "E-Value" = 5 et "E-Value" = 10 qu'entre "P-Value" = 0.993 et 0.99995.

"Cours d'autoformation en bioinformatique" - Université Paris 5 : Trés bien fait et didactique. Avec exercices corrigés d'autoévaluation.

"The Statistics of Sequence Similarity Scores" - Altschul, S.F.

Smith, T. & Waterman M. (1981) "Identification of common molecular subsequences" J. Mol. Biol. 147, 195 - 197

BLAST : Altschul, S.F., Gish, W., Miller, W., Myers, E.W. & Lipman, D.J. (1990) "Basic local alignment search tool" J. Mol. Biol. 215, 403 - 410

FASTA : Pearson, W.R. & Lipman, D.J. (1988) "Improved tools for biological sequence comparison" Proc. Natl. Acad. Sci. USA 85, 2444 - 244

Clustal W : Thompson, J.D., Higgins, D. G. & Gibson , T. J. (1994) "CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice" Nucleic Acids Res. 22, 4673 - 4680