Alignement de séquences (2/2) - [TIMC-IMAG] : Pages …membres-timc.imag.fr/Francoise.Giroud/Bio24a/pdf/TD3… · · 2013-02-04UE Bio24a – La Bio-informatique (UJF/DLST - Année

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.


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


D3


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


D4

B Aspartic Acid ou Glutamic AcidZ Glutamine ou Glutamic AcidX inconnu Proprités physico-chimiques

diagramme Venn


Rappel sur les acides aminés ….


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


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


D7

Calcul de score : matrices de similarité

Alignement des séquences


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


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


D10


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 :


D11


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.


D12


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.


D13

Etape 1 :Construction dela matrice de comparaison. Matrice(m,n)

Etape 2 :Transformation de la matrice par addition des scores.


Construire des alignements de séquence ?Programmation dynamique :

Alignement global de Needlemann & Wunsch (1970)

http://www.info.univ-angers.fr/~richer/recbioal3.php


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 :


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


D15




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


D16




Matrice transformée finale :Matrice transformée intermédiaire :

Processus ascendant


D17

Etape 3 :Chemin des scores maxima



ij

j

i

Processus descendant


D18



Alignement local de Smith-Waterman (1981)

Les deux séquences présentent une similarité que l’alignement global ne révèle pas !!!!!


D19


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.


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


D21


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 ….


D22


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.


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)

???


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)

???


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.


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)


D27


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.


D28


Evaluer les résultats de BLAST : les indicateurs


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/


D30


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.


D31


Les différents programmes BLAST :


D32

Choisir le programme :

Choisir l’espèce étudiée :

http://blast.ncbi.nlm.nih.gov/Blast

Choisir la base de données :


D33

Entrer la séquence requête :

Ajuster la sélection de la

base de données :

Optimisez les contraintes de

sélection :


D34

Réglez les paramètres de

votre recherche :


D35

Les résultats !!


D36


D37


D38


D39


D40


D41


D42


D43


D44


D45


D46


D47


D48


D49


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é


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)


D52


D53


D54

Merci de votre attention !!!!!!!!

Documents

Alignement de séquences (2/2) - [TIMC-IMAG] : Pages …membres-timc.imag.fr/Francoise.Giroud/Bio24a/pdf/TD3… · · 2013-02-04UE Bio24a – La Bio-informatique (UJF/DLST - Année