Comparaison et alignement de séquencesbioc.polytechnique.fr/biocomputing/courses/Alignements_M2.pdf · Q 7-1 -4 Y 8 4 F 8 Extrait de la matrice empirique BLOSUM50. P(x i,y j) = probabilité

Comparaison et alignementde séquences

Mastère Ingénierie et Chimie des BioMoléculesModule Bioinformatique structurale. Cours I

Novembre 2017T. Simonson, Ecole Polytechnique

● Comparaisons de séquences: pourquoi faire?

● L'alignement de séquences commemodèle d'un processus évolutif

● Alignement de séquences: algorithmes

● Déroulement du module Bioinformatique

Arbrephylogénétique

retraçantl'évolution

des globines.

Millio ns d'a nnées

1) Les protéines similaires ont souvent unancêtre commun: Exemple des globines

Gène X

Gène X Gène X

Spéciation

Divergence

Orthologues

Les protéines similaires ont souventun ancêtre commun

Gène X

Gène X Gène X

Gène Y Gène Z

Duplication

Divergence

Paralogues

Gène X

Gène X Gène X

Gène Y Gène Z

Duplicationaccidentelle

Divergence

Paralogues

Les paralogues changent généralement de fonction

La duplication conduit à des gènes paralogues

individu

individu +descendance

population

invasionde la

population

Gène X

Gène X Gène X

Gène Y Gène Z

Divergence

Paralogues

Les paralogues changent généralement de fonction

La duplication conduit à des gènes paralogues

Duplicationaccidentelle

X

duplication

spéciation

spéciation

duplication

AB

B1B2

a b1 c1b2 c2 c3

paralogues

temps

orthologues

Evolution d'un gène par spéciation, duplication et divergence

Séquence Structure

Fonction

2) Les protéines similaires ont souventdes structures et fonctions similaires

KLHGGPMLDSDQKFWRTPAAL

Launay & SimonsonBMC Bioinformatics2008

A partir de 60% d'identité de séquence on peut dire avec confiance que deux homologues ont la même fonction.

A partir de 35% d'identité des complexes homologues vont probablement interagir de manière homologue.

L'alignement de séquences comme modèle d'un processus évolutif

L'alignement comme modèled'un processus évolutif

Hypothèse: deux protéines similairesont toujours un ancêtre commun

T C L I C G D E A S G C H Y

T C L V C G D E A T G Y H Y

L C V V C G D K A T G Y H Y

Récepteur de l'androstérone

Ancêtre commun hypothétique

Récepteur de l'hormone thyroïdienne

Mutations hypothétiques en rouge

L'hypothèse ci-dessus est-elle vraisemblable?

L'alignement comme hypothèsed'un ancêtre commun “parsimonieux”

Un modèle probabiliste d'évolution

P(xi,y

j) = probabilité d'observer x

i aligné avec y

j

P(xi ¹

y

j) = P(“x

i muté en y

j” ou “y

j muté en x

i”)

P(xi =

y

j) = P(“x

i conservé”)

● Probabilités estimées à partir d'alignements tests

● Hypothèse de positions équivalentes et indépendantes



séquence x:séquence y:

La vraisemblance ou probabilité d'un alignement


L C V V - G D K A T G Y H Y


Récepteur de l'hormonethyroïdienne

Mutations probables alignement probable

Mutations improbables alignement improbable

En comparant des protéines homologues, on voitque les mutations ont des probabilités différentes

androgène VFFKRAAEG--KQKYLCASRNDCTIDKFRRKNCPSCRLRKCYprogestérone VFFKRAVEG--HHNYLCAGRNDCIVDKIRRKNCPACRLRKCYminéralocorticoïde VFFKRAVEG--QHNYLCAGRNDCIIDKIRRKNCPACRLQKCLglucocorticoïde VFFKRAVEG--QHNYLCAGRNDCIIDKIRRKNCPACRYRKCLestrogène AFFKRSIQG--HNDYMCPATNQCTIDKNRRKSCQACRLRKCYacide rétonïque GFFRRSIQK--NMVYTCHRDKNCIINKVTRNRCQYCRLQKCFvitamine D3 GFFRRSMKR--KALFTCPFNGDCRITKDNRRHCQACRLKRCVthyroïde GFFRRTIQKNLHPTYSCKYDSCCVIDKITRNQCQLCRFKKCL **:*: . : : * : * *. * ** ::*


androgen CLICGDEASGAHYGALTCGSCKVFFKRAAEGKQKYL-CASRNDCTIDKFRRKNCPSCRLRKCYEAGMTLGARev Erb CKVCGDVASGFHYGVLACEGCKGFFRRSIQQNIQYKRCLKNENCSIVRINRNRCQQCRFKKCLSVGMSRD-glucocorticoid CLVCSDEASGCHYGVLTCEGCKAFFKRAVEGQHNYL-CKYEGKCIIDKIRRKNCPACRYRKCLQAGMNLEAretinoic acid CAICGDRSSGKHYGVYSCEGCKGFFKRTVRKDLTYT-CRDNKDCLIDKRQRNRCQYCRYQKCLAMGM---

Se fixent sur l'ADN et régulentl'expression génétiquesous le contrôle de petitsligands: stéroïdes, vitamines, ...

Récepteurs nucléaires

Les mutations ont des probabilités différentes

androgène VFFKRAAEG--KQKYLCASRNDCTIDKFRRKNCPSCRLRKCYprogestérone VFFKRAVEG--HHNYLCAGRNDCIVDKIRRKNCPACRLRKCYminéralocorticoïde VFFKRAVEG--QHNYLCAGRNDCIIDKIRRKNCPACRLQKCLglucocorticoïde VFFKRAVEG--QHNYLCAGRNDCIIDKIRRKNCPACRYRKCLestrogène AFFKRSIQG--HNDYMCPATNQCTIDKNRRKSCQACRLRKCYacide rétinoïque GFFRRSIQK--NMVYTCHRDKNCIINKVTRNRCQYCRLQKCFvitamine D3 GFFRRSMKR--KALFTCPFNGDCRITKDNRRHCQACRLKRCVthyroïde GFFRRTIQKNLHPTYSCKYDSCCVIDKITRNQCQLCRFKKCL **:*: . : : * * : * *. * ** ::*

PHE F

TYR Y

homologues

KYLNYLNYLNYLDYMVYTLFTTYS :

Les propriétés structurales des acides aminés fontque les mutations ont des probabilités différentes

Les propriétés structurales des acides aminés fontque les mutations ont des probabilités différentes

LYS K

ARG R

GLN Q

homologues

RKCYRKCYQKCLRKCLRKCYQKCFKRCVKKCL::*

Un modèle probabiliste d'évolution

P(xi,y


i aligné avec y

j

P(xi ¹

y

j) = P(“x

i muté en y

j” ou “y

j muté en x

i”)

P(xi =

y

j) = P(“x

i conservé”)

● Probabilités estimées à partir d'alignements tests




séquence x:séquence y:

Difficulté: qu'est-ce qu'une grande probabilité?Alignement avec le récepteur humain de la progestérone

PQKTCLICGDEASGAHYGALTCGSCKVFFKRAAEGKQKYLCASRNDCTIDKFRRKNCPSCPQRVCVICGDEASGCHYGVLTCGSCKVFFKRAVEGHHQYLCAGRNDCIVDKIRRKNCPAC**' *'******** *** ************* ** '**** **** '** ******'*

Alignement avec le récepteur humain de l'hormone thyroïdienne

PQKTCLICGDEASGAHYGALTCGSCKVFFKRAAEG--KQKYLCASRNDCTIDKFRRKNCPSCKDEQCVVCGDKATGYHYRCITCEGCKGFFRRTIQKNLHPTYSCKYDSCCVIDKITRNQCQLC *''***'*'* ** '** ** **'* ' * * * *** * * *

Alignement avec la ferrédoxine de la bactérie Proteus vulgaris

PQKTCLICGDEASGAHYGTLTCGSCKVFFKRAAEGKQKYLCASRNDCTIDKFRRKNCPSCDQDKCIGCKTCVLACPYGTMEVVSRPVMRKLTALNTIEAFKAEANKCDLCHHRAEG-PAC * *' * ***' * * * * * * * ' * ' *'*

Modèle “aléatoire” comme point de référence

Q(xi,y


i et y

j

dans deux protéines indépendantes

= qxi q

yjFréquences naturelles de x

i, y

j

x qxW 1.3 % des acides aminés L 9.0 %

WW

LL

Hypothèse “évolutive”: deux séquences ont un ancêtre commun (parsimonieux)Hypothèse concurrente: elles n'ont aucune relation biologique: c'est comme si on cherchait à aligner deux séquences aléatoires, tirées au hasard.

Vraisemblance d'une colonne dans un alignement

M(xi,y

j) = log P(x

i,y

j)/Q(x

i,y

j)

= log [ P(xi,y

j)/q

xi q

yj ]



xi

yi

M = matrice de “score”

déf.

On prend toujours un ratio entre une probabilité P (scénario évolutif) et une probabilité Q (scénario aléatoire):

Une matrice empirique très utilisée: BLOSUM62 C S T P A G N D E Q H R K M I L V F Y W C 9 -1 -1 -3 0 -3 -3 -3 -4 -3 -3 -3 -3 -1 -1 -1 -1 -2 -2 -2 C S 4 1 -1 1 0 1 0 0 0 -1 -1 0 -1 -2 -2 -2 -2 -2 -3 S T 5 -1 0 -2 0 -1 -1 -1 -2 -1 -1 -1 -1 -1 0 -2 -2 -2 T P 7 -1 -2 -2 -1 -1 -1 -2 -2 -1 -2 -3 -3 -2 -4 -3 -4 P A 4 0 -2 -2 -1 -1 -2 -1 -1 -1 -1 -1 0 -2 -2 -3 A G 6 0 -1 -2 -2 -2 -2 -2 -3 -4 -4 -3 -3 -3 -2 G N 6 1 0 0 1 0 0 -2 -3 -3 -3 -3 -2 -4 N D 6 2 0 -1 -2 -1 -3 -3 -4 -3 -3 -3 -4 D E 5 2 0 0 1 -2 -3 -3 -2 -3 -2 -3 E Q 5 0 1 1 0 -3 -2 -2 -3 -1 -2 Q H 8 0 -1 -2 -3 -3 -3 -1 2 -2 H R 5 2 -1 -3 -2 -3 -3 -2 -3 R K 5 -1 -3 -2 -2 -3 -2 -3 K M 5 1 2 1 0 -1 -1 M I 4 2 3 0 -1 -3 I L 4 1 0 -1 -2 L V 4 -1 -1 -3 V F 6 3 1 F Y 7 2 Y W 11 W C S T P A G N D E Q H R K M I L V F Y W

Une matrice empirique très utilisée: BLOSUM62

Pénalty pour gaps: voir plus loinExc: calculer les valeurs de P(W,W) et P(L,L) et les commenter.

C S T P A G N D E Q H R K M I L V F Y W C 9 -1 -1 -3 0 -3 -3 -3 -4 -3 -3 -3 -3 -1 -1 -1 -1 -2 -2 -2 C S 4 1 -1 1 0 1 0 0 0 -1 -1 0 -1 -2 -2 -2 -2 -2 -3 S T 5 -1 0 -2 0 -1 -1 -1 -2 -1 -1 -1 -1 -1 0 -2 -2 -2 T P 7 -1 -2 -2 -1 -1 -1 -2 -2 -1 -2 -3 -3 -2 -4 -3 -4 P A 4 0 -2 -2 -1 -1 -2 -1 -1 -1 -1 -1 0 -2 -2 -3 A G 6 0 -1 -2 -2 -2 -2 -2 -3 -4 -4 -3 -3 -3 -2 G N 6 1 0 0 1 0 0 -2 -3 -3 -3 -3 -2 -4 N D 6 2 0 -1 -2 -1 -3 -3 -4 -3 -3 -3 -4 D E 5 2 0 0 1 -2 -3 -3 -2 -3 -2 -3 E Q 5 0 1 1 0 -3 -2 -2 -3 -1 -2 Q H 8 0 -1 -2 -3 -3 -3 -1 2 -2 H R 5 2 -1 -3 -2 -3 -3 -2 -3 R K 5 -1 -3 -2 -2 -3 -2 -3 K M 5 1 2 1 0 -1 -1 M I 4 2 3 0 -1 -3 I L 4 1 0 -1 -2 L V 4 -1 -1 -3 V F 6 3 1 F Y 7 2 Y W 11 W C S T P A G N D E Q H R K M I L V F Y W

Les mutations ont des probabilités différentes

K R Q Y FK 6 3 2 -2 -4R 7 1 -1 -3Q 7 -1 -4Y 8 4F 8

Extrait de la matrice empirique BLOSUM50

P(xi,y


i aligné avec y

j

= P(“xi conservé” ou “xi muté en y

j” ou “y

j muté en x

i”)

●Probabilités estimées à partir d'alignements tests

●Hypothèse de positions équivalentes

●Hypothèse de positions indépendantes: P(alignement) = P(i,j)

P(xi,y

j)



La vraisemblance ou probabilité d'un alignement

Vraisemblance ou “score” d'un alignement

s(xi,y

j) = log P(x

i,y

j)/Q(x

i,y

j)

= log [ P(xi,y

j)/q

xi q

yj ]

s(x,y) = S(i,j)

s(xi,y

j)



La probabilité de mutation dépend du temps

P(x,y) = P(x,y;T) = probabilité d'une mutation pendant le temps T

Une matrice de similarité vaut pour uneéchelle de temps, ou de similarité donnée.

BLOSUM50 BLOSUM62

Les cytochromes c de chimpanzee et d'humainsont plus similaires que les cytochromes cd'humain et d'Escherichia coli...

Il est nettement plus facile d'allonger un gapexistant que d'ouvrir un nouveau gap

●Ouvrir un gap: -d●L'allonger d'un résidu: -e (e<d)

●Coût d'un gap de longueur m:g(m) = -d – (m-1) e

Eg, boucles

Il faut un traitement plus réaliste des gaps

Les positions ne sont plus équivalentes ni indépendantes

En résumé, un alignement correspond àun modèle d'évolution, qui comprend:

● Hypothèse de divergence “minimale” depuis un ancêtre commun

● Détermination empirique des probabilités de mutations


● Un modèle de référence (hypothèse “nulle”)

L'alignement de séquences:algorithmes

Comparaison graphique de deuxséquences par une matrice densité

WWP * *Q * *R * *WW A A P Q R A A A P Q R A

On dispose les deux séquences sur les bords d'une matrice.Pour chaque paire de résidus similaires ou identiques, ondessine un point dans la matrice:

Séqu

e nce

2

Séquence 1

Comparaison graphique de deuxséquences par une matrice densité

cheval

humain

Cytochromes c

Récepteur estrogène

Récepteurandrogène

C'est souvent une partie d'une protéine qui estconservée: il faut chercher un alignement “local”

Aspartyl-ARNtsynthétasede levure

Domaine dusite actif,Aspartyl-ARNtsynthétased'E coli

BLAST: Basic Local Alignment Search Tool

● recherche de tétrapeptides homologues● extension de chaque peptide tant que la similarité > seuil

C L I C G D E A S G C H Y

L C V V G D K A T G Y H Y



G D E A scoreBLOSUM62

G D E A 21 = 6+6+5+4

G D D A 18G D Q A 18

G E E A 17 G D E G 17G D K A 17G D E V 17

Tétrapeptides homologues àun tétrapeptide de référence

V A G D E Q KA 0 4G 6D 6 2E 5 2 1

BLOSUM62

7 homologues (avec BLOSUM62 et un seuil de 17).

Eg: Tétrapeptides homologuesà la référence GDEA

>sp|P10827|THA_HUMAN Thyroid hormone receptor alpha Homo sapiens.MEQKPSKVECGSDPEENSARSPDGKRKRKNGQCSLKTSMSGYIPSYLDKDEQCVVCGDKATGYHYRCITCEGCKGFFRRTIQKNLHPTYSCKYDSCCVIDKITRNQCQLCRFKKCIAVGMAMDLVLDDSKRVAKRKLIEQNRERRRKEEMIRSLQQRPEPTPEEWDLIHIATEAHRSTNAQGSHWKQRRKFLPDDIGQSPIVSMPDGDKVDLEAFSEFTKIITPAITRVVDFAKKLPMFSELPCEDQIILLKGCCMEIMSLRAAVRYDPESDTLTLSGEMAVKREQLKNGGLGVVSDAIFELGKSLSAFNLDDTEVALLQAVLLMSTDRSGLLCVDKIEKSQEAYLLAFEHYVNHRKHNIPHFWPKLLMKEREVQSSILYKGAAAEGRPGGSLGVHPEGQQLLGMHVVQGPQVRQLEQQLGEAGSLQGPVLQHQSPKSPQQRLLELLHRSGILHARAVCGEDDSSEADSPSSSEEEPEVCEDLAGNAASP

G D E AG D D AG D Q AG E E A G D E GG D K AG D E V

On identifie dans la séquence cible untétrapeptide homologue à la séquence de référence

C L I C G D E A S G C H Y

L C V V G D K A T G Y H Y



On étend le “micro-alignement” dans chaquedirection, tant que le score > seuil

●Chaque tétrapeptide homologue conduit à un alignement local sans gaps●On retient les meilleurs alignements

Homologues du récepteur de l'androstéroneidentifiés avec BLAST

ID % Match # Swissprot Hit Description Score E Identity Length

(bits) * 1 P15207 ANDR_RAT Androgen receptor. 162 1e-40 100 73 6 P19091 ANDR_MOUSE Androgen receptor. 162 1e-40 100 73 14 Q63449 PRGR_RAT Progesterone receptor (PR) 136 1e-32 80 72 17 P06401 PRGR_HUMAN Progesterone receptor (PR) 136 1e-32 80 72 21 P08235 MCR_HUMAN Mineralocorticoid receptor (MR) 136 1e-32 79 72 33 P04150 GCR_HUMAN Glucocorticoid receptor (GR) 131 3e-31 77 72 41 Q9YH32 ESR2_ORENI Estrogen receptor beta (ER-beta) 99 3e-21 58 72 42 Q9YH33 ESR1_ORENI Estrogen receptor (ER-alpha) 98 4e-21 55 72 : : : : : : : : : : : : : : : : : :343 Q9N4Q7 NH13_CAEEL Nuclear hormone receptor nhr-13 54 8e-08 39 66344 Q23294 NH11_CAEEL Nuclear hormone receptor nhr-11 54 8e-08 42 66345 O45460 NH54_CAEEL Nuclear hormone receptor nhr-54 54 1e-07 37 67346 Q09565 NH20_CAEEL Nuclear hormone receptor nhr-20 51 7e-07 34 66347 Q09587 NH22_CAEEL Nuclear hormone receptor nhr-22 45 5e-05 32 66349 P17672 E75B_DROME Ecdysone-induced protein 75B 40 0.001 37 47351 P20659 TRX_DROME Trithorax protein. 31 0.74 26 49355 P98164 LRP2_HUMAN Lipoprotein receptor. 30 1.7 27 65

*E = espérance du nombre d'alignements fortuits de score supérieur

Une méthode plus rigoureuse, qui s'inspirede la “matrice” déja vue

P Q R A

SP * Q * R *

On dispose les deux séquences sur les bords d'une matrice:

Séqu

ence

2

Séquence 1

Une méthode plus rigoureuse; présentation partielle

P Q R A

SP * Q * R *

On dispose les deux séquences sur les bords d'une matrice.Un alignement correspond à une ligne à travers la matrice:

Séqu

ence

2

Séquence 1

P Q R A

SP Q R Sé

quen

ce 2

Séquence 1

-PQRASPQR-

Exc: représenter les alignements suivants: P-QRASPQR-

P--QRASPQ-R-

Un alignement correspond à une ligne à travers la matrice.Une ligne “incomplète” correspond à un alignement incomplet:

P Q R A

SP Q R

-PQRASPQR-

P Q R A

SP Q R

-PQSPQ


Un alignement correspond à une ligne à travers la matrice.On annote la table avec les scores:

P Q R A

SP Q R

P Q R A

0

S-8

P -1

Q 4

R 9 1

-PQRASPQR-

S P Q RP -1 7 -1 -2Q 0 -1 5 1R -1 -2 1 5A 1 -1 -1 -1


P Q R A

0

S-8

P -1

Q 4

R 9 1

L'alignement optimal est en compétition avec beaucoup d'autres alignements possibles:

P-QRASPQR-

P Q R A

0

S -1

P -9

Q -4

R 1 -7

-PQRASPQR-


P Q R A

0

S-8

P -1

Q 4

R 9 1

L'alignement optimal est en compétition avec beaucoup d'autres alignements possibles:

P Q R A

0

S -1

P -9

Q -4

R 1 -7

PQ--RAS-PQR-

P Q R A

0

S -1 -9

P -17

Q -25

R -20 -28

P-QRASPQR-

-PQRASPQR-


Comment trouver le meilleur chemin à travers la table?

P Q R A

0

S

P

Q -1 -9

R 9 ?

Supposons que nous connaissons les scores de trois alignements particuliers:

Chaque score bleu correspond à unalignement incomplet, inconnu à ce stade.Pour le moment, nous n'avons pas besoinde savoir comment ces valeurs sont obtenues:elles sont admises.

A partir de ces 3 scores, je peux trouver le scoremanquant! Comment??


P Q R A

0

S

P

Q -1 -9

R 9 ?


A partir des 3 scores bleus, je peux trouverle score manquant!

3 possibilités: score -1 -1 = -2

score 9 - 8 = 1

score -9 - 8 = -17


P Q R A

0

S

P

Q -1 -9

R 9 1


A partir des 3 scores bleus, je peux trouverle score manquant!

3 possibilités: score -1 -1 = -2

score 9 - 8 = 1

score -9 - 8 = -17


P Q R A

0

S

P

Q 4 -1 -9

R -4 ?

Supposons que nous connaissons encore trois autres scores:

On peut construire progressivement un alignement optimal;pour une description complète de la méthode, voir Dardel & Képès


P Q R A

0

S

P

Q 4 -1 -9

R -4 9 1


Comment obtenir ces scores “intermédiaires”? Par une opérationde remplissage de la table entière, en commençant en haut à gauche.


P Q R A

0

S

P

Q 4 -1 -9

R -4 9 1


Comment obtenir ces scores “intermédiaires”? Par une opérationde remplissage de la table entière, en commençant en haut à gauche.

La méthode de Needleman-Wunsch: initialisation

P Q R A

0 -8 -16 -24 -32

S -8

P-16

Q-24

R-32

F(i,j)

F(i-1,j)F(i-1,j-1)

F(i,j-1)

-d

-d

s(xi,y

j)

y1 y

2 y

3 y

4 y

5 y

6

x1

x2

x3

x4

x5

Calcul récursif de F(i,j)

- P Q R A

Extension de F

-

S

P

Q

R

0 -8 -16 -24 -32

-8 -1 -8

P QS -1 0

Matrice de similarité

P Q- S

Coût pq en mémoire et calcul

La méthode de Needleman-Wunsch

P Q R A

0 -8 -16 -24 -32

S -8 -1 -8 -16 -23

P-16 -1 -2 -10 -15

Q-24 -9 4 -1 -9

R-32 -17 -4 9 1

Pour les détails, voir le livre de Dardel & Képès


P Q R A

0 -8 -16 -24 -32

S -8 -1 -8 -16 -23

P-16 -1 -2 -10 -15

Q-24 -9 4 -1 -9

R-32 -17 -4 9 1

Pour les détails, voir le livre de Dardel & Képès


P Q R A

0 -8 -16 -24 -32

S -8 -1 -8 -16 -23

P-16 -1 -2 -10 -15

Q-24 -9 4 -1 -9

R-32 -17 -4 9 1

Pour les détails, voir le livre de Dardel & Képès (chap. 2)

P Q R A

SP Q R Sé

que n

ce 2

Séquence 1

-PQRASPQR-

Alignements multiples:principes

Homologues du récepteur de l'androstéroneidentifiés avec BLAST

*E = espérance du nombre d'alignements fortuits de score supérieur

ID % Match # Swissprot Hit Description Score E Identity Length

(bits) * 1 P15207 ANDR_RAT Androgen receptor. 162 1e-40 100 73 6 P19091 ANDR_MOUSE Androgen receptor. 162 1e-40 100 73 14 Q63449 PRGR_RAT Progesterone receptor (PR) 136 1e-32 80 72 17 P06401 PRGR_HUMAN Progesterone receptor (PR) 136 1e-32 80 72 21 P08235 MCR_HUMAN Mineralocorticoid receptor (MR) 136 1e-32 79 72 33 P04150 GCR_HUMAN Glucocorticoid receptor (GR) 131 3e-31 77 72 41 Q9YH32 ESR2_ORENI Estrogen receptor beta (ER-beta) 99 3e-21 58 72 42 Q9YH33 ESR1_ORENI Estrogen receptor (ER-alpha) 98 4e-21 55 72 : : : : : : : : : : : : : : : : : :343 Q9N4Q7 NH13_CAEEL Nuclear hormone receptor nhr-13 54 8e-08 39 66344 Q23294 NH11_CAEEL Nuclear hormone receptor nhr-11 54 8e-08 42 66345 O45460 NH54_CAEEL Nuclear hormone receptor nhr-54 54 1e-07 37 67346 Q09565 NH20_CAEEL Nuclear hormone receptor nhr-20 51 7e-07 34 66347 Q09587 NH22_CAEEL Nuclear hormone receptor nhr-22 45 5e-05 32 66349 P17672 E75B_DROME Ecdysone-induced protein 75B 40 0.001 37 47351 P20659 TRX_DROME Trithorax protein. 31 0.74 26 49355 P98164 LRP2_HUMAN Lipoprotein receptor. 30 1.7 27 65

Méthode heuristique pour un alignement multiple:trois phases successives

● Alignement 2 à 2 des séquences

● Construction d'un arbre “guide”

● Alignement progressif séquences-profil

a) S T A Rb) S K A Tc) P I T

S T A RS K A T4 -1 4 -1

Score =6

S T A RP I T --1 -1 0 -8

S K A TP – I T-1 -8 -1 5

Score =-10 (Exc.)

Score =-5 (Exc.)

Phase 1: alignement des séquences 2 à 2

Phases 2, 3: on reprend le problème à zéro, entraitant les séquences dans un ordre intelligent

Phase 2: Classement des séquences par similarité

Phase 3: On les aligne progessivement,en commençant par les plus similaires

Phase 2: classement hiérarchique,ou arbre “guide”

a b

c d

a bc d

a b

c d 1

2

3

“Unweighted Pair Group Joining with Arithmetic Mean”

Phase 3: alignement des séquencesen remontant progressivement l'arbre

progesterone

mineralocorticoid

glucocorticoid

estrogen

vitamin D

PPAR

retinoic acid

thyroidandrogen

0.8

0.7

0.8

0.41.2

0.51.1

1.40.2

0.9

1.0

Phase 3: alignement des séquencesen remontant progressivement l'arbre

a b

c

a) S T A Rb) S K A T

a avec b

c avec {a, b}

Alignement “séquence-profil”

S T A RS T I RS K A T

PIT

P T -1 T -1 K -1total -3

0 -24

-27

Alignement séquence-profil:programmation dynamique


P I T

P T -1 T -1 K -1total -3

Aligner une séquence avec un alignement:calcul d'un score moyen

Alignement existant:

Séquence à aligner:

bs(a, b' ) = s(a,b) + s(a,b') + s(a,b'') b''

Sommede

paires

0 -24 -48 -72 -96

-24 -3 -27 -51 -75

-48 -19 -6 -25 -49

-72 -43 -10 -4 -22


PIT

S T A RT S A RS K I TP - I T

Alignement séquence-profil:programmation dynamique


PPIIGT

S T A RT S A RS K I TP - I TP - I G

Aligner deux profils ou alignements:calcul d'un score moyen

a bs( a' , b' ) = s(a,b) + s(a,b') b'' + s(a,b'')+ s(a',b) + s(a',b')+ s(a',b'')

Somme de paires

Produit final:androgène VFFKRAAEG--KQKYLCASRNDCTIDKFRRKNCPSCRLRKCYprogestérone VFFKRAVEG--HHNYLCAGRNDCIVDKIRRKNCPACRLRKCYminéralocorticoïde VFFKRAVEG--QHNYLCAGRNDCIIDKIRRKNCPACRLQKCLglucocorticoïde VFFKRAVEG--QHNYLCAGRNDCIIDKIRRKNCPACRYRKCLestrogène AFFKRSIQG--HNDYMCPATNQCTIDKNRRKSCQACRLRKCYacide rétinoïque GFFRRSIQK--NMVYTCHRDKNCIINKVTRNRCQYCRLQKCFvitamine D3 GFFRRSMKR--KALFTCPFNGDCRITKDNRRHCQACRLKRCVthyroïde GFFRRTIQKNLHPTYSCKYDSCCVIDKITRNQCQLCRFKKCL **:*: . : : * : * *. * ** ::*

584 588

588

Nécessité d'une validation expérimentale

● Mutagénèse des résidus conservés

● Mise en évidence d'une interaction avec un substrat ou inhibiteur

● Détermination de structures tri-dimensionnelles (!)

Matinées 9h30 – 12h30 Après midis 14h – 17h30 dates chapitres de la matinée (salles) après-midi------------------------------------------------------------------------------------------------------------ 9/11 Alignements de séquence (Becquerel) TP (SI33)

16/11 Modélisation (TBA) TP (SI33)

23/11 Modélisation, suite (PC13) + TD (SI33) TP (SI33)

30/11 TD (TBA) + TD (SI33) TP (SI33)

19/12 Reconnaissance moléculaire 1 (PC41) + TD (SI33) TP (SI33)

22/12 Reconnaissance moléculaire 2 + TD (PC41) TP (SI35) 04/01 TP (TBA) TP (TBA)

Contrôle: présentation d'un des TPs + contrôle oral le 11/1/[email protected] [email protected] Laboratoire de Biochimie, Ecole Polytechnique http://biology.polytechnique.fr/biocomputing/teach.html

Finished early, at 12:15. Started only 5' late (9h35)

Good rhythm, plenty of questions.

Careful: need to explain better Needleman-Wunsch:We fill the table recursively but also selectively: at each step, only the best segment is indicated and accumulated!Need at least one more slide for this; there's plenty of time.

Careful: check that classroom is NOT next to the opera class!!This year, opera was in PC6...

Documents

Comparaison et alignement de séquencesbioc.polytechnique.fr/biocomputing/courses/Alignements_M2.pdf · Q 7-1 -4 Y 8 4 F 8 Extrait de la matrice empirique BLOSUM50. P(x i,y j) = probabilité