M1 Bioinformatique, Connaissances et Donn´ees - Master Stic pour la Sant´e
GMIN220 - Alignement
Ann´ee 2014-2015
TD 1 : Programmation dynamique
Anne-Muriel Arigon Chifolleau - Universit´e Montpellier, LIRMM
[email protected]
1
Alignement global
G
G
C
T
G
A
C
G
A
T
C
M´
ethode de distance :
â s : une matrice de score
â g : coˆ
ut associ´
e`
a un indel
â initialisation
M (0, 0) = 0
M (0, j) = g × j
M (i, 0) = g × i
â remplissage

 M (i − 1, j − 1) + s(xi , yj )
M (i − 1, j) + g
M (i, j) = min

M (i, j − 1) + g
ici g = 3 et s(a, b) = 3 si a 6= b et 0 si a = b
1
match ou mismatch
d´
el´
etion
insertion
2
Alignement local
G
G
C
T
G
A
C
C
A
C
C
G
A
T
C
A
C
T
T
C
C
A
T
G
Sch´
ema de score :
â s : une matrice de score
â g : p´
enalit´
e associ´
e`
a un indel
â initialisation
M (0, 0) = 0
M (0, j) = 0
M (i, 0) = 0
â remplissage

M (i − 1, j − 1) + s(xi , yj )



M (i − 1, j) + g
M (i, j) = max
M (i, j − 1) + g



0
ici g = −1 et s(a, b) = −1 si a 6= b et 2 si a = b
2
match ou mismatch
d´
el´
etion
insertion
T
T
3
Alignement avec p´
enalit´
e de gap affine
Fonction : c(g) = −d − (g − 1) × e
Match ou mismatch :

 M (i − 1, j − 1) + s(xi , yj )
D(i − 1, j − 1) + s(xi , yj )
M (i, j) = max

I(i − 1, j − 1) + s(xi , yj )
D´
el´
etion :
M (i − 1, j) − d
D(i − 1, j) − e
M (i, j − 1) − d
I(i, j − 1) − e
D(i, j) = max
Insertion :
I(i, j) = max
— Matrice M :
C
T
G
A
C
A
T
C
T
G
A
C
A
T
C
T
G
A
C
A
T
C
T
A
— Matrice D :
C
T
A
— Matrice I :
C
T
A
ici d = 3, e = 1 et s(a, b) = −1 si a 6= b et 2 si a = b
3
4
Alignement de motifs r´
ep´
et´
es en tandem
Aligner T =CTCTAGC avec une r´ep´etition en tandem du motif P =ACT, avec Ins = Del = 2 et Sub(a, b) = 3 si a 6= b et 0
sinon.
A
C
T
C
T
A
G
C
4
C
T

Julien Baste –