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 expression régulières suit des règles précises et utilise des caractères spéciaux qui agissent comme des opérateurs.

L'expression régulière [AY]-x-H-x(4)-{DE} (figure ci-contre) 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

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

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

En voici quelques exemples.

  • L'opérateur "x" ou "." 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 "$" )

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

import re                                                                # Importation de la bibliothèque ou module "re".
       dna = "ATGACGTACGTACTCAGACGTACGGGTTGACGTACAG"
       m = re.search(r"GA[ATGC]{3}AC", dna)            # La fonction "search" attend 2 paramètres : l'expression régulière (sous la forme d'une chaîne)
                                                                              # et la chaîne de caractères dans laquelle on recherche cette expression régulière.
                                                                              # On stocke le résultat dans la variable m
print(m.group())

Le résultat est : GACGTAC

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 des séquences de protéines pour détecter des concordances avec la collection de motifs de la base de données PROSITE ou par rapports à des modèles définis par l'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).

Let's consider the query sequence : ARGHLTFYIFQLM

First step : this query sequence is cut in words of fixed size W.

  • Values of W = 2, 3, 6 / default value : W = 6 for protein.
  • Note that the smaller the word size, the slower the search will be.
  • Example of a word of size 3 from the query sequence : TFY.

For each of these words, a list of similar words is created, using a substitution matrix. For example, the PAM 250 substitution matrix (see below).

This matrix allows to calculate a score for substitution of an amino acid into another one.

For example, comparison of the word TFY with the similar word TDY gives :

T changed into T gives the score (T,T) = 3

F changed into D gives the score (F,D) = -6

Y changed into Y gives the score (Y,Y) = 10

scores sum = 7

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


If the value of the score sum is higher than a fixed value (the score threshold),
the word is retained in the list.
words retained TDY
TWY
THY
TAY
a score threshold
words not retained
(word's score < score threshold)
TRY
TEY

Second step

Each word from the list of similar words is searched for similarity (a hit) against all sequences of the database.

A hit is also defined by a score value that must be higher than a fixed value.

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

Third step : the similarity is extended starting from the hit, in both directions along the matching sequence.

The extension will be finished when either :

  • the cumulated score decreases of a fixed amount "X" compared to the maximum value previously reached
  • the cumulated score becomes = 0
  • one extremity of one of the two sequences is reached

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

Finally, the longest fragment found is called a High Scoring Pairs (HSP).

An example of HSP.

Source : N. Gaedeke - Max Plant Institute

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

PAM 250 substitution matrix

A low value in the matrix indicates that the amino acid considered can be replaced by the other (e.g., tryptophane W replaced by cystéine C : -8) and therefore that this part of the sequence is weakly homologuous.

On the contrary, a high value indicates a region with high homology.


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

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

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

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

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

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.

 

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