Bienvenue sur
PhyloGraphe !

Pour mesurer la distance entre des séquences non alignées, la méthode AAF (Assembly and Alignment-Free) consiste à compter les k-mères communs entre ces deux séquences. Un k-mère est une sous-séquence de longueur k. Dans une séquence de longueur L, il y a donc (L − k + 1) k-mères qui se chevauchent. Ces k-mères ne sont pas nécessairement uniques. Dans une séquence d'ADN il y a par exemple seulement 4 monomères distincts (pour k = 1; A, T, C, G), 16 dimères distincts (pour k = 2; AA, AT, AC, AG, TA, TT, TC, TG, CA, CT, CC, CG, GA, GT, GC, GG), etc. De manière générale, il y a au maximum 4^k k-mères différents dans une séquence d'ADN, ou 20^k dans une séquence peptidique. Si une mutation se produit dans un k-mère hérité d'une séquence ancestrale alors celui-ci ne sera plus commun entre les deux séquences comparées. On doit donc choisir k suffisamment grand pour que deux k-mères partagés par deux séquences ne le soient pas par hasard (spécificité). Mais on doit aussi choisir k suffisamment petit pour que la probabilité que plusieurs mutations se produisent dans le même k-mère reste faible afin de ne pas sous-estimer la distance calculée (sensibilité). On calcule cette distance d avec la formule suivante (n étant le nombre de k-mères distincts dans la plus petite des deux séquences et s le nombre de k-mères communs entre les deux séquences) :

d = ln(n) − ln(s)k

Cette méthode d'estimation des distances entre des séquences ne repose pas sur un modèle de substitution des nucléotides ou des acides aminés, mais il suppose tout de même que les mutations sont réparties aléatoirement dans les séquences. Une concentration des mutations dans certaines régions peut aboutir à une sous-estimation de la distance, surtout pour des valeurs élevées de k.

La spécificité est égale à c =4^kL_max (pour les séquences de nucléotidiques) ou bien c =20^kL_max (pour les séquences peptidiques). La sensibilité est égale à s =1kd_max. Ces deux indices sont sans unités et ne sont pas comparables. On cherche à les maximiser tous les deux. On essaie empiriquement d'avoir une spécificité supérieure à 350 et une sensibilité supérieure à 0,25.

La distance de Hamming est simplement le nombre de positions où deux séquences de même longueur présentent un symbole différent. On peut normaliser cette distance pour pouvoir comparer des distances entre des paires de séquences de longueurs différentes en divisant le nombre de différences par la longueur des deux séquences comparées. Cette distance peut ainsi s'exprimer en pourcentage, elle représente la proportion de différences de les deux séquences, c'est pourquoi on l'appelle aussi la p-distance. On a donc :

p = fL où f est le nombre de différences et L la longueur des deux séquences.

On ignore donc les lacunes causées par les insertions et les délétions, on ne compte que les évènements de substitutions. Cette distance ne tient pas non plus compte de la possibilité qu'un même résidu puisse subir plusieurs substitutions, ni non plus que les différents types de substitutions aient des probabilités différentes de survenir. La p-distance sous-estime donc toujours la distance réelle entre deux séquences et n'est fiable que pour de très petites distances (inférieure à 2 %).

La distance de Levenshtein normalisée (ou distance d'édition normalisée) est très similaire à la p-distance. On compte le nombre des substitutions, mais on compte également le nombre de lacunes (correspondant aux insertions et aux délétions) qui diffèrent entre les deux séquences. Deux lacunes seront considérées comme différentes si leur position de début ou bien leur position de fin sont différentes. Une lacune compte toujours pour un seul évènement d'insertion ou de délétion, quelle que soit sa longueur. La formule ajustée est ainsi la suivante :

p* = f + g_{A Δ B}L + g_{A ∪ B}

Ici f est le nombre de substitutions, L la longueur des deux séquences (en ignorant les lacunes), g_{A Δ B} est est le nombre de lacunes non partagées entre les deux séquences, et g_{A ∪ B} est le nombre de lacunes uniques dans les deux séquences (on ne compte les lacunes partagées qu'une seule fois). Cette prise en compte des lacunes rappelle la distance de Jaccard. Bien que l'on ait incorporé une information supplémentaire pour évaluer plus précisément la distance, cette méthode souffre des mêmes limitations que la p-distance classique et ne sera fiable que pour les séquences très proches (environ 2 % de différences au maximum).

La distance LogDet est basée sur le logarithme naturel du déterminant de la matrice des fréquences de tous les types de substitutions observées entre les deux séquences comparées. L'avantage de la distance LogDet est qu'elle ne repose pas sur un modèle de substitution particulier et ne requiert donc pas d'estimer les paramètres d'un tel modèle. De plus, elle estime correctement les distances entre des séquences ayant des fréquences de résidus différentes contrairement aux modèles de substitutions qui sont généralement stationnaires et qui supposent donc que les fréquences des différents types de résidus sont similaires dans les deux séquences comparées. La méthode du LogDet donne généralement de meilleurs résultats pour les séquences nucléotidiques que pour les séquences peptidiques qui sont plus courtes et comportent davantage de types de résidus différents.

d(X, Y) = (1 −rΣi = 1π_i²) ×2 × ln(det(F_XY)) − ln(det(A_XA_Y))2 − 2r

Dans cette formule les π_i sont les fréquences globales des différents résidus, r est le nombre d'états différents (4 pour l'ADN et l'ARN, 20 pour les protéines), F_XY est la matrice r × r des fréquences des sites où l'on trouve le résidu i dans la séquence X et le résidu j dans la séquence Y, et A_X et A_Y sont les matrices diagonales r × r des fréquences des différents résidus dans les séquencse X et Y respectivement.

La distance de Jukes et Cantor introduit une correction statistique par rapport à la p-distance (correspondant à la simple observation de la proportion de résidus différents entre les deux séquences comparées) qui permet de tenir compte de la possibilité qu'un nucléotide puisse subir plusieurs substitutions. Cette mesure de la distance suppose cependant que tous les nucléotides ont la même fréquence d'équilibre (25 %), que tous les types de substitutions sont équiprobables, et que les mutations sont réparties de manière homogène le long des séquences. Ces hypothèses ne sont pas biologiquement réalistes, la distance corrigée par Jukes et Cantor n'est donc fiable que pour les petites distances (inférieure à 5 %).

d = −34ln(1 −43p)

La distance de Kimura-2-paramètres utilise une correction statistique similaire à celle de Jukes et Cantor (JC69), mais contrairement à cette dernière tous les types de substitutions ne sont pas considérés comme équiprobables. Le calcul de la distance K2P distingue en effet le taux de transitions (entre deux purines A↔G ou entre deux pyrimidines T↔C) et le taux de transversions (entre une purine et une pyrimidine). La probabilité relative d'une transition est en effet empiriquement bien plus élevée qu'une transversion. Cette distance ne tient toutefois pas compte de possibles biais de compositions comme des taux de GC différents d'une séquence à l'autre.

d = −12ln(1 − 2P − Q) −14ln(1 − 2Q)

Dans cette formule P est la proportion empirique de transitions et Q est la proportion empirique de transversions. Ces deux proportions ne sont pas indépendantes l'une de l'autre étant donné un certain nombre de substitutions, il n'y a donc qu'un seul paramètre libre contrairement à ce que laisse penser le nom de cette distance.

La distance de Tamura est une amélioration de la distance K2P qui tient compte non seulement de taux de transitions et de transversions distincts, mais aussi d'une richesse en GC différente entre les deux séquences.

d = − h ln(1 −Ph− Q) −12(1 − h) ln(1 − 2Q)

On a ici P la proportion de transitions, Q la proportion de transversions, et h = θ₁ + θ₂ − 2θ₁θ₂ avec θ₁ le taux de GC dans la séquence 1 et θ₂ le taux de GC dans la séquence 2. On remarque alors que la distance K2P est un cas particulier de T92 où h = 0,5 (c'est-à-dire θ₁ = 0,5 ou θ₂ = 0,5).

La distance F84 repose sur le modèle de Substitutions présenté par Felsenstein en 1984. Ce modèle prend en compte des taux de transitions et de transversions distincts, ainsi que des fréquences d'équilibre différentes de 1/4 pour chaque nucléotide sur les deux séquences considérées (pas seulement la richesse en GC contrairement à T92). De plus, les taux des deux types de transitions (entre purines ou bien entre pyrimidines) sont différents mais ne sont pas libres. Ces deux taux sont en effet reliés entre eux par les fréquences d'équilibre des nucléotides.

d = − a ln(1 − Pa− (a − b)Qac) + (a − b − c)ln(1 − Qc)

Dans cette formule P est la proportion observée de transitions et Q est la proportion observée de transversions. Les indices a, b et c sont calculés comme suit :

a = 2g_Tg_Cg_Y + 2g_Ag_Gg_R

b = 2g_Tg_C + 2g_Ag_G

c = 2g_Yg_R

Où g_A, g_T, g_C et g_G sont les proportions observées des différents nucléotides, et g_Y = g_T + g_C, et g_R = g_A + g_G. On remarque que l'on retrouve la formule de T92 dans le cas particulier où a = h, b = a2 et c = 12

La distance de Tamura et Nei (1993) est l'une des plus générales, elle comporte en effet pas moins de 5 paramètres libres  les 4 paramètres de fréquences d'équilibre des différents nucléotides, dont 3 libres, ainsi qu'un taux de transversions et deux taux de transitions distincts (entre purines et entre pyrimidines), ce qui compte comme 2 paramètres libres.

d = −2g_Ag_Gg_Rln(1 −g_RP₁2g_Ag_G−Q2g_R) −2g_Tg_Cg_Yln(1 − g_YP₂2g_Tg_C−Q2g_Y) − 2(g_Rg_Y −g_Ag_Gg_Yg_R−g_Tg_Cg_Rg_Y)ln(1 −Q2g_Rg_Y)

Dans cette formule P₁ est la proportion observée de transitions entre purines, P₂ est la proportion observée de transitions entre pyrimidines, et Q est la proportion observée de transversions. On a de plus g_A, g_T, g_C et g_G les proportions observées des différents nucléotides, avec g_Y = g_T + g_C et g_R = g_A + g_G. Le dernier terme de cette somme, qui concerne uniquement les transversions, est strictement identique à celui que l'on trouve dans la formule de la distance F84.

La correction de Poisson est l'équivalent pour les protéines de la distance JC69. Elle suppose que tous les types de substitutions entre acides aminés ont la même probabilité de survenir et son réparties de manière homogène le long des séquences. Elle ne tient donc pas compte des fréquences d'équilibre des différents acides aminés, ni de la redondance du code génétique. Les lacunes (insertions et délétions) sont également ignorées. On calcule la distance d à partir de la proportion p d'acides aminés différents entre les deux séquences. Cette correction, dite de Poissson, permet de prendre en compte la probabilité qu'un même acide aminé ait changé plus d'une fois.

d = −1920ln(1 −2019p)

Pour pallier les biais auxquels la simple correction de Poisson ne pouvait pas remédier, Kimura a essayé d'adapter la formule de manière empirique pour que la valeur de la distance calculée soit plus proche de la valeur attendue. Cet ajustement ne tient toutefois toujours pas compte explicitement des fréquences d'équilibre des différents acides aminés, ni non plus de leurs divers taux de substitutions les uns avec les autres. La distance d est ainsi toujours calculée seulement à partir de la proportion p d'acides aminés différents entre les deux séquences :

d = − ln(1 − p −p²5)

La méthode Scoredist d'estimation de la distance entre deux séquences peptidiques s'appuie sur les fréquences de substitutions observées dans une grande base de données de séquences peptidiques alignées. Ces fréquences ont été traduites en une matrice de scores arrondis à un entier relatif (BLOSUM62). Plus le score est élevé et plus la fréquence de cette substitution est élevée. Cette méthode est donc plus précise et fiable qu'une simple correction empirique basée sur la p-distance qui ne tient pas compte des propriétés des différents acides aminés et de leurs fréquences de substitution. La distance d est ainsi calculée de la manière suivante :

d = − c × ln(s(A, B) − s₀L s(A, A) + s(B, B)2− s₀L)

Dans cette formule on a s() la fonction de score additionnant pour toutes les positions dans les séquences comparées les valeurs de la matrice BLOSUM62 ci-contre, s₀ = −0,5209 l'espérance de cette matrice pour deux acides aminés aléatoires (en tenant compte de leurs fréquences respectives), L la longueur des deux séquences comparées A et B (en ignorant les lacunes), et enfin c = 1.2873 un facteur de calibration empirique (ajusté au modèle de substitution JTT qui représente le meilleur compromis si l'on ne connait pas le modèle représentant le mieux l'évolution des séquences étudiées).