Chapitre IV : Alignement (Partie 2)
Calcul de pénalité pour les gaps :
Fonction linéaire
n : nombre de trous (indels)
: constante pénalisante
Fonction affine
n : nombre de trous ou taille de gap
α : coût de l’ouverture (le début d’un gap)
β : coût de l’allongement ou de l’extension d’un gap
α et β sont deux constantes définies empiriquement
Exemple : = -6, α = -10, β = -2 et Matrice BLOSUM62 :
Avantages et inconvénients de la programmation dynamique :
Elle garantit à 100% d’obtenir un ou plusieurs alignements optimaux.
Par contre, elle est lente en termes de temps d’exécution ; d’où la nécessité d’utiliser des
méthodes heuristiques (ou approximatives).
En pratique : Séquence requête vs. Banque de données
Exemple : La banque UniProtKB possède plus de 71 millions de séquences protéiques
avec plus de 23 milliards d’acides aminés !!!
Méthodes heuristiques :
FASTA : (FASTP, FASTN)
Présenté en 1985.
Accessible sur : http://fasta.bioch.virginia.edu/fasta_www2/fasta_list2.shtml
Se baser sur la matrice de points, sans pour autant la calculer !!!
Deux séquences S1 : n résidus ; S2 : m résidus → (n + m -1) diagonales dans la matrice de
points.
Utiliser des petits segments ayant une taille de k résidus : k-uplets
k = 1 - 4 pour les acides aminés
k = 7 - 11 pour les acides nucléiques
Etapes à suivre :
1. Décomposer les deux séquences : S1 (séquence requête) et S2 (appartient à la banque de
données) en k-uplets chevauchants.
1
2. Créer un tableau de scores pour toutes les diagonales :
Le score d’une diagonale ≈ Nombre d’identités qui se trouvent sur cette diagonale.
3. Pour chaque k-uptet commun entre S1 et S2, incrémenter le score de la diagonale (i-j) où i
et j sont les positions du k-uptlet commun dans S1 et S2, respectivement.
4. Choisir une taille de bande d autour de la diagonale principale qui permettra de choisir
uniquement quelques diagonales dans le tableau de scores bande d’homologie
maximale ou une deuxième approche qui consiste à choisir les 10 meilleures diagonales
avec les scores les plus élevés.
5. L’alignement final sera construit à partir de la bande choisie précédemment en recollant
les k-uplets trouvés dans cette bande avec la possibilité d’utiliser l’algorithme de
Needleman & Wunsch.
Exemple :
k =2 ; Acides nucléiques (par souci de simplification, on choisit k = 2)
S1 : ATGCAAGCAATC ; S2 : CATCAATTGCA (S2 fait partie d’une banque de données)
L’indice ( i - j ) indique la diagonale sur laquelle se trouve un k-uptlets communs entre S1 et S2. On ne
garde que les régions identiques de longueur ≥ k.
S1 S2
Positions Positions
2-uplet 2-uplet
(i) (j)
AT 1 , 10 CA 1 , 4 , 10
TG 2 AT 2,6
GC 3,7 TC 3
CA 4,8 AA 5
AA 5,9 TT 7
AG 6 TG 8
TC 11 GC 9
Tableau de score :
d-10 d-9 d-8 d-7 d-6 d-5 d-4 d-3 d-2 d-1 d0 d1 d2 d3 d4 d5 d6 d7 d8 d9 d10 d11
1 0 0 0 4 3 1 0 3 4 3 1 1 4 5 1 0 2 3 0 0 1
d=5
S1 : -ATGCAA--GCAATC
S2 : CAT-CAATTGCA---
En pratique, c’est beaucoup plus compliqué que
cela, surtout quand les séquences font plusieurs
centaines de résidus.
2
BLAST: Basic Local Alignment Search Tool
Présenté en 1990.
https://blast.ncbi.nlm.nih.gov/Blast.cgi
Utilisation de k-uplets plus longs contrairement au FASTA. Au niveau de l’interface de BLAST,
k correspond au paramètre w (pour Word size).
Etapes à suivre:
1. Retrouver tous les k-uplets (mots) de S1
2. Pour tout k-uplet appartient à S1, récupérer tous les k-uplets ayant un score de similarité
≥ Seuil H Construire la liste L.
3. Faire la recherche des mots appartenant à la liste L dans la banque de données.
4. Stratégie de BLAST : Prolonger l’alignement de part et d’autre autour des k-uplets initiaux
tant que le score monte ou reste stable.
Exemple :
k = 4 ; H (seuil) = 17 ; Matrice de substitution : BLOSUM62
S1 : … IFKRFW …
La liste L pour le quadruplet : FKRF
Score = 22 Score = 19 Score = 18 Score = 17
FKRF YKRF FQRF WKRF
FKRY FERF FKRW
FRRF FKQF FNRF
FKKF FSRF
FKNF
FKEF
FKHF
La liste L va être utilisée pour examiner toutes les séquences de la banque de données. Chaque fois
qu’un quadruplet appartenant à L est trouvé, on essaie d’étendre l’alignement autour des
quadruplets initiaux tant que le score augmente ou reste stable.
S1 : … IFKRFW …
S2 : … LFKQFY …
Le score de similarité initial entre les deux quadruplets ‘FKRF’ et ‘FKQF’ est de 18. L’idée de BLAST
consiste à reconsidérer les deux segments initiaux en leur ajoutant le résidu qui se trouve à leur
droite : ‘FKRFW’ et ‘FKQFY’ → le score devient égal à 20. Si on ajoute cette fois-ci le résidu qui se
trouve à gauche, le score de similarité monte à 22 entre ‘IFKRFW’ et ‘LFKQFY’, etc.
Versions de BLAST :
3
Fiabilité et qualité des méthodes heuristiques :
Questions auxquelles il faut répondre :
Trouver toutes les séquences homologues ?
Signification statistique / biologique de l’homologie trouvée ?
Impact des paramètres de la méthode choisie : BLAST
H ↗ : Risque de rater des alignements intéressants
H ↘ : Risque de récupérer des intrus
Outil d’évaluation est nécessaire et indispensable:
Pour BLAST :
Mesure E-value = Espérance mathématique calculée à partir d’un modèle statistique
Définition d’après https://www.ncbi.nlm.nih.gov/BLAST/tutorial/Altschul-1.html:
“The Expect value (E) is a parameter that describes the number of hits one can
"expect" to see by chance when searching a database of a particular size. It decreases
exponentially as the Score (S) of the match increases. Essentially, the E value
describes the random background noise. For example, an E value of 1 assigned to a
hit can be interpreted as meaning that in a database of the current size one might
expect to see 1 match with a similar score simply by chance.
The lower the E-value, or the closer it is to zero, the more "significant" the match is.
However, keep in mind that virtually identical short alignments have relatively high E
values. This is because the calculation of the E value takes into account the length of
the query sequence. These high E values make sense because shorter sequences have
a higher probability of occurring in the database purely by chance.” Hit = Alignment
n : Longueur de la séquence requête
m : Longueur de la banque de données (nombre total de résidus)
S : Score normalisé
n.m : espace de recherche
N.B. Aucun support électronique n’est prévu pour les autres parties abordées en cours : Alignement
multiple & Arbres phylogénétiques.
Références bibliographiques :
