Comparaison de deux séquences avec gaps : score local et p

ContexteL’analyse d’une séquence

Comparaison de deux séquencesQue faut-il penser de tout ça ?

Comparaison de deux séquences avec gaps :score local et p-valeur

Sabine MERCIER

Institut de Mathématiques de Toulouse (IMT)Laboratoire de Statistique et Probabilités (LSP)

Université Toulouse le Mirail (UTM)[email protected]

Nancy, 28 mars 2008

Sabine MERCIER Comparaison de deux séquences avec gaps 1/46



Plan

1 ContexteLes séquences biologiquesModélisation

2 L’analyse d’une séquenceScore local pour une séquenceSignification statistique

3 Comparaison de deux séquencesAlignementS et scores d’alignementSSignification statistiqueLes derniers résultats sur les gaps

4 Que faut-il penser de tout ça ?




Les séquences biologiquesModélisation

Plan









Les séquences biologiques (1/3)

Un peu de biologie moléculaire.Les types de séquences biologiques.











Protéine : la stucture primaire correspond à la séquence desacides aminés.

>1A6A : A HLA-DR3HVIIQAEFYLNPDQSGEFMFDFDGDEIFHVDMAKKETVWRLEEFGRFASFEAQGALANIAVDKANLEIMTKRSNYTPITNVPPEVTVLTNSPVELREPNVLICFIDKFTPPVVNVTWLRNGKPVTTGVSETVFLPREDHLFRKFHYLPFLPSTEDVYDCRVEHWGLDEPLLKHEF





Modélisation des séquences biologiques (1/2)

Les séquences biologiques correspondent à une suite decaractères pris dans un alphabet (fini) adapté au type desséquences.

A = {A,C,G,T}, A = {A,C,D, . . . ,U},

ou A = {α, β,U , . . .}, . . .

Mathématiquement, les séquences sont modélisées par unesuite de variables à valeurs dans A

A = A1 . . .An Ak → A

>1A6A : A HLA-DR3 = HVIIQAEFYLNP...HWGLDEPLLKHEF





Modélisation des séquences biologiques (2/2)

A = A1 . . .An, Akv .a.→ A. Comment varient-elle ?

Modèle M0 ou IID (Indépendantes et IdentiquementDistribuées) : le moins réaliste, le plus utilisé.Modèle markovien M1 ou plus.Les chaînes de Markov cachés (HMM) : il peut prendre encompte par exemple l’hétérogénéité des séquences(codant/non-codant).





Longueur des séquences

Génome humain :3 milliards de paires de bases.Bactérie :'4600 kb (E. Coli).Protéine :de '10 à '1000 d’a.a., 350 a.a. en moyenne.




Score local pour une séquenceSignification statistique

Plan









L’analyse d’une séquence

On cherche le segment le plus “quelque chose”.

1 Cette recherche s’effectue par rapport à un critère :hydrophobicité, acidité, etc...

→ choix d’une échelle de scores

2 On regarde quels segments ? Tous !

à longueur fixée→ fenêtre glissanteou bien de n’importe quel longueur→ score local





Echelles de scores : exemples

→ caractères physico-chimiques

Hydrophobicité(Kyte et Doolittle 1982)

A 1.8 C 2.5 D -3.5E -3.5 F 2.8 G -0.4H -3.2 I 4.5 K -3.9L 3.8 M 1.9 N -3.5P -1.6 Q -3.5 R -4.5S -0.8 T -0.7 V 4.2W -0.9 Y -1.3

Antigéniticité

A 0.12 C -0.12 D 0.31E 0.06 F -0.77 G -0.18H -0.65 I -2.92 K -0.05L 0.75 M 0.38 N -0.14P -0.05 Q -0.03 R -0.07S -0.01 T 0.21 V -0.01W -0.11 Y 0.01





Score local d’analyse - Exemple

Echelle d’hydrophobicité (Karlin et Altschul 1990) :

s =

I, L, V → +2F , M, A, C → +1G, S, Y , W , T , P → 0N, Q, H, D, E → −1K , R → −2

A = F C G K C V N I D K R A YX = +1 +1 0 −2 +1 +2 −1 +2 −1 −2 −2 +1 +0

Hn = max1≤i≤j≤n(Xi + · · ·+ Xj) → Hn = 4





Score local d’analyse - Le dessin

X : :

1 n i j

Sk

k 0

Sk = X1 + … + Xk

Hn

I

Sk





Signification statistique

Les scores locaux calculés sont-ils significatifs ?

Test : (Hypothèse privilégiée) séquence ordinaire(Hypothèse alternative) origine biologique

Etablir la distribution du score local

PH0[Hn ≥ a] p-valeur

Choix d’un modèle : X = (Xk ) i.i.d.





Approximation de Karlin - Résultat

(Karlin et al. 1990, 1992, 1993)Hypothèse : Scores en moyenne négatifs

loi de Hnn→+∞−→ loi de Gumble

entièrement définie par 2 paramètres λ et K

λ

racine d’une équationpolynomiale

E [eλXi ] = 0.

K

plus difficileà obtenir





Approximation de Karlin - Démonstration !

On définit des temps d’arrêt (échelles descendant).

X : :

1 n i j

Sk

k 0

Sk = X1 + … + Xk

T0 T1 T2 T3

Q1 Q2

Q3

Hn ' max1≤i≤nQ (Qi)

Théorie durenouvellement :la séquence estdécoupée en portionsi.i.d.





Loi exacte (1/3) (Daudin et al. 1999, 2000)

X : :

1 n i j

Sk

k 0

Sk = X1 + … + Xk

Wk

0 k

S0 = 0 Sk = Sk-1 + Xk

W0 = 0 Wk = max(0,Wk-1 + Xk)

T1 T2

T3





Loi exacte (2/3)

Ainsi, le score local correspond au maximum de W.

Hn = max1≤k≤nWk

W est un processus connu, le processus de Windley.

Pour X i.i.d., W est une chaîne de Markov d’ordre 1.

Loi du maximum d’une chaîne de Markov→ On sait faire !





Loi exacte (3/3)

Pour obtenir la p-valeur exacte P[Hn ≥ a],

On établit une matrice de taille

(a + 1)× (a + 1)

remplie à partir de la distribution des scores.Il faut élever cette matrice à la puissance n.





Avantages et inconvénients

Approximation

Calcul immédiatScore moyen négatifInadaptée aux courtesséquencesInadaptée pour E [Xi ] ' 0

Loi exacte

Exacte (choix du modèle !)Indépendant du signe duscore moyenAdaptée aux courtes etmoyennes longueursScores entiers outransformés





Conclusion

Deux méthodes ayant clairement leur propre champd’application : méthodes complémentaires.

La méthode exacte a de l’avenir.

Amélioration de l’implémentation (Nuel 2006)

Cas markovien (Hassenforder et al. 2003)

Prochaine étape : cas de deux séquences.




AlignementS et scores d’alignementSSignification statistiqueLes derniers résultats sur les gaps

Plan









Alignements de deux séquences (1/2)

1 2 3 4 5 6 7 8 9

A: G E N E P A F I N

B: M M G E B I E N M A N G 1 2 3 4 5 6 7 8 9 10 11 12

I

J

G E N - E P - A F I N M M G E B I E N M A NG

Ici, décalage de α = +2.

Un alignement local gappé est définipar les indices des lettres alignées

A : u(1) = 1 . . . u(4) = 4 . . . u(6) = 6

B : v(1) = 3 . . . v(4) = 7 . . . u(6) = 10

` u(.) v(.)





Alignements de deux séquences (2/2)

1


B: M M G E B I E N M A N G

3

I

J

G E N E PA F I N MM G E B I E NMANG

Longueur commune

3

Toujours un décalage de α = +2.

Un alignement local sans gap estdéfini par les indices de début dessegments et la longueur. Ici,

i = 1 j = 3 ` = 3





Matrices de similarité s(., .) =?

BLOSUM62 Substitution Matrix

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 S -1 4 1 -1 1 0 1 0 0 0 -1 -1 0 -1 -2 -2 -2 -2 -2 -3 T -1 1 4 1 -1 1 0 1 0 0 0 -1 0 -1 -2 -2 -2 -2 -2 -3 P -3 -1 1 7 -1 -2 -1 -1 -1 -1 -2 -2 -1 -2 -3 -3 -2 -4 -3 -4 A 0 1 -1 -1 4 0 -1 -2 -1 -1 -2 -1 -1 -1 -1 -1 -2 -2 -2 -3 G -3 0 1 -2 0 6 -2 -1 -2 -2 -2 -2 -2 -3 -4 -4 0 -3 -3 -2 N -3 1 0 -2 -2 0 6 1 0 0 -1 0 0 -2 -3 -3 -3 -3 -2 -4 D -3 0 1 -1 -2 -1 1 6 2 0 -1 -2 -1 -3 -3 -4 -3 -3 -3 -4 E -4 0 0 -1 -1 -2 0 2 5 2 0 0 1 -2 -3 -3 -3 -3 -2 -3 Q -3 0 0 -1 -1 -2 0 0 2 5 0 1 1 0 -3 -2 -2 -3 -1 -2 H -3 -1 0 -2 -2 -2 1 1 0 0 8 0 -1 -2 -3 -3 -2 -1 2 -2 R -3 -1 -1 -2 -1 -2 0 -2 0 1 0 5 2 -1 -3 -2 -3 -3 -2 -3 K -3 0 0 -1 -1 -2 0 -1 1 1 -1 2 5 -1 -3 -2 -3 -3 -2 -3 M -1 -1 -1 -2 -1 -3 -2 -3 -2 0 -2 -1 -1 5 1 2 -2 0 -1 -1 I -1 -2 -2 -3 -1 -4 -3 -3 -3 -3 -3 -3 -3 1 4 2 1 0 -1 -3 L -1 -2 -2 -3 -1 -4 -3 -4 -3 -2 -3 -2 -2 2 2 4 3 0 -1 -2 V -1 -2 -2 -2 0 -3 -3 -3 -2 -2 -3 -3 -2 1 3 1 4 -1 -1 -3 F -2 -2 -2 -4 -2 -3 -3 -3 -3 -3 -1 -3 -3 0 0 0 -1 6 3 1 Y -2 -2 -2 -3 -2 -3 -2 -3 -2 -1 2 -2 -2 -1 -1 -1 -1 3 7 2 W -2 -3 -3 -4 -3 -2 -4 -4 -3 -2 -2 -3 -3 -1 -3 -2 -3 1 2 11





Score d’alignement (1/2)

1


B: M M G E B I E N M A N G

3

I

J

G E N E PA F I N MM G E B I E NMANG

Longueur commune

3

i = 1 j = 3 ` = 3

Score d’alignement : on somme lesscores des couples.

+6 + 5− 2 = 9

maxi j `→ Hn,m





Score d’alignement (2/2)

1 2 3 4 5 6 7 8 9


B: M M G E B I E N M A N G 1 2 3 4 5 6 7 8 9 10 11 12

I

J

G E N - E P - A F I N M M G E B I E N M A NG

Choix de pénalité des gaps :−δ = −2.

u = 1,2,3,4,5,6v = 3,4,5,7,9,10` = 6

+6 + 5−2 + 5−2 + 4 − (2×2) = 12

maxu v `

→ Mn,m





Matrice de Smith et Waterman

C C C A T C C C - G

s(.,.) A C G T A +3 -4 -2 0 C +3 +1 -3 G +4 +2T +1

BA 0

C0

C0

G0

T 0

C 0 3 3 1 0 A 0 1 1 1 0 T 0 0 0 3 2

δ=-2

Alignements locaux optimaux

. . . T T − . . . T

. . . G . . . G G −

Mij = max

0

Mi−1,j − δMi,j−1 − δ

Mi−1,j−1 + s(Ai ,Bj)

Temps de calcul linéaire au produitdes longueurs n ×m.





BLAST

Basic Local Alignment Search Tool (Altschul et al., 1990)

Méthode de calcul approché du score local de Smith etWaterman (Mn,m).Le seul à proposer une signification statistique (E-value).Utilisé plusieurs centaines de milliers de fois par jour(NCBS).





Problème statistique

Les scores locaux calculés sont-ils significatifs ?

Test : (Hypothèse privilégiée) séquences indépendantes(Hypothèse alternative) ancêtre commun

Etablir la distribution du score local

PH0[Mm,n ≥ a] p-valeur

A = (Ak ) et B = (Bk ) i.i.d.





Signification statistique : état de l’art

1 Prise en compte des shifts :

p-valeur de Hn,m

2 Et des gaps :p-valeur de Mn,m

Tous ces résultats reposent sur le cas d’une séquence :

p-valeur Hn





Résultat autour de Karlin, SANS gap, Hn,m

G E N E P A F I N

M M G E B I E N M A N G

α=0 A : G E N EPAF I N B : MMG EB I ENM ANG Xα : -3-2+0+5 … -2

α=0

α=+8

A : G E N E PAFI N B : MMGEBIEN M A N G Xα : -3-1+6-2

α=+8

…

. .

.

Résultat cas 1 séquence”valable” cas 2 séquences.Dembo et al. 1994 ledémontrent pour n = m.

Loi de Hn,m

n→+∞−→

Loi de Gumble λu, Ku

longueur = nm





Autour des méthodes exactes, SANS gap, Hn,m

G E N E P A F I N

M M G E B I E N M A N G

α=0 A : G E N EPAF I N B : MMG EB I ENM ANG Xα : -3-2+0+5 … -2

α=0

α=+8

A : G E N E PAFI N B : MMGEBIEN M A N G Xα : -3-1+6-2

α=+8

…

. .

. Hn,m(A,B) = max

αHnα(Xα)

SI les décalages sontindépendants

P[Hn,m < a] =∏α

P[Hnα < a]

avec P[Hnα < a] p-valeurexacte du score local d’UNEséquence de longueur nα.





Comparaison des p-valeurs, cas SANS gap

pu : ExactepF : Karlinpe : Référence





Les résultats autour de Karlin : cas des GAPS

On a toujours une loi de Gumble : λg , Kg , mn.

ConjecturesConfirmées par simulations.(Mott 1992, Vingron et al. 1994,Altschul et al. 1996, Spang et al. 1998)Calcul de λg et Kg : par ajustement (bases de données ousimulations).(Pearson et al. 1988, Pearson 1998,Altschul et al. 2001, Bundschuh 2002).

Résultats théoriques partiels : coût des gaps lourd.(Bailey et Gribskov 2002).p-valeur approchée pour un score local gappé différent decelui de Smith et Waterman (Mott et Tribe 1999)





Les derniers résultats sur les gaps

Mais comment prendre en compte les gaps ! ?

Méthode des h-uplets (Fayyaz et al. 2007)GEM : Greedy Extention Method (Mott et Tribe 1999)





Méthode h-uplets (1/5) : un nouveau score local

A

B α

h lettres (ici h=3)

Aαhi

AHY AHY

AVL KLY

UZN

EHB

CFE

FGN

Soit un décalage α et un entier h >0

Soit S une fonction de scores de Ah ×Ah

S(CFE ,FGN) S(AHY ,KLY ) S(AHY ,AVL) . . .

Xαh = −2 +1 +2 . . .

Soit Hnαh le score local de LA séquence Xαh.





Méthode h-uplets (2/5)

On définit

Mhm,n = maxα Hnαh

Introduction des gaps par la fonction des scores (Zhang 1995).

S = score global avec gaps des h-uplets (s :BLOSUM62, δ=-1)

S(CUY ,AYG) = +2 : −→ C U Y −A − Y G

α −1−2 +2−1 +3−3 · · · → C U Y − . . . U D − TA − Y G . . . − D G N






La signification statistique deMhm,n ?

On adapte le résultat du score local sans gap avec shifts.La différence est sur l’alphabet, Ah au lieu de A.Une fonction de score qui fait aparaître les gaps.






Choix de h ? Test pour 2 ≤ h ≤ 4.

Pour des séquences courtes et moyennes,h = 2 donne de meilleurs résultats et c’est rapide.Pour des séquences plus grandes (' 1000),h = 4 donne de meilleurs résultats.









Plan








Conclusion

Bilan des différents travaux

p-valeur du score local gappé reste un problème important.Les méthodes en ligne ne sont pas satisfaisantes.Il faut implémenter les derniers résultats.




Conclusion

Mon “sentiment”

Il n’est pas raisonable de se focaliser sur le score local deSmith et Waterman.Définir un score local gappé proche de celui réellementcalculé et trouver sa p-valeur.

Le problème probabiliste est difficilecar l’outil est compliqué.




Conclusion

Perspectives et idées

Net effort sur les temps de calculs.Loi du nombre de gaps dans l’alignement réalisant le scorelocal.Actuellement, la séquence requête comme la base dedonnées sont considérées aléatoires.p-valeur d’un score local conditionnellement à la requête ?


Documents

Comparaison de deux séquences avec gaps : score local et p