Expressions régulières
Principe de l'algorithme de BLAST - Programme PHI-Blast

Flux RSS

 

1. Les expressions régulières

2. Principe de l'algorithme de BLAST

3. PHI-blast ("Pattern Hit Initiated-Blast")

4. Liens Internet et références bibliographiques

 

1. Les expressions régulières

Elles sont aussi appelées expressions rationnelles (en anglais : "regular expressions", abrégé "regexp", acronyme re).

C'est un moyen d'écrire de manière "compacte" un ensemble (qui peut-être extrêmement vaste) de séquences de caractères : par exemple des séquences de nucléotides ou d'acides aminés.

Voir l'exemple des toxines de serpent.

L'écriture des expressions régulières suit des règles précises et utilise des caractères spéciaux (les métacaractères) qui agissent comme des opérateurs.

regular expression reguliere program sequence comparison local alignment similarity search BLAST PhiBlast substitution matrix PAM BLOSUM score biochimej

L'expression régulière [AY]-x-H-x(4)-{DE} (figure ci-dessus) se lit :

  • [AY] = soit A, soit Y
  • puis : x = n'importe quel acide aminé
  • puis : H = H
  • puis : x(4) = 4 fois n'importe quel acide aminé
  • puis : {DE} = n'importe quel acide aminé sauf D et E

Voir un cours sur le langage Python et les expressions régulières.

Retour haut de page

Il existe de nombreux opérateurs (ou métacaractères) pour les expressions régulières. En voici quelques exemples.

  • L'opérateur "." signifie "n'importe quel caractère", c'est-à-dire n'importe quel acide aminé.
  • L'opérateur "[ ]" signifie "n'importe quel caractère parmi ceux entre les crochets".
    Exemple : [FGKM] n'importe quel acide aminé parmi F, G, K et M.
  • L'opérateur "^" est un métacaractère de positionnement ou d'ancrage. Il signifie "commence par ". C'est donc la position N-terminale dans le cas d'une séquence d'acides aminés.
    Exemple : ^HHH ou ^H{3} recherche 3 résidus histidine en position N-terminale.
    Exemple : ^[A-DX] signifie "commence par A, B, C, D ou X".
    Remarque : l'opérateur "<" est aussi utilisé pour désigner le premier caractère d'une chaîne de caractères.
  • L'opérateur "$" est un métacaractère de positionnement ou d'ancrage. Il signifie "finit par ". C'est donc la position C-terminale dans le cas d'une séquence d'acides aminés.
    Exemple: GHS[DE]K$ signifie "finit par la séquence GHS[DE]K".
    Remarque : l'opérateur ">" est aussi utilisé pour désigner le dernier caractère d'une chaîne de caractères.
  • L'opérateur "[^]" (^entre crochets) signifie l'exclusion.
    Exemple 1: [^KLY] signifie tous les acides aminés sauf K, L et Y.
    Exemple 2: ^[^G] signifie "qui ne commence pas par G" (expression régulière complémentaire de l'opérateur "^").
  • L'opérateur "|" signifie "ou". Exemple : NPN|NPY signifie "contient NPN ou NPY ou les deux"

Les métacaractères "*", "+" , "{ }" et "?" sont des opérateurs de quantification ou quantificateur.

  • L'opérateur "*" après un caractère (ou un groupe de caractères) recherche ce caractère zéro fois ou plus.
  • L'opérateur "+" signifie au moins 1 fois le caractère (ou le groupe de caractères) qui le précède. Exemple : E+ représente "E" ou "EE" ou "EEE" ou ...
  • L'opérateur "{ }" :
    E{4} : 4 fois E
    E{1,3} : 1 à 3 fois E
    E{,5} : 0 à 5 fois E
    E{7,} : au moins 7 fois E
  • L'opérateur "?" signifie 0 ou 1 fois un caractère (en d'autre terme, l'existence facultative de ce caractère).
    Exemple: CWPN?L$ signifie qu'il peut y avoir ou non le caractère N dans le motif CWP - L (situé en position C-terminale puisqu'il y a l'opérateur $).

Le méta-caractère "\" (back-slash) est utilisé comme caractère d'échappement.

L'opérateur "\w" signifie tout caractère alpha-numérique : équivaut à [_A-Za-z0-9].
L'opérateur "\W" signifie tout caractère autre qu'alpha-numérique (c'est le contraire de "\w") : équivaut à [^_A-Za-z0-9].

L'opérateur "\d" signifie que la chaîne de caractères est composé uniquement de chiffre : équivaut à [0-9].
L'opérateur "\D" signifie que la chaîne de caractères n'est pas composé de chiffre : équivaut à [^0-9].

Exemple :

L'expression régulière ^ATG[ATGC]{30,1000}A{5,10}$ se traduit par :

  • un codon d'initiation ATG au début de la séquence (opérateur "^" )
  • puis 30 à 1000 ({30,1000}) nucléotides A, T, G ou C (expression [ATGC])
  • puis 5 à 10 fois A ({5,10}) à la fin de la séquence : la queue poly-A (opérateur "$" )

Retour haut de page

Expressions régulières et programmes

On retrouve les expressions régulières dans un très grand nombre de langages de programmation : Perl, Python, PHP, javascript, Ruby, R, XML, ...

Par exemple :

  • POSIX "Portable Operating System Interface" : langage d'expressions régulières lié au langage PHP. Plus simple que PCRE.
  • PCRE "Perl Compatible Regular Expressions" : expressions régulières issues du langage Perl. Plus rapides et performantes que POSIX.

Ci-dessous : exemple d'un programme très simple (langage Python) qui recherche une expression régulière (GA[ATGC]{3}AC) dans une séquence nucléotidique (variable "sequenceADN") avec le module "re" :

import re      # Module "re" (regular expression) de Python
sequenceADN = "ATGACGTACGTACTCAGACGTACGGGTTGACGTACAG"
resultat = re.search(r"GA[ATGC]{3}AC",sequenceADN)      
               # La méthode "search" attend 2 paramètres : 
               # - l'expression régulière (ou motif) à rechercher
               # - la chaîne de caractères (ici la variable "sequenceADN") dans laquelle on recherche ce motif
               # On stocke le résultat dans la variable "resultat"
print(resultat)    # Affichage du résulat de la recherche du motif

Le résultat est : GACGTAC

Retour haut de page

Expressions régulières et bases de données

PROSITE est une base de données de motifs qui utilisent les expressions régulières.

Exemple (PDOC00245) :

  • L'expression régulière G-C-x(1,3)-C-P-x(8,10)-C-C-x(2)-[PDEN] est une signature des toxines de serpents.
  • Les 4 cystéines sont impliquées dans des ponts disulfure.

Voir la syntaxe des expressions régulières PROSITE.

ScanProsite : c'est un programme qui permet d'analyser les séquences de protéines de l'utilisateur pour y détecter des concordances avec la collection de motifs contenus dans la base de données PROSITE ou par rapport à des modèles définis par cet utilisateur.

Retour haut de page

2. Principe de l'algorithme du programme BLAST

BLAST recherche des régions de similarité locale entre des séquences nucléotidiques ou d'acides aminés. Ce programme compare les séquences à des bases de données de séquences et il calcule la signification statistique des correspondances.

BLAST est utile pour déduire des relations fonctionnelles et évolutives entre séquences ainsi ou pour identifier les membres des familles.

Retour haut de page

Soit la séquence requête ("query") arbitraire d'acides aminés (code à 1 lettre) : ARGHLTFYIFQLM

1ère étape : cette séquence est découpée en mots d'une taille ("word size") fixe W (= 2 ou 3 pour le programme "BLAST protein"). Pour une taille plus petite, le temps de recherche est plus important.

Exemple d'un mot de taille 3 issu de la séquence requête : TFY.

Pour chacun de ces mots, une liste de mots similaires est créée à l'aide d'une matrice de substitution.

word length hit program sequence comparison local alignment similarity search BLAST substitution matrix PAM BLOSUM biochimej

Cette matrice permet de calculer un score élémentaire pour la substitution d'un acide aminé par un autre.

Par exemple, la comparaison du mot TFY avec le mot TDY donne avec la matrice de substitution PAM 250 (voir ci-dessous) :

  • T changé en T => score (T, T) = 3; F changé en D => score (F, D) = - 6; Y changé en Y => score (Y, Y) = 10
  • Somme de ces scores élémentaires = 3 - 6 + 10 = 7

Si la valeur de la somme des scores élémentaires est supérieure à une valeur appelée score seuil, le mot est conservé dans la liste. Par exemple :

  • mots retenus : TDY, TWY, THY, TAY
  • une certaine valeur de seuil du score
  • mots non retenus (score du mot < score seuil) : TRY, TEY

Retour haut de page

2ème étape : chaque mot de la liste des mots similaires fait l'objet d'une recherche de similarité (appelé "hit") dans l'ensemble des séquences de la base de données ou du jeu de données testé. Un hit est également défini par une valeur de score qui doit être supérieure à une valeur fixée.

blast database search hit score program sequence comparison local alignment similarity search substitution matrix PAM BLOSUM biochimej

3ème étape : la similarité est étendue à partir du hit, dans les 2 sens le long de la séquence (de la base de données) en cours d'analyse. L'extension s'arrête quand :

  • le score cumulé diminue d'une valeur fixe X par rapport à la valeur maximale précédemment atteinte
  • le score cumulé = 0
  • l'une des deux extrémités de la séquence est atteinte

BLAST high scoring pair HSP program sequence comparison local alignment similarity search substitution matrix PAM BLOSUM biochimej

Finalement, le fragment de séquence le plus long trouvé s'appelle un "High Scoring Pairs" (HSP). Par exemple :

BLAST high scoring pair HSP program sequence comparison local alignment similarity search substitution matrix PAM BLOSUM biochimej

Source : N. Gaedeke - Max Plant Institute

Retour haut de page

La matrice de substitution PAM 250

Une faible valeur dans la matrice indique que l'acide aminé considéré peut être remplacé par un autre (exemple : le tryptophane W remplacé par la cystéine C : -8) et donc que cette partie des séquences est faiblement homologue.

Au contraire, une valeur élevée indique une région présentant une forte homologie des séquences.


A R N D C Q E G H I L K M F P S T W Y V
A 2


















R -2 6

















N 0 0 2
















D 0 -1 2 4















C -2 -4 -4 -5 4














Q 0 1 1 2 -5 4













E 0 -1 1 3 -5 2 4












G 1 -3 0 1 -3 -1 0 5











H -1 2 2 1 -3 3 1 -2 6










I -1 -2 -2 -2 -2 -2 -2 -3 -2 5









L -2 -3 -3 -4 -6 -2 -3 -4 -2 2 6








K -1 3 1 0 -5 1 0 -2 0 -2 -3 5







M -1 0 -2 -3 -5 -1 -2 -3 -2 2 4 0 6






F -4 -4 -4 -6 -4 -5 -5 -5 -2 1 2 -5 0 9





P 1 0 -1 -1 -3 0 -1 -1 0 -2 -3 -1 -2 -5 6




S 1 0 1 0 0 -1 0 1 -1 -1 -3 0 -2 -3 1 3



T 1 -1 0 0 -2 -1 0 0 -1 0 -2 0 -1 -2 0 1 3


W -6 2 -4 -7 -8 -5 -7 -7 -3 -5 -2 -3 -4 0 -6 -2 -5 17

Y -3 -4 -2 -4 0 -4 -4 -5 0 -1 -1 -4 -2 7 -5 -3 -3 0 10
V 0 -2 -2 -2 -2 -2 -2 -1 -2 4 2 -2 2 -1 -1 -1 0 -6 2 4

Retour haut de page

Choix de la base de données de séquences de protéines à fouiller lors de l'utilisation de BLAST

(menu déroulant de l'option "Database" / onglet "Choose search Set")

Base de données Description
Non-redundant protein sequences (nr)
(> 258 millions séquences)
Séquences non redondantes issues de la traduction des séquences codantes ("CDS translations") de GenBank + séquences de la PDB + séquences de SwissProt + séquences de PIR + séquences de PRF à l'exclusion des échantillons environnementaux des projets de séquençage de génomes complets ("whole genome sequencing", WGS).
Reference proteins (refseq_protein)
(> 159 millions séquences)
Séquences de NCBI Reference Sequence project
Model Organisms (landmark) Séquences correspondant aux protéomes issus de plusieurs dizaines de génomes couvrant une large gamme taxonomique.
UniProtKB / Swiss-Prot (swissprot)
(> 473.000 séquences)
Séquences non redondantes issues de UniProtKB/SwissProt.
Patented protein sequences (pataa)
(> 2,4 millions séquences)
Séquences de protéines dérivées de la division des brevets de GenBank.
Protein Data Bank proteins (pdb)
(> 112.000 séquences)
Séquences de protéines dérivées des données de structures tridimensionnelles de la Protein Data Bank.
Metagenomic proteins (env_nr)
(> 9,8 millions séquences)
Séquences de protéines dérivées de données métagénomiques WGS (env_nr).
Transcriptome Shotgun Assembly proteins (tsa_nr)
(> 3,1 millions séquences)
Séquences de protéines dérivées de l'assemblage des séquences du transcriptome.

Aller à l'interface de BLAST.

Retour haut de page

Exemple d'un résultat issu d'une recherche avec BLAST

BLAST high scoring pair HSP program sequence comparison local alignment similarity search substitution matrix PAM BLOSUM biochimej

Alignement local entre la séquence requête ("Query") et l'une des séquences ("Sbjct") trouvées dans la base de données fouillée (N° d'accession : XP_009417953).

  • signe "+" : similarité ("positives")
  • tiret "-" : gap

La valeur "Expect" ou "E-value"

  • Plus cette valeur est faible (plus elle est proche de zéro), plus la concordance entre la séquence requête et la séquence trouvée est significative.
  • Cette valeur diminue de façon exponentielle à mesure que le score (S) des concordances augmente.
  • Point important : le calcul de la valeur de "Expect" prend en compte la longueur de la séquence requête.

Le paramètre "Expect threshold" (seuil de signification statistique, "statistical significance threshold")

  • Il décrit le nombre de résultats que l'on peut "espérer" obtenir par hasard lors de la recherche dans une base de données d'une taille particulière.
  • Il correspond au seuil de signification statistique pour le renvoi des résultats des concordances ("matches") entre la séquence requête et les séquences de la base de données fouillée.

Il se trouve dans la partie "Algorithm parameters", onglet "General Parameters" (en bas de l'interface de BLAST). Sa valeur par défaut est 10 : cela signifie que 10 concordances semblent trouvées par hasard (selon le modèle stochastique de Karlin & Altschul, 1990).

Si la signification statistique attribuée à une concordance est supérieure à la valeur du paramètre "Expect threshold", cette concordance n'apparaît pas dans les résultats.

Voir un complément.

Retour haut de page

3. PHI-BLAST ("Pattern Hit Initiated-BLAST")

C'est un programme de recherche par comparaison de séquences.

  • Il utilise les expressions régulières (syntaxe PROSITE) pour décrire une courte séquence consensus appelée patron ("pattern").
  • PHI-BLAST prend donc en entrée une séquence requête d'une protéine et le pattern défini par une expression régulière. Ce pattern doit être collé dans une fenêtre qui apparaît spécifiquement quand on coche le bouton radio "PHI-BLAST" de l'interface de BLAST.

regular expression reguliere program sequence comparison local alignment similarity search BLAST PhiBlast substitution matrix PAM BLOSUM score biochimej

PHI-BLAST est adapté pour détecter des séquences de protéines qui :

  • Contiennent le pattern (fenêtre "PHI pattern" de la section "Algorithm").
  • Et sont similaires à la séquence requête (fenêtre "Search") dans le voisinage proche du pattern.

Aller à PHI-BLAST : entrer le numéro d'accession 2NBT_A et le motif G-C-x(1,3)-C-P-x(8,10)-C-C-x(2)-[PDEN]

 

4. Liens Internet et références bibliographiques

Regular Expressions

Python regular expressions

Aller au site

Aller au site

Altschul et al. (1990) "Basic local alignment search tool" J. Mol. Biol. 215, 403 - 410

Karlin & Altschul (1990) "Methods for assessing the statistical significance of molecular sequence features by using general scoring schemes" PNAS 87, 2264 - 2268

Altschul et al. (1997) "Gapped BLAST and PSI-BLAST: A new generation of protein database search programs" Nuc. Acids Res. 25, 3389 - 3402

Article

Article

Article

Retour haut de page

Valid XHTML 1.0 Transitional