Algorithmes et programmes de comparaison de séquences

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

Sommaire

1. Définitions

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

3. Diversité des programmes - spécificité selon le type de données analysées

4. Programmes d'alignement local

a. Préambule

b. Programme FASTA

 

c. Les programmes BLAST (Basic Local Alignment Search Tool)

5. Programme d'alignement multiple progressif : Clustal W

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

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

8. 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 : processus par lequel deux (ou n) séquences sont comparées afin d'obtenir le plus de correspondances (identités ou substitutions conservatives) possibles entre les lettres qui les composent.
  • 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.

Indel gap alignement

indel :

  • "in" = insertion

  • "del" = délétion

insertion deletion alignement

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".

identite substitution alignement

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

  • soit la substitution d'un caractère par un autre, c'est-à-dire une mutation
  • soi l'introduction d'un "gap"

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.

Retour haut de page

 

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 chanes 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.


Algorithme de Needleman & Wunsch

alignement global optimal de 2 séquences

Algorithme de Smith & Waterman

alignement local optimal de 2 séquences

Algorithme de Needleman & Wunsch

Algorithme de Smith & Waterman

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(xi,yj) : valeur obtenue partir de la matrice de substitution pour les nucléotides ou les acides aminés (xi,yj) correspondant la position (i,j) de la matrice. C'est donc le score correspondant l'alignement des lettres xi et yj.

Ce score prend, par exemple, les valeurs suivantes :

  • identité : +3
  • non identité : -1
  • s(xi,-) et s(-,yj) 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


Application : alignement de la séquence 1 = ACGCT avec la séquence 2 = ACT

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 cote : -5
  • celui du C de la séquence 2 avec l'insertion d'un second gap de la séquence 1 cote : -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
  j 0 1 2 3
i   - (gap) A C T
0 - (gap) 0 -5 -10 -15
1 A -5 3 -2 -7
2 C -10 -2 6 1
3 G -15 -7 1 5
4 C -20 -12 -4 0
5 T -25 -17 -9 -1

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.

 
Seq1 A C G C T
Seq2 A - - C T

 

Seq1 A C G C T
Seq2 A C - - T

Retour haut de page

 

3. Diversité des programmes - spécificité selon le type de données annalysées

Voir l'extrême diversité des programmes.

Type de séquences

Protéines ou acides nucléiques (ADN et/ou ARN) ou les deux

Type d'alignement Local ou global
Accessibilité Serveur Web ou implémenté sur l'ordinateur (lignes de commandes)
Spécialisation de plus en plus prononcée du champs d'application des algorithmes / programmes
  • recherche dans des bases de données
  • alignement de séquences 2 à 2 ("paiwise alignment")
  • alignement de séquences multiples
  • analyse de génome
  • recherche de motifs (sous-séquences spécifiques "signature") : ScanProsite
  • alignement de millions de courtes séquences (voir les nouvelles technologies de séquençage trs haut débit)
  • modélisation de structures homologues et superposition de structures 3D de protéines ("homology modeling"- "protein threading")
  • ...
Les "benchmarks" sont de vastes ensembles de données (homogènes, curées, testées) qui permettent de comparer les performances d'algorithmes / programmes. Exemples de "benchmarks":
  • BAliBASE : le premier "benchmark" construit d'alignements de séquences protéiques
  • HOMSTRAD ("HOMologous STRucture Alignment Database") : curated database of structure-based alignments for homologous protein families.
  • PFAM ("Protein FAMilies") : contient toutes les familles de protéines identifiées (environ 14.000 en 2012). Chacune est représentée par un alignement multiple des séquences de la famille considérée auquel est adjoint un profil HMM ("Hidden Markov Model").
  • Affycomp : pour l'analyse de l'expression de gènes - puces à ADN Affymetrix
  • "The Protein Classification Benchmark collection" : pour l'annotation fonctionnelle par apprentissage machine

Figure ci-contre : comparaison des performances de plusieurs programmes d'alignement de séquences

Bleu : efficacité / Orange : rapidité (échelle log)

Programme score d'efficacité temps de calcul
Probcons 79.4% 2.7 jours
T-Coffee 79.4% 2.7 jours
Mafft (linsi) 81.6% 1.2 heures
Kalign 74.3% 3 minutes !

Etape algorithme Fasta

Source : Thompson et al. (2011)

Les programmes sont de plus en plus spécifiques du type de données biologiques traitées ou du type d'analyse effectuée :

  • 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
  • analyse de paramètres physico-chimiques d'acides aminés de protéines
  • séquences consensus conservées ("pattern")
  • recherche de motifs structuraux
  • analyse du niveau de transcription des gènes
  • annotations
  • ...

Illustration : la comparaison de structures et la modélisation par homologie

On a de plus en plus d'informations qui tendent à démontrer que le nombre de repliements des protéines dans la nature est limité (quelques milliers). On peut donc regrouper les protéines selon le type de repliement qu'elles adoptent. Voir les bases de données CATH et SCOP, par exemple.

Remarque : les protéines dites "intrinsèquement non structurées" sont à part.

Le préalable de la modélisation par homologie ("homology modeling"- "protein threading") est de disposer d'au moins une protéine dont la structure 3D a été déterminée. Elle sert de "modèle" pour modéliser la structure 3D potentielle d'une protéine pour laquelle on ne dispose que de la séquence. Cette séquence doit bien sûr être proche (homologue) de celle de la protéine modèle. Il faut donc d'abord effectuer des alignements de séquences.

  • Exemple de logiciel / interface Web qui renvoie un fichier au format PDB : ESyPred3D.
  • Exemples d'autres programmes de modélisation structurale par homologie :
    1. DeepView
    2. Chimera
    3. MolIDE

Figure ci-contre : Procédure de "PyMod" qui intègre divers types de données et d'analyses :

  • recherche dans une base de données de similarités (de séquences et de structures) avec la séquence requête
  • alignement multiple de séquences sur la base d'homologies de structures
  • modélisation de structures 3D par homologie avec le logiciel Modeller.

Chaque "bloc de procédure" est indépendant des autres : on peut donc, par exemple, effectuer un alignement multiple de séquences sans recherche préalable dans une base de données.

Source : Bramucci et al. (2012)

Etape algorithme Fasta

Retour haut de page

 

4. Programmes d'alignement local

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 sont 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.

b. Programme FASTA - Pearson & Lipman (1988)

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 algorithme Fasta

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.

Etape algorithme Fasta parametre

Interprétation des résultats

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

  • 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é

Retour haut de page

 

c. Les programmes BLAST (Basic Local Alignment Search Tool) - Altschul et al. (1990)

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

Les différents programmes 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. Voir aussi "Primer - BLAST".
Program Word Size DUST Filter Setting Expect Value
Standard blastn 11 On 10
Search for short and near exact matches 7 Off 1000

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.
Program Word Size SEG Filter Expect Value Score Matrix
Standard protein BLAST 3 On 10 BLOSUM62
Search for short and near exact matches 2 Off 20000 PAM30
  • 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.
First sequence Second Sequence Program
Nucleotide Nucleotide blastn or tblastx
Nucleotide Protein blastx
Protein Nucleotide tblastn
Protein Protein blastp
  • 11. DELTA-BLAST ("Domain Enhanced Lookup Time Accelerated BLAST") : Une recherche rapide de type RPS-BLAST permet de construire un profil PSSM ("Position Specific Scoring Matrix") puis de rechercher ce PSSM dans une base de données BLAST. Les résultats de DELTA-BLAST peuvent servir de point de départ pour une recherche de type PSI-BLAST.  
  • 12. 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 ("Position specific iterative BLAST").
  • 13. Smart-BLAST : recherche séquence de protéines contre bases de données.

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
Biegert A. & Soding J.(2009) "Sequence context-specific profiles for homology searching" Proc Natl Acad Sci USA 106, 3770 - 3775


Choix des différentes bases de données de séquences de protéines
Bases de données Description
nrNon-redundant GenBank CDS translations + PDB + SwissProt + PIR + PRF, excluding those in env_nr.
refseqProtein sequences from NCBI Reference Sequence project.
swissprotLast major release of the SWISS-PROT protein sequence database (no incremental updates).
patProteins from the Patent division of GenBank.
monthAll new or revised GenBank CDS translations + PDB + SwissProt + PIR + PRF released in the last 30 days.
pdbSequences derived from the 3-dimensional structure records from the Protein Data Bank.
env_nrNon-redundant CDS translations from env_nt entries.
Smart v4.0 663 PSSMs from Smart, no longer actively maintained.
Pfam v11.0 7255 PSSMs from Pfam, not the latest.
COG v1.00 4873 PSSMs from NCBI COG set.
KOG v1.00 4825 PSSMs from NCBI KOG set (eukaryotic COG equivalent).
CDD v2.05 11399 PSSMs from NCBI curated cd set.

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 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)

Application :

  • Aller à BLAST
  • dans la fenêtre du haut ("Enter accession number(s)") : entrer le numéro d'accession AAC05356
  • choisir PHI-BLAST et dans la fenêtre qui apparaît, entrer le profil : DSD (caratéristique des protéines LEA de la classe 4)

Complément sur PSI-Blast

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 affiné 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 de probabilités correspondant :

           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.

Naumoff D.G. & Carreras M. (2009) "PSI Protein Classifier: a new program automating PSI-BLAST search results" Molecular Biology (Engl Transl) 43, 652 - 664

Profils et "Position Specific Scoring Matrice" (PSSM)

 

La construction de ces profils est basée sur la fréquence de chaque résidu d'acide aminé à une position spécifique d'un alignement multiple.

Profils et Position Specific Scoring Matrice PSSM)

  • Colonne 1 : fréquence (A, 1) = 0/5 = 0 ; fréquence (G, 1) = 5/5 = 1 ; ...
  • Colonne 2 : fréquence (A, 2) = 0/5 = 0 ; fréquence (H, 2) = 5/5 = 1 ; ...
  • ...
  • Colonne 15 : fréquence (A, 15) = 2/5 = 0,4 ; fréquence (C, 15) = 1/5 = 0,2 ; ...

Certaines fréquences sont égales à 0 du fait du nombre de séquence dans l'alignement multiple. Une telle fréquence pourrait entraîner une "exclusion" de l'acide aminé concerné à cette position.

On contourne ce biais en ajoutant une "petite valeur" à toutes les fréquences observées. Cette faible "fréquence non-observée" s'appelle un "pseudo-count". En reprenant l'exemple précédent avec un "pseudo-count" de 1 :

  • Colonne 1 : f' (A, 1) = (0+1)/(5+20) = 0,04 ; f' (G, 1) = (5+1)/(5+20) = 0,24 ; ...
  • Colonne 2 : f' (A, 2) = (0+1)/(5+20) = 0,04 ; f' (H, 2) = (5+1)/(5+20) = 0,24 ; ...
  • ...
  • Colonne 15 : f' (A, 15) = (2+1)/(5+20) = 0,12 ; f' (C, 15) = (1+1)/(5+20) = 0,08 ; ...

La fréquence de chaque acide aminé déterminée à chaque position est comparée à la fréquence à laquelle chaque acide aminé est attendu dans une séquence au hasard. On fait l'hypothèse que chaque acide aminé est observé avec une fréquence identique dans une séquence au hasard.

Le score est calculé à partir du logarithme du rapport (fréquences observées) / (fréquences attendues) : scoreij = log (f'ij / qi)

où :

  • scoreij est le score pour le résidu i à la position j
  • f'ij est la fréquence relative pour le résidu i à la position j, corrigée par les "pseudo-count"
  • qi est la fréquence relative attendue pour le résidu i dans une séquence au hasard
Ci-contre : la matrice PSSM "Position Specific Scoring Matrice" complète calculée à partir de l'exemple précédent.

Position Specific Scoring Matrice

La matrice PSSM est ensuite appliquée à la séquence requête en utilisant une "fenêtre glissante".

A chaque position, un score PSSM est ca lculé en sommant les scores de toutes les colonnes.

Le plus haut score est retenu.

Construction matrice PSSM

Position Specific Scoring Matrice PSSM

Position Specific Scoring Matrice PSSM

Source figures : Pagni M. (2003) "An introduction to Patterns, Profiles, HMMs and PSI-BLAST" / SIB Course
Conclusion PSSM
Avantages Inconvénients
  • Bonne méthode pour de courtes régions conservées.
  • Approche statistique (basée sur la taille des banques) / interprétation des résultats sur la base d'une "e-value".
  • Insertions et délétions interdites avec les matrices PSSm . Sinon, il faut utiliser des "profils généralisés".
  • Les séquences correspondant à de longues regions ne peuvent être décrites avec cette méthode.

A utiliser pour modéliser de courtes régions avec une forte variabilité mais de longueurs constantes.

Outils :

Bases de données :

  • "Prosite" : Database of protein domains, families and functional sites
  • "PRINTS": PSSM database
  • "Pfam": protein domain database
  • "SMART ": protein domain database
  • "ProDom ": protein domain database
  • "InterPRO ": protein "signatures" database

Application à PSI-Blast

1. Une recherche standard BLAST est effectuée contre une base de données en utilisant une matrice de substitution.

2. Une matrice PSSM est construite automatiquement à partir d'un alignement multiple des séquences ayant le plus haut score ("hits") dans cette première recherche BLAST.

  • positions trés conservées : scores élevés
  • positions faiblement conservées : scores faibles

3. La matrice PSSM remplace la matrice initiale et on effectue une 2ème recheche BLAST.

4. Les étapes 3 et 4 sont répétées et à chaque fois, les séquences nouvellement trouvées sont ajoutées afin de construire une nouvelle matrice PSSM.

5. On considère que le programme PSI-BLAST a convergé quand aucune nouvelle séquence n'est ajoutée.

Retour haut de page

 

5. Programme d'alignement multiple progressif : Clustal W

La complexité des algorithmes de programmation dynamique croit de faon 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.

Etape 1

  • 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.

Etape de l'algorithme ClustalW

Source : La Base de Connaissances en Bio-informatique

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

Retour haut de page

 

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

L'apprentissage machine est un processus par lequel un ordinateur accrot 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.

Modele Markov cache transition

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.

Le modèle de Markov caché ci-contre contient 3 états :

  • losanges verts : une insertion
  • carrés rouges : un appariement - mésappariement
  • ronds bleus : une délétion

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).

Modele Markov cache

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

PFAM arabidopsis

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

Retour haut de page

 

7. 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équences de longueurs m et n, 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 :

K et λ

"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.

E-Value = K.m.n. eS (1)

"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 :

S' = λ.S - Ln K / Ln 2

E-Value = m.n. 2-S'


"E-Value"

Interprétation

Plus la "E-Value" est faible, plus l'alignement est significatif.

Pour des séquences requêtes trés courtes, la "E-Value" est élevée, même pour les séquences dont l'alignement obtenu est significatif.

< 1 e-100

La probabilité de trouver par hasard un alignement comme celui qui est obtenu est inférieure 1 e-100
--> appariement exact : même séquence, même origine

1 e-100 < E < 1 e-50 séquences quasiment identiques : allèles, mutations, espèces voisines
1 e-50 < E < 0,1 une éventuel lien entre la séquence requête et celles qui ont été trouvées
> 0,1 séquences de l'alignement rejeter, sans lien avec la séquences requête

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).

P = e-E

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

P-Value = 1 - e-E

E P-Value
10 0,99995
5 0,993
très faible valeurs de "E-Value" et de "P-Value" peu près égales

BLAST renvoie la "E-Value" plutot que la "P-Value".

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.

 

8. Liens Internet et références bibliographiques

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

Aller au site

"Sequence Manipulation Suite" : ensemble d'applications Java pour manipuler les séquences. Trés bien fait et didactique pour se familiariser rapidement. Superbe Aller au site
"An introduction to Bionformatics Algorithms" Aller au site

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

NCBI - Blast
Needleman, S.B. & Wunsch, C.D. (1970) "A general method applicable to the search for similarities in the amino acid sequence of two proteins" J. Mol. Biol. 48, 443 - 453

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

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

BLAST

Article

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

FASTA

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

ClustalW

Article

Corpet, F. (1988) "Multiple sequence alignment with hierarchical clustering" Nucleic Acids Res. 16, 10881 - 10890 Multalin
Sonnhammer et al. (1998) "Pfam: multiple sequence alignments and HMM-profiles of protein domains" Nucleic Acids Res. 26, 320 - 322 PFAM

Article

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. & Carreras M. (2009) "PSI Protein Classifier: a new program automating PSI-BLAST search results" Molecular Biology (Engl Transl) 43, 652 - 664

Edgar, R.C. (2004) "MUSCLE: multiple sequence alignment with high accuracy and high throughput" Nucleic Acids Res. 32, 1792 - 1797

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

Thompson et al. (2011) "A Comprehensive Benchmark Study of Multiple Sequence Alignment Methods: Current Challenges and Future Perspectives" PLoS ONE 6, e18093

Article

Article

Article

Eswaret et al. (2006) "Comparative protein structure modeling using MODELLER" Curr. Protoc. Bioinformatics Chapter 5, unit 5.6

Bramucci et al. (2012) "PyMod: sequence similarity searches, multiple sequence-structure alignments, and homology modeling within PyMOL" BMC Bioinformatics 13, S2 

Braberg et al. (2012) "SALIGN: a web server for alignment of multiple protein sequences and structures" Bioinformatics 28, 2072 - 2073

 

Article

Article

CATH ("Class, Architecture, Topology and Homology")

SCOP ("Structural Classification Of Proteins")

CATH

SCOP

 

Valid XHTML 1.0 Transitional         Flux RSS Retour haut de page