Françoise Giroud- Laboratoire TIMC-IMAG/Equipe DyCTiMUE Bio24a – La Bio-informatique (UJF/DLST - Année 2011-2012) – 4 Février 2013
D1
Alignement de séquences (2/2)
Oui … mais !!!!
Pas de mesure quantitative de similarité
Simple, visuel,
Très informatif :• Permet de repérer une similarité globale• Permet de repérer des similarités locales• Permet de repérer des répétitions
Observation à l’aide de l’outil graphique : le dotplot.
Françoise Giroud- Laboratoire TIMC-IMAG/Equipe DyCTiMUE Bio24a – La Bio-informatique (UJF/DLST - Année 2011-2012) – 4 Février 2013
D2
Alignement de séquences
http://en.wikipedia.org/wiki/Sequence_alignment
identité substitutionInsertion / Délétion
Alignement : mise en correspondance de deux séquences
Quantifier et localiser la similarité dans une paire de séquences
Trouver la meilleure mise en correspondance des résidus qui conserve l’ordre des séquences
Utilisation de la méthode des scoresTrouver le meilleur score
Françoise Giroud- Laboratoire TIMC-IMAG/Equipe DyCTiMUE Bio24a – La Bio-informatique (UJF/DLST - Année 2011-2012) – 4 Février 2013
D3
Alignement de séquences
Matrice de similarité Pénalités
Le score de l’alignement est la somme des scores des événements élémentaires
Calcul de score ?
http://en.wikipedia.org/wiki/Sequence_alignment
identité substitution Insertion / Délétion
Françoise Giroud- Laboratoire TIMC-IMAG/Equipe DyCTiMUE Bio24a – La Bio-informatique (UJF/DLST - Année 2011-2012) – 4 Février 2013
D4
B Aspartic Acid ou Glutamic AcidZ Glutamine ou Glutamic AcidX inconnu Proprités physico-chimiques
diagramme Venn
Alignement de séquences
Rappel sur les acides aminés ….
Françoise Giroud- Laboratoire TIMC-IMAG/Equipe DyCTiMUE Bio24a – La Bio-informatique (UJF/DLST - Année 2011-2012) – 4 Février 2013
D5
Alignement de séquencesCalcul de score : matrices de similarité
Matrices protéiques : BLOSUM (Henikoff & Henikoff, 1992)PAM (Dayhoff, 1969)
Choix de la matrice ?Il n’existe pas de matrice idéale !!!
Blosum62 semble être la plus générale.
Blosum 62
A R N D P W AG K M H C W A0 2 -2 1 -3 11 4 Total = 13
Françoise Giroud- Laboratoire TIMC-IMAG/Equipe DyCTiMUE Bio24a – La Bio-informatique (UJF/DLST - Année 2011-2012) – 4 Février 2013
D6
Calcul de score : matrices de similarité
Alignement des séquences
Matrice d’acides nucléiques : Matrice d’ADN
Mésappariementde 2 purines ou 2 pyrimidines
Françoise Giroud- Laboratoire TIMC-IMAG/Equipe DyCTiMUE Bio24a – La Bio-informatique (UJF/DLST - Année 2011-2012) – 4 Février 2013
D7
Calcul de score : matrices de similarité
Alignement des séquences
Françoise Giroud- Laboratoire TIMC-IMAG/Equipe DyCTiMUE Bio24a – La Bio-informatique (UJF/DLST - Année 2011-2012) – 4 Février 2013
D8
Alignement de séquencesCalcul de score : pénalité des indel
Ouverture
pénalités• ouverture• extension
Ajustement des pénalités ?
• augmenter le score en fonction de la longueur du « gap » :choisir une pénalité d’ouverture > à la pénalité d’extension,
• faire en sorte de ne pas affecter le score en fonction de la longueur du « gap » : pénaliser juste l’ouverture du « gap », très peu ou pas du tout l’extension.
Extensions
Françoise Giroud- Laboratoire TIMC-IMAG/Equipe DyCTiMUE Bio24a – La Bio-informatique (UJF/DLST - Année 2011-2012) – 4 Février 2013
D9
Alignement de séquencesCalcul de score : exercices
Calculer les scores pour chacun des alignements etselon les 2 matrices de similarité : BLOSUM62 et BLOSUM50
Blosum 62Blosum 50
Françoise Giroud- Laboratoire TIMC-IMAG/Equipe DyCTiMUE Bio24a – La Bio-informatique (UJF/DLST - Année 2011-2012) – 4 Février 2013
D10
Alignement de séquences
L’alignement par paires : alignement global,
alignement sur la totalité de la longueur de deux séquences
nécessité d’ajout d’indel dans l’une des séquences
Algorithme de Needleman-Wunsch
alignement local,
identification de régions de forte homologie
alignement sur les régions conservées seulement
Algorithme de Smith-Waterman
L’alignement multipleAlignement global entre plus de 2 séquences.
On distingue différents types d’alignements :
Françoise Giroud- Laboratoire TIMC-IMAG/Equipe DyCTiMUE Bio24a – La Bio-informatique (UJF/DLST - Année 2011-2012) – 4 Février 2013
D11
Alignement de séquences
Construire des alignements de séquence ?
Calcul informatique (1) : approche exhaustive (naïve)o les différentes solutions alternatives d’alignement possibles sont proposées,o Les scores sont calculés pour chacune de ces alternatives,o Est conservé le meilleur alignement, càd celui qui a le score le plus élevé.
Simple, mais temps de calcul bien trop élevé Op. x nn !!!!!Estimation du temps de calcul :alignement de 2 séquences de longueur n=20, temps de calcul (1 itération Op.=0,1s) 300 millions d’années.
Françoise Giroud- Laboratoire TIMC-IMAG/Equipe DyCTiMUE Bio24a – La Bio-informatique (UJF/DLST - Année 2011-2012) – 4 Février 2013
D12
Alignement de séquences
Construire des alignements de séquence ?
Calcul informatique (2) : approche dynamiqueo Optimiser le score pour chaque paire de résidus (m*n paires),o Le meilleur score est la somme des meilleurs scores de chaque paire.
Exact, rapide [temps de calcul Op. x(m*n)], mais gourmand en mémoire !!!!!Estimation du temps de calcul :alignement de 2 séquences de longueur n=20, temps de calcul (1 itération Op.=0,1ms) 40 s.
Françoise Giroud- Laboratoire TIMC-IMAG/Equipe DyCTiMUE Bio24a – La Bio-informatique (UJF/DLST - Année 2011-2012) – 4 Février 2013
D13
Etape 1 :Construction dela matrice de comparaison. Matrice(m,n)
Etape 2 :Transformation de la matrice par addition des scores.
Alignement de séquences
Construire des alignements de séquence ?Programmation dynamique :
Alignement global de Needlemann & Wunsch (1970)
http://www.info.univ-angers.fr/~richer/recbioal3.php
Françoise Giroud- Laboratoire TIMC-IMAG/Equipe DyCTiMUE Bio24a – La Bio-informatique (UJF/DLST - Année 2011-2012) – 4 Février 2013
D14
Etape 2 :Transformation de la matrice par addition des scores :o Initialisation de (m,0) et (0,n)o Addition des scores :
Alignement de séquencesConstruire des alignements de séquence ?Programmation dynamique :
Alignement global de Needlemann & Wunsch (1970)
Avec :S(i,j) : score dans la case (i,j)de la matrice transformée.
se(i,j) : score élémentaire de la case d’indice i et j de la matrice initiale.
ij
Démonstration : construction de la matrice transformée
+
Matrice initiale :
yx
Françoise Giroud- Laboratoire TIMC-IMAG/Equipe DyCTiMUE Bio24a – La Bio-informatique (UJF/DLST - Année 2011-2012) – 4 Février 2013
D15
Etape 2 :Transformation de la matrice par addition des scores :o Initialisation de (m,0) et (0,n)o Addition des scores :
Alignement de séquencesConstruire des alignements de séquence ?Programmation dynamique :
Alignement global de Needlemann & Wunsch (1970)
Avec :S(i,j) : score dans la case (i,j)de la matrice transformée.
se(i,j) : score élémentaire de la case d’indice i et j de la matrice initiale.
ij
Démonstration : construction de la matrice transformée
+
Matrice initiale :
yx
Françoise Giroud- Laboratoire TIMC-IMAG/Equipe DyCTiMUE Bio24a – La Bio-informatique (UJF/DLST - Année 2011-2012) – 4 Février 2013
D16
Etape 2 :Transformation de la matrice par addition des scores :o Initialisation de (m,0) et (0,n)o Addition des scores :
Alignement de séquencesConstruire des alignements de séquence ?Programmation dynamique :
Alignement global de Needlemann & Wunsch (1970)
Matrice transformée finale :Matrice transformée intermédiaire :
Processus ascendant
Françoise Giroud- Laboratoire TIMC-IMAG/Equipe DyCTiMUE Bio24a – La Bio-informatique (UJF/DLST - Année 2011-2012) – 4 Février 2013
D17
Etape 3 :Chemin des scores maxima
Alignement de séquencesConstruire des alignements de séquence ?Programmation dynamique :
Alignement global de Needlemann & Wunsch (1970)
ij
j
i
Processus descendant
Françoise Giroud- Laboratoire TIMC-IMAG/Equipe DyCTiMUE Bio24a – La Bio-informatique (UJF/DLST - Année 2011-2012) – 4 Février 2013
D18
Alignement de séquencesConstruire des alignements de séquence ?Programmation dynamique :
Alignement global de Needlemann & Wunsch (1970)
Alignement local de Smith-Waterman (1981)
Les deux séquences présentent une similarité que l’alignement global ne révèle pas !!!!!
Françoise Giroud- Laboratoire TIMC-IMAG/Equipe DyCTiMUE Bio24a – La Bio-informatique (UJF/DLST - Année 2011-2012) – 4 Février 2013
D19
Alignement de séquencesConstruire des alignements de séquence ?Programmation dynamique :
Alignement local de Smith-Waterman (1981)
Dans le cas de l’alignement local :
• N’importe quelle cellule de la matrice de comparaison peut être prise comme point de départ pour le calcul des scores sommes.
• Tout score somme qui devient négatif stoppe la progression du calcul.
• Cette nouvelle case peut être initialisée à 0 et constituer un nouveau point de départ.
Françoise Giroud- Laboratoire TIMC-IMAG/Equipe DyCTiMUE Bio24a – La Bio-informatique (UJF/DLST - Année 2011-2012) – 4 Février 2013
D20
Alignement de séquencesUn outil d’alignement : Align.
http://www.ebi.ac.uk/emboss/align
Choix de la méthode :
« needle » (global)Needleman-Wunsch
« water » (local)Smith-Waterman
Françoise Giroud- Laboratoire TIMC-IMAG/Equipe DyCTiMUE Bio24a – La Bio-informatique (UJF/DLST - Année 2011-2012) – 4 Février 2013
D21
Alignement de séquencesUn outil d’alignement : Align.
http
://w
ww
.ebi
.ac.
uk
/em
boss
/ali
gn
Etape 1 :
Entrée des deux séquences à analyser
Etape 2 :
Choix :. des penalités et . de la matrice de similarité.
Etape 3 : Exécution ….
Françoise Giroud- Laboratoire TIMC-IMAG/Equipe DyCTiMUE Bio24a – La Bio-informatique (UJF/DLST - Année 2011-2012) – 4 Février 2013
D22
Alignement de séquencesUn outil d’alignement : Align.
http
://w
ww
.ebi
.ac.
uk
/em
boss
/ali
gn
Des Résultats :
Identité :Proportion des paires de résidus identiques entre les deux séquences alignées(exprimée en %)
Similarité :Mesure de la ressemblance entre les deux séquences alignées. Le degré de similitude entre les deux séquences est quantifié par un score basé sur le % de similarité (% d’identité + % de substitutions conservatives).
Score :Somme des scores des événements élémentaires.
Françoise Giroud- Laboratoire TIMC-IMAG/Equipe DyCTiMUE Bio24a – La Bio-informatique (UJF/DLST - Année 2011-2012) – 4 Février 2013
D23
Pourquoi ?
Savoir si ma séquence ressemble à d’autres séquences déjà connues,
Trouver toutes les séquences d’une même famille,
Rechercher toutes les séquences qui contiennent un motif donné.
Recherche de similitudes dans une base de séquences (base de données)
???
Françoise Giroud- Laboratoire TIMC-IMAG/Equipe DyCTiMUE Bio24a – La Bio-informatique (UJF/DLST - Année 2011-2012) – 4 Février 2013
D24
Méthodes ?
Recherche à grande échelle (bases de données contenant des 10zaines de milliers de séquences)
pas raisonnable d’utiliser des programmes classiques d’alignement
Utilisation d’heuristiques : BLAST & FASTABasic Local Alignment Search Tool (Altschul et al, 1990)
Méthodes approximatives basées sur une idée de filtrage.
Recherche de similitudes dans une base de séquences (base de données)
???
Françoise Giroud- Laboratoire TIMC-IMAG/Equipe DyCTiMUE Bio24a – La Bio-informatique (UJF/DLST - Année 2011-2012) – 4 Février 2013
D25
BLAST : Basic Local Aligment Search Tool :Recherche de régions de similarité locales.
L’algorithme BLAST :
Étape 1 : création d’une liste de tous les fragments (mots) de taille k (avec k petit: 11 pour les acides nucléiques, 2 ou 3 pour les protéines) trouvés dans la séquence requête et qui obtiennent un score > à un seuil donné.
Etape 2 : construction d’un automate fini déterministe pour retrouver les positions de tous les mots dans toutes les séquences de la banque de données.
A partir de ces positions, BLAST essaie d’étendre l’alignement local tant que le score reste au dessus d’un seuil donné.
Toutes ces positions dans les séquences de la banque permettent ainsi de construire la liste des segments les plus similaires ou HSP (High Scoring Segment Pairs).
Étape 3 : ordonner les alignements locaux, appelés MSP (Maximal-scoring Segment Pairs) en fonction de leur score maximun.
Françoise Giroud- Laboratoire TIMC-IMAG/Equipe DyCTiMUE Bio24a – La Bio-informatique (UJF/DLST - Année 2011-2012) – 4 Février 2013
D26
Étape 1 :Création d’une liste de tous les fragments (mots) de taille ktrouvés avec un score > seuil
Etape 2 :Construction d’un automateretrouver les positionsdans séquences de la BD.
Extension de l’alignement localscore reste au dessus d’un seuil donné=>construction de la liste des HSP,
Etape 3 :Construction de la liste de MSP (HSP à score maximal)
Françoise Giroud- Laboratoire TIMC-IMAG/Equipe DyCTiMUE Bio24a – La Bio-informatique (UJF/DLST - Année 2011-2012) – 4 Février 2013
D27
BLAST : Basic Local Aligment Search Tool :Recherche de régions de similarité locales.
Evaluer les résultats de BLAST : les indicateurs
Le score brute : est la somme des scores des MSP qui composent cet alignement.
Le score modifié : scores bruts convertis du logarithme (utilisés pour la création de la matrice de scores) au logarithme à base 2.Cela permet de comparer les scores obtenus entre différents alignements.
La E-value : donne les informations sur la significativité d’un alignement donné. La E-value d’un alignement indique le nombre d’alignements que l’on s’attendrait à trouver dans les banques avec un score supérieur ou égal au score qu’obtiendrait la séquence requête contre une banque de données aléatoire (probabilité d'observer au hasard ce score à travers la banque de séquences considérée).
Plus la E-value est faible, plus l'alignement est significatif.
Françoise Giroud- Laboratoire TIMC-IMAG/Equipe DyCTiMUE Bio24a – La Bio-informatique (UJF/DLST - Année 2011-2012) – 4 Février 2013
D28
BLAST : Basic Local Aligment Search Tool :Recherche de régions de similarité locales.
Evaluer les résultats de BLAST : les indicateurs
Françoise Giroud- Laboratoire TIMC-IMAG/Equipe DyCTiMUE Bio24a – La Bio-informatique (UJF/DLST - Année 2011-2012) – 4 Février 2013
D29
Implémentation de l’algorithme BLAST :
NCBI BLAST & WU-BLAST ?
NCBI BLAST & WU-BLAST :Utilisables en tant que serveurs Web ou paquetage logiciel téléchargeable.
NCBI BLAST :disponible sur le serveur du NCBI.http://blast.ncbi.nlm.nih.gov/BlastPour les versions les plus récentes : profit du développement de méthodes permettant de comparer les profils de séquences multiples.
WU-BLAST :version alternative développée et maintenue à partir de la version NCBI Interrogation de bases de données protéines.http://www.ebi.ac.uk/Tools/sss/wublast/
Françoise Giroud- Laboratoire TIMC-IMAG/Equipe DyCTiMUE Bio24a – La Bio-informatique (UJF/DLST - Année 2011-2012) – 4 Février 2013
D30
BLAST : Basic Local Aligment Search Tool :Recherche de régions de similarité locales.
Les différents programmes BLAST :
blastp : séquence requête protéique contre banque de données de séquences protéiques.
blastn : séquence requête nucléique contre banque de données de séquences nucléiques.
blastx : séquence requête nucléique traduite dans les six phases de lecture contre banque de données de séquences protéiques.
tblastn : séquence requête protéique contre banque de données de séquences nucléiques dynamiquement traduite dans les six phases de lecture.
tblastx : séquence requête nucléiques traduite dans les six phases de lecture contre banque de données de séquences nucléiques dynamiquement traduites suivant les six phases de lecture.
Françoise Giroud- Laboratoire TIMC-IMAG/Equipe DyCTiMUE Bio24a – La Bio-informatique (UJF/DLST - Année 2011-2012) – 4 Février 2013
D31
BLAST : Basic Local Aligment Search Tool :Recherche de régions de similarité locales.
Les différents programmes BLAST :
Françoise Giroud- Laboratoire TIMC-IMAG/Equipe DyCTiMUE Bio24a – La Bio-informatique (UJF/DLST - Année 2011-2012) – 4 Février 2013
D32
Choisir le programme :
Choisir l’espèce étudiée :
http://blast.ncbi.nlm.nih.gov/Blast
Choisir la base de données :
Françoise Giroud- Laboratoire TIMC-IMAG/Equipe DyCTiMUE Bio24a – La Bio-informatique (UJF/DLST - Année 2011-2012) – 4 Février 2013
D33
Entrer la séquence requête :
Ajuster la sélection de la
base de données :
Optimisez les contraintes de
sélection :
Françoise Giroud- Laboratoire TIMC-IMAG/Equipe DyCTiMUE Bio24a – La Bio-informatique (UJF/DLST - Année 2011-2012) – 4 Février 2013
D34
Réglez les paramètres de
votre recherche :
Françoise Giroud- Laboratoire TIMC-IMAG/Equipe DyCTiMUE Bio24a – La Bio-informatique (UJF/DLST - Année 2011-2012) – 4 Février 2013
D35
Les résultats !!
Françoise Giroud- Laboratoire TIMC-IMAG/Equipe DyCTiMUE Bio24a – La Bio-informatique (UJF/DLST - Année 2011-2012) – 4 Février 2013
D36
Françoise Giroud- Laboratoire TIMC-IMAG/Equipe DyCTiMUE Bio24a – La Bio-informatique (UJF/DLST - Année 2011-2012) – 4 Février 2013
D37
Françoise Giroud- Laboratoire TIMC-IMAG/Equipe DyCTiMUE Bio24a – La Bio-informatique (UJF/DLST - Année 2011-2012) – 4 Février 2013
D38
Françoise Giroud- Laboratoire TIMC-IMAG/Equipe DyCTiMUE Bio24a – La Bio-informatique (UJF/DLST - Année 2011-2012) – 4 Février 2013
D39
Françoise Giroud- Laboratoire TIMC-IMAG/Equipe DyCTiMUE Bio24a – La Bio-informatique (UJF/DLST - Année 2011-2012) – 4 Février 2013
D40
Françoise Giroud- Laboratoire TIMC-IMAG/Equipe DyCTiMUE Bio24a – La Bio-informatique (UJF/DLST - Année 2011-2012) – 4 Février 2013
D41
Françoise Giroud- Laboratoire TIMC-IMAG/Equipe DyCTiMUE Bio24a – La Bio-informatique (UJF/DLST - Année 2011-2012) – 4 Février 2013
D42
Françoise Giroud- Laboratoire TIMC-IMAG/Equipe DyCTiMUE Bio24a – La Bio-informatique (UJF/DLST - Année 2011-2012) – 4 Février 2013
D43
Françoise Giroud- Laboratoire TIMC-IMAG/Equipe DyCTiMUE Bio24a – La Bio-informatique (UJF/DLST - Année 2011-2012) – 4 Février 2013
D44
Françoise Giroud- Laboratoire TIMC-IMAG/Equipe DyCTiMUE Bio24a – La Bio-informatique (UJF/DLST - Année 2011-2012) – 4 Février 2013
D45
Françoise Giroud- Laboratoire TIMC-IMAG/Equipe DyCTiMUE Bio24a – La Bio-informatique (UJF/DLST - Année 2011-2012) – 4 Février 2013
D46
Françoise Giroud- Laboratoire TIMC-IMAG/Equipe DyCTiMUE Bio24a – La Bio-informatique (UJF/DLST - Année 2011-2012) – 4 Février 2013
D47
Françoise Giroud- Laboratoire TIMC-IMAG/Equipe DyCTiMUE Bio24a – La Bio-informatique (UJF/DLST - Année 2011-2012) – 4 Février 2013
D48
Françoise Giroud- Laboratoire TIMC-IMAG/Equipe DyCTiMUE Bio24a – La Bio-informatique (UJF/DLST - Année 2011-2012) – 4 Février 2013
D49
Françoise Giroud- Laboratoire TIMC-IMAG/Equipe DyCTiMUE Bio24a – La Bio-informatique (UJF/DLST - Année 2011-2012) – 4 Février 2013
D50
CLUSTALL :Algorithme de type progressif.
Composé de trois étapes :
Alignement par paires
Calcul d’un arbre de guidage
Alignement progressif.
Alignement multiple de séquences ?
ABCD
10---D210--C9410-B27510A
DCBAMatrice desimilarité
Arbre deguidage
BDACsimilarité
Françoise Giroud- Laboratoire TIMC-IMAG/Equipe DyCTiMUE Bio24a – La Bio-informatique (UJF/DLST - Année 2011-2012) – 4 Février 2013
D51
CLUSTALL :Algorithme de type progressif.
Composé de trois étapes :
Calcul d’un arbre de guidage
Alignement progressif.
Alignement multiple de séquences ?
Arbre deguidage
BDACsimilarité
BD
Alignement des paires les plus similairesGaps pour optimiser l’alignement
AC
AC
BD
Nouveaux gaps pour optimiserL’alignement (BD) avec (AC)
Françoise Giroud- Laboratoire TIMC-IMAG/Equipe DyCTiMUE Bio24a – La Bio-informatique (UJF/DLST - Année 2011-2012) – 4 Février 2013
D52
Françoise Giroud- Laboratoire TIMC-IMAG/Equipe DyCTiMUE Bio24a – La Bio-informatique (UJF/DLST - Année 2011-2012) – 4 Février 2013
D53
Françoise Giroud- Laboratoire TIMC-IMAG/Equipe DyCTiMUE Bio24a – La Bio-informatique (UJF/DLST - Année 2011-2012) – 4 Février 2013
D54
Merci de votre attention !!!!!!!!