L2 - BI4U2 - Bioinformatique appliquée
Définition des concepts

Table des matières


Matrices de substitution

Une matrice de substitution associe un score à chaque paire de résidus. Ce score (appelé log-odds ou lod score) indique la vraisemblance qu'a cette paire de résidus de se retrouver dans une alignement de séquences homologues.

En termes évolutifs, le lod-score peut être interprété comme une indication de l'acceptabilité de la substitution. Ce concept d'acceptabilité a été proposé par Margret Dayhoff en 1978, sur base de l'analyse d'une collection d'alignements de séquences protéiques. L'idée sous-jacente est que certaines substitutions ont de plus fortes chances de perturber la fonction de la protéine.

Par exemple:

En analysant une collection d'alignements entre paires de protéines homologues, Margret Dayhoff réalise que certaines paires de résidus se retrouvent plus fréquemment alignées que ce qu'on s'attendrait à observer au hasard. Elle définit le lod-score, qui mesure cette propriété.

LOD-score (log-odds)

Le log-odds score est le logarithme de vraisemblance de trouver une substitution au sein d'un alignement entre séquences homologues.

Illustrations: voir diapos

si,j = sj,i = log2(fi,j/(fifj))

Le produit fifj indique la fréauence relative attendue au hasard, c'est-à-dire la probabilité d'aligner les résidus i et j si on les avait tirés aléatoirement, de façon indépendante, suivant leurs fréquences respectives.

Le rapport fi,j/(fifj) indique le niveau de sur- ou sous-représentation de la substitution i, j au sein des alignements. Il prend une valeur

Le LOD est la transformation logarithmique (en base 2) de ce rapport. Il est donc

La série de matrices de substitution BLOSUM

Henikoff et Henikoff (1982) définissent une série de matrices de substitution sur base d'alignements locaux multiples ("blocks" d'alignements). Les matrices de cette série portent toutes le préfixe BLOSUM (pour "BLOck SUbstitution Matrix"), suivi d'un suffixe indiquant le pourcentage d'identité minimal entre séquences utilisées pour construire la matrice.

La matrice BLOSUM62 a été construite à partir de blocks de séquences protéiques alignées présentant un pourcentage d'identité ≥62%.

La matrice BLOSUM30 a été construite à partir de blocks de séquences protéiques alignées présentant un pourcentage d'identité ≥30%. Elle est donc adaptée à des alignemements de protéines évolutivement distantes.

Il existe indubitablement une correspondance entre les substitutions fréquentes (marquées en vert) des matrices BLOSUM62 et BLOSUM30. Cependant, certaines substitutions obtiennent des scores différents selon la distance évolutive, et peuvent même passer d'un score négatif (substitutions contre-sélectionnées) à un score positif (substitutions dites "conservatives" ou "acceptées"). Il est donc crucial de choisir, pour chaque alignement, une matrice BLOSUM dont le suffixe correspond approximativement au taux de conservation (identités) entre protéines alignées.

Ceci pose évidemment un problème de circularité: comment peut-on savoir quelle matrice choisir avant d'avoir réalisé l'alignement ? La solution la plus simple est de commencer par faire un alignement avec une matrice de conservation "moyenne" (typiquement, la BLOSUM62, ce qui explique sa popularité), puis de choisir la meilleure matrice sur base du premier alignement, pour faire l'alignement final.

Comment choisir la bonne matrice de substitution pour réaliser un alignement ?

Quand on aligne deux ou plusieurs protéines, il est important de choisir la matrice de substitutions la plus appropriée, c'est-à-dire celle qui correspond le mieux possible leur taux d'identité.

Pour la série de matrices BLOSUM (Henikoff & Henikoff, 1992), le numéro de matrice indique le pourcentage d'identité minimal pour lequel la matrice est appropriée.

Par exemple,

Bien entendu, cette règle pose un problème de circularité: pour pouvoir aligner des protéines, il faut choisir la matrice appropriée sur base de leur pourcentage d'identité, mais pour connaître ce pourcentage, il faut déjà disposer d'un alignement.

Une règle pratique assez simple consiste à suivre le protocole suivant:

  1. Effectuer un premier alignement avec une matrice intermédiaire (typiquement, la BLOSUM62).
  2. Sur base du résultat de cet alignement, évaluer le pourcentage d'identité des protéines, et identifier la matrice correspondante dans la série BLOSUM.
  3. Si cette matrice n'est pas la BLOSUM62, refaire l'alignement en choisissant cette fois la bonne matrice.
  4. Vérifier si l'alignement final donne plus ou moins le même taux d'identités que l'alignement initial (et, en tout cas, si le taux d'identité final correspond à la matrice utilisée).
[Retour à la table des matières]

Dot plot

Le dot plot est une représentation graphique qui indique les régions identiques ou similaires entre deux séquences biologiques. La première séquence entrée est projetée sur l'axe horizontal, la seconde sur l'axe vertical.

Illustrations: voir diapos

[Retour à la table des matières]

Alignements par paires

Un alignement par paire indique les régions similaires entre deux séquences biologiques (nucléiques ou peptidiques).

Les gaps

Afin d'aligner au mieux les résidus identiques ou similaires (scores positifs dans les matrices de substitutions), les programmes d'alignement peuvent insérer des espacements (gaps) au sein des séquences alignées. Les gaps sont représentés par des traits d'union "-".

      R  L  A  S  V  E  T  D  M  P   -  -  -  -  -  L  T  L  R  Q  H
      T  L  T  S  L  Q  T  T  L  K   N  L  K  E  M  A  H  L  G  T  H

Les gaps peuvent être interprétés selon deux scénarios évolutifs alternatifs:

  1. perte des résidus par délétion dans la séquence présentant le gap;
  2. gain de résidus par insertion dans l'autre séquence.

L'alignement d'une paire de séquences ne permet pas de départager ces deux possibilités. On définit le terme indel (in extenso: insertion ou délétion) pour indiquer cet événement évolutif de nature indéterminé qui est à l'origine du gap.

Comment calculer le score brut d'un alignement ?

Pour calculer le score brut (raw score) d'un alignement, on associe à chaque paire de résidus alignés le score correspondant dans la matrice de substitutions.

Dans l'exemple ci-dessous, nous avons calculé le score de l'alignement suivant avec la matrice BLOSUM62.

      R  L  A  S  V  E  T  D  M  P   -  -  -  -  -  L  T  L  R  Q  H
      T  L  T  S  L  Q  T  T  L  K   N  L  K  E  M  A  H  L  G  T  H
     -1 +4 +0 +4 +1 +2 +5 -1 +2 -1                 -1 -2 +4 -2 -1 +8

On applique un traitement particulier pour assigner un score aux gaps: on définit (de façon quelque peu arbitraire) deux pénalités.

  1. Pour la première position de chaque gap, on applique la pénalité d'ouverture de gap (ci-dessous: -10).
  2. Pour les résidus suivants du gap, on applique la pénalité d'extension de gap (ci-dessous: -1).
  3. Note: on peut, de façon optionnelle, décider d'assigner ou non une pénalité aux gaps terminaux (en début et en fin d'alignement).

On peut dès lors calculer le score brut (raw score) en additionnant, tout au long de l'alignement, des scores d'identité, de substitution, d'ouverture et d'extension de gap.

      R  L  A  S  V  E  T  D  M  P   -  -  -  -  -  L  T  L  R  Q  H
      T  L  T  S  L  Q  T  T  L  K   N  L  K  E  M  A  H  L  G  T  H
     -1 +4 +0 +4 +1 +2 +5 -1 +2 -1 -10 -1 -1 -1 -1 -1 -2 +4 -2 -1 +8 = 7

Enfin, pour faciliter la lecture de l'alignement, on insère entre les deux séquences alignées un ligne de symboles.
| identités  
: substitutions conservatives (celles qui ont un score positif dans la matrice de substitution)
. substitutions non-conservatives (celles qui ont un score strictement négatif dans la matrice de substitution)
- gaps

      R  L  A  S  V  E  T  D  M  P   -  -  -  -  -  L  T  L  R  Q  H
      .  |  .  |  :  :  |  .  :  .                  .  .  |  .  .  |
      T  L  T  S  L  Q  T  T  L  K   N  L  K  E  M  A  H  L  G  T  H
      -1 +4 +0 +4 +1 +2 +5 -1 +2 -1 -10 -1 -1 -1 -1 -1 -2 +4 -2 -1 +8 = 7 

Scores dérivés d'un alignement  par paires

Au-delà du score brut, on peut dériver une série de scores qui fournissent des informations complémentaires concernant la qualité de l'alignement.

Longueur de l'alignement Nombre de colonnes de l'alignement. Attention, la longueur de l'alignement diffère généralement de celle des séquences alignées, pour différentes raisons:
  • Dans un alignement global, la présence de gaps alternés dans les deux séquences peut générer un alignement plus log que chacune des séquences alignées.
  • En cas d'alignement local, l'alignement peut se limiter à un fragment des protéines alignées, et peut donc être plus court que chacune des séquences alignées. Notons que ceci n'est pas forcé: selon les cas, un algorithme d'alignement local peut éventuellement arriver à un alignement qui recouvre les séquences alignées sur toute leur longeur, et, s'il y a des gaps, ce alignement sera plus long que les protéines alignées.
Nombre d'identités nombre de positions où sont alignés deux résidus identiques
Pourcentage d'identités Nombre d'identités divisé par la longueur totale de l'alignement.
Nombre de similarités ("positives") Nombre de positions de l'alignement caractérisées par un score positif dans la matrice de substitution (identités et substitutions "conservatives").
Pourcentage de similarités Nombre de similarités divisé par la longueur totale de l'alignement.
[Retour à la table des matières]

Alignement global versus local

Un alignement global recouvre les séquences alignées sur l'ensemble de leur longueur, tandis qu'un alignement local peut se limiter à un fragment de chaque séquence.

L'intérêt de l'alignement global est de révéler les événements évolutifs (délétions, insertions, substitutions) sur l'ensemble de la longueur des séquences d'intérêt. On recourt par exemple aux alignements globaux quand on veut étudier l'évolution d'une famille de protéines dans son ensemble.

Les alignements locaux révèlent les segments conservés entre deux ou plusieurs séquences. On les utilise par exemple pour extraire un domaine conservé à partir d'une famille de séquences homologues.

[Retour à la table des matières]

BLAST: une famille d'outils pour la recherche de séquences par similarités

BLAST est une méthode de recherche de séquences par similarité qui effectue des alignements locaux entre une séquence requête (query sequence) et chacune des séquences d'une base de données (par exemple UniprotKB, qui recouvre 40 millions de séquences protéiques).

Pour pouvoir effectuer cette tâche énorme dans un temps raisonnable, BLAST se base sur une approche heuristique: les séquences de la base de données sont préalablement indexées dans un "dictionnaire de mots", qui dresse la liste des séquences de la base de données contenant chaque oligomère (oligopeptide pour les bases de données de protéines, oligonucléotides pour les séquences nucléiques) d'une taille donnée.

Quand on lance une recherche, BLAST commence par analyser la séquence requête en dressant la liste des oligomères présents. Il consulte ensuite le dictionnaire pour extraire la liste des séquences de la base de données qui contiennent ces mots, et lance un alignement par paire avec ce sous-ensemble des séquences.

Cette heuristique est plus rapide que les méthodes d'alignement par paire par programmation dynamique (Needleman-Wunsch en alignement global, Smith-Waterman en alignement local), mais elle présente un certain risque de louper des similarités.

Les modalités de BLAST

BLAST permet non seulement de comparer des séquences de même type (protéine versus protéine, acide nucléique versus acide nucléique), mais également d'effectuer des recherches avec une séquence requête d'un type (peptidiques ou nucléiques) dans une base de donnée de l'autre type. Pour ces recherches croisées, les séquences nucléiques sont traduites dans les 6 cadres de lectures (3 cadres de lecture par brin), et le résultat est analysé avec l'algorithme blastp.

Requête Base de données Logiciel Exemples d'applications
séquence peptidique séquence peptidique blastp
  • En partant d'une protéine de fonction connue, collecter les protéines similaires dans la base de données Uniprot afin de constituer la famille de protéine supposées homologues.
  • séquence nucléique séquence nucléique blastn
  • Comparer les séquences d'ARNm aux séquences génomiques.
  • Aligner un ARN d'interférence (ARNi) sur un génome pour détecter ses cibles potentielles.
  • séquence nucléique (traduite dans les 6 cadres) séquence peptidique blastx
  • Après avoir séquencé un morceau d'ADN, chercher des fragments potentiellement codants (susceptibles de produire un polypeptide similaire à des protéines connues) dans cette séquence même si on ne connaît pas la position des gènes.
  • séquence peptidique séquence nucléique (traduite dans les 6 cadres) tblastn
  • Identifier une région génomique susceptible de coder pour un homologue d'une protéine d'intéret.
  • Identifier dans un génome les pseudo-gènes (gènes défectifs, qui peuvent contenir un ou plusieurs codons stop) correspondant à une protéine d'intérêt.
  • séquence nucléique (traduite dans les 6 cadres) séquence nucléique (traduite dans les 6 cadres) tblastx
    [Retour à la table des matières]

    Les différents types d'erreurs de prédiction

    Statut réel
    + -
    Prédiction + VP (vrai positif) FP (faux positif)
    - FN (faux négatif) VN (vrai négatif)

    Statistiques d'évaluation des prédictions

    Sn Sensibilité
    =taux de couverture
    fraction d'éléments de statut réel positif prédits comme positifs Sn = VP / (VP + FN)
    PPV Valeur prédictive positive fraction de prédictions positives possédant un statut réel positif. PPV = VP / (VP + FP)
    FPR Taux de faux-positifs
    (false positive rate)
    fraction de prédictions positives parmi les éléments de statut réel négatif FPR = FP / (FP + VN)
    Sp Spécificité fraction de prédictions négatives parmi les éléments de statut réel négatif Sp = VN / (FP + VN)

    Il existe généralement un compromis entre sensibilité et PPV: si l'on augmente les contraintes sur les prédictions (par exemple en augmentant les seuils de similarité), on augmentera la valeur prédictive positive mais on diminuera la sensibilité.

    [Retour à la table des matières]

    Comment interpréter une e-valeur ("expect") ?

    La e-valeur (en anglais: e-value ou expect pour expected value) représente le nombre de résultats qu'on s'attendrait à obtenir au hasard, en fonction des paramètres utilisés pour un programme.

    Par exemple, le logiciel BLAST caractérise chaque alignement par une e-valeur, qui est calculée en fonction du le score brut, de la longueur des protéines alignées, et de la taille de la base de données (quand la taille d'une base de données augmente, on a plus de chances d'observer un hit fortuit). La e-valeur est le paramètre le plus informatif, d'une part parce qu'elle tient compte de l'ensemble des autres paramètres, d'autre part parce que son interprétation est directe: elle nous informe quant au risque que nous prenons si nous considérons la similarité comme significative. La e-valeur est liée au concept de risque de faux positifs: le risque de considérer comme significatif un résultat qui ne l'est pas.

    Une e-valeur faible indique qu'un résultat est statistiquement significatif.

    La e-valeur ne s'applique pas uniquement aux résultats de BLAST. La plupart des logiciels bioinformatiques indiquent la significativité des résultats, sous forme de e-valeur ou d'autres statistiques apparentées. Il est essentiel de pouvoir interpréter ces nombres pour éviter de se faire flouer par un résultat apparemment prometteur.

    [Retour à la table des matières]

    Alignements multiples

    La méthode la plus utilisée pour aligner plusieurs protéines est l'alignement progressif. Elle se décompose en plusieurs étapes:

    1. Calcul d'une matrice de distance entre toutes les paires de séquences.
    2. Construction d'un arbre-guide à partir de cette matrice de distances
    3. Construction de l'alignement sur base de l'arbre-guide

    Matrice de distances entre paires de séquences

    La première étape d'un alignement progressif consiste à aligner chaque paire de séquences, et à calculer leur distance. On regroupe les résultats dans une matrice de distances, où

     seq 1seq 2...seq n
    seq 1d1,1d1,2...d1,n
    seq 2d2,1d2,2...d2,n
    ...............
    seq ndn,1dn,2...dn,n

    Les alignements par paires peuvent être effectués en utilisant la programmation dynamique (algorithme de Needleman-Wunsch) ou une heuristique plus rapide (fasta, blast).

    Construction de l'arbre-guide

    A partir de la matrice de distance, on peut construire un arbre-guide par la méthode du Neighbour joining (NJ).

    Le principe est d'établir en premier lieu un branchement qui relie les deux séquences les plus proches (celles qui ont la distance minimale dans la marice de distances), puis les séquences un peu moins proches, et ainsi de suite jusqu'à avoir branché toutes les séquences.

    Attention: l'arbre-guide ne doit en aucun cas être considéré comme inférence des relations phylogénétiques entre séquences.

    Il s'agit uniquement d'un outil utilisé temporairement pour déterminer l'ordre d'incorporation des séquences dans l'alignement entre séquences multiples.

    L'inférence phyogénétique nécessite des analyses plus poussées, qui ne pourront être effectuées q'uaprès avoir obtenu l'alignement multiple.

    Alignement progressif

    Après avoir calculé la matrice de distance et construit l'arbre-guide, on construit l'alignement multiple en incorporant progressivement les séquences selon leur ordre de branchement dans l’arbre guide, en remontant des plus proches aux plus éloignées.

    [Retour à la table des matières]

    Motifs dans les séquences

    Consensus

    Chaîne de caractère indiquant les résidus conservés à chaque colonne d'un alignement multiple.

    Le consensus est obtenu en retenant, pour chaque colonne d'un alignement multiple, soit un seul résidu (on parle alors de consenssu strict, soit une combinaison de résidus représentatifs (consensus dégénéré). Les consensus dégénérés peuvent être représentés par des expressions régulières, combinées avec les spécifications IUPAC pour les résidus ambigüs.

    Un consensus fournit une représentation compacte d'un motif séquentiel. Les consensus sont par exemple utilisés

    Le consensus fournit une représentation compacte et intuitive d'un motif, mais souffre de quelques limitations.

    Expressions régulières

    Une expression régulière est une chaîne de caractères qui décrit un motif (ou pattern) composé de différents types d'éléments.

    Exemples:

    [Retour à la table des matières]

    Phylogénie moléculaire

    [Retour à la table des matières]

    Evénements évolutifs

    [Retour à la table des matières]

    Arbres phylogénétiques

    [Retour à la table des matières]

    Estimation des distances sur un arbre phylogénétique

    Voir diapos

    [Retour à la table des matières]

    Bootstrap

    Le booststrap est une stratégie basée sur le rééchantillonnage, qui vise à estimer la robustesse d'une procédure appliquée à un jeu de données. Le principe est d'appliquer de façon itérative la même procédure à un sous-ensemble des données sélectionné aléatoirement. On compare ensuite les résultats obtenus avec les différents sous-ensembles: s'ils sont similaires, la procédure sera qualifiée de robuste.

    Dans le domaine de la phylogénie moléculaire, on utilise le bootstrap pour estimer la robustesse de l'arbre phylogénétique inféré par rapport aux données (alignement multiple) qui ont servi à le générer. Pour ce faire, on sélectionne aléatoirement un sous-ensemble des colonnes de l'alignement multiple, à partir desquelles on infère un arbre phylogénétique. On répète l'opération (typiquement 100 ou 1000 fois) et on compare les arbres obtenus. Chaque branchement de l'arbre initial (celui obtenu avec toutes les colonnes de l'alignement) est annotée en indiquant le nombre de fois où ce même branchement se retrouve dans les bootstraps.

    Valeurs de boostrap sur l'arbre phylogénétique des alcohol déhydegénases de bactéries.

    [Retour à la table des matières]

    Relations entre algorithmes d'inférence phylogénique et arbres

    Méthode Type d'arbre Hypothèse d'horloge moléculaire Enracinement
    Parcimonie Cladogramme Non Non
    UPGMA Chronogramme Oui Oui
    Neighbour joining Phylogramme Non Non
    Maximum de vraisemblance ("Maximum likelihood" en anglais) Phylogramme Non Non
    [Retour à la table des matières]
    Emese Meglécz (IMBE, Aix-Marseille Université) & Jacques van Helden (TAGC, Aix-Marseille Université).