Expressions régulières
Principe de l'algorithme de 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").

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 un exemple : toxines de serpent.

L'écriture des expressions régulières suit des règles précises et utilise des caractères spéciaux 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

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 ([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.

Exemple d'un programme très simple en langage Python pour la recherche d'une expression régulière dans une séquence nucléotidique appelée "sequenceADN" :

import re          # Emulation du 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)    # Affichge du résulat de la recherche du motif

Le résultat est : GACGTAC

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

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.

Aller à BLAST (NCBI).

Retour haut de page

Soit la séquence requête ("query") : ARGHLTFYIFQLM

1ère étape : cette séquence est découpée en mots d'une taille ("word size") fixe W (= 2 ou 3 pour 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. Par exemple, la matrice de substitution PAM 250 (voir ci-dessous).

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

Cette matrice permet de calculer un score pour la substitution d'un acide aminé par un autre. Par exemple, la comparaison du mot TFY avec le mot TDY donne :

  • 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 des scores élémentaires = 7

Si la valeur de la somme des scores élémentaires est supérieure à une valeur appelée seuil du score, 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 < seuil du score) : TRY, TEY

Retour haut de page

2ème étape : haque 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 fixe.

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 deux 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
  • une extrémité de l'une des deux séquences est atteinte

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

Finalement, le fragment 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

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

Le paramètre « expect »

Il correspond au seuil de signification statistique (« statistical significance threshold ») 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 qui est fouillée.

En d'autres termes, le paramètre « expect » 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 :

  • plus la valeur du paramètre « expect » est faible (plus elle est proche de zéro), plus la concordance est significative.
  • la valeur de ce paramètre diminue de façon exponentielle à mesure que le score (S) des concordances augmente.
  • point important : le calcul du paramètre « expect » prend en compte la longueur de la séquence requête.

La valeur par défaut du paramètre « expect » 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 », cette concordance n'apparaît pas dans les résultats.

Retour haut de page

Choix des différentes bases de données de séquences de protéines - interface BLAST
Bases de données Description
nr
(> 187 millions séquences)
Non-redundant GenBank CDS translations + PDB + SwissProt + PIR + PRF
excluding environmental samples from WGS projects.
refseq
(> 128 millions séquences)
Protein sequences from NCBI Reference Sequence project.
Model Organisms (landmark) Proteomes from 27 genomes spanning a wide taxonomic range.
UniProtKB / Swiss-Prot
(> 471.000 séquences)
Non-redundant UniProtKB/SwissProt sequences.
Patented protein sequences (pat)
(> 2,3 millions séquences)
Protein sequences derived from the Patent division of GenBank.
Protein Data Bank proteins (pdb)
(> 104.000 séquences)
Sequences derived from the 3-dimensional structure records from the Protein Data Bank.
Metagenomic proteins (env_nr)
(> 7 millions séquences)
Proteins from WGS (Whole Genome Shotgun sequencing) metagenomic projects (env_nr).
Transcriptome Shotgun Assembly proteins (tsa_nr)
(> 2,6 millions séquences)
Transcriptome Shotgun Assembly (TSA) sequences.

Aller à l'interface BLAST.

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

BLAST ("Basic Local Alignment Search Tool") et PHI-BLAST (NCBI - NIH)

"The PROSITE database of protein domains, families and functional sites"

BLAST

PROSITE

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