Alignement de sequences

Helene Touzet

Exemple: sequence de l’insuline

elephant FVNQHLCGSHLVEALYLVCGERGFFYTPKTGIVEQCCTGVCSLYQLENYCN

||||||||||||||||||||||||||||| ||| |||| |||||||||||

hamster FVNQHLCGSHLVEALYLVCGERGFFYTPKSGIVDQCCTSICSLYQLENYCN

elephant FVNQHLCGSHLVEALYLVCGERGFFYTPKTGIVEQCCTGVCSLYQLENYCN

||||||||||||||||||||||||||||| ||||||| |||||||||||

baleine FVNQHLCGSHLVEALYLVCGERGFFYTPKAGIVEQCCASTCSLYQLENYCN

elephant FVNQHLCGSHLVEALYLVCGERGFFYTPKTGIVEQCCTGVCSLYQLENYCN

|| ||||||| ||||||||||||| || ||||||| |||||||||||

alligator AANQRLCGSHLVDALYLVCGERGFFYSPKGGIVEQCCHNTCSLYQLENYCN

Alignement

I Mise en correspondance de deux sequences (ADN ou proteines)

R D I S L V - - - K N A G I

| | | | | | | |

R N I - L V S D A K N V G I

I Trois operations d’editionI substitution (match ou mismatch)I deletionI insertion

I A chaque operation est associe un score

I Le score de l’alignement est la somme des scores elementaires

I Probleme: etant donnees deux sequences, des scores associes achaque operation, trouver l’alignement de score maximal

Algorithme de Needleman& Wunsch (1970)

I programmation dynamique classique

I sequences ACGGCTAT et ACTGTAG

I scores match = 2, mismatch = -1 , insertion/deletion: GAP= -2

I que peut-il se passer pour la derniere operation?

I Substitution de T en GACGGCTA T

? ? ? |

ACTGTA G

score deACGGCTA

ACTGTA−1

I Deletion de T

ACGGCTA T

? ? ?

ACTGTAG -

score deACGGCTA

ACTGTAT−2

I Insertion de G

ACGGCTAT -

? ? ?

ACTGTA G

score deACGGCTAT

ACTGTA−2

Algorithme de Needleman& Wunsch (1970)

I Deux sequences U et V , de longueur m et n

I Sim(i , j) : score optimal entre U(1..i) et V (1..j)

I Formule de recurrence

Sim(0, 0) = 0

Sim(0, j) = Sim(0, j − 1) + Ins(V (j))

Sim(i , 0) = Sim(i − 1, 0) + Del(U(i))

Sim(i , j) = max

Sim(i − 1, j − 1) + Sub(U(i),V (j))

Sim(i − 1, j) + Del(U(i))

Sim(i , j − 1) + Ins(V (j))

I Etape 1: creation d’une table indexee par les deux sequences.

A C G G C T A T

0 −2 −4 −6 −8 −10 −12 −14 −16

A −2 2 0 −2 −4 −6 −8 −10 −12

C −4 0 4 2 0 −2 −4 −6 −8

T −6 −2 2 3 1 −1 0 −2 −4

G −8 −4 0 4 5 3 1 −1 −3

T −10 −6 −2 2 3 4 5 3 1

A −12 −8 −4 0 1 2 3 7 5

G −14 −10 −6 −2 −1 0 4 5 6

Case Sim(i , j) : score entre les i premieres bases de U=ACGGCTAT et les jpremieres bases de V=ACTGTAG.

I Etape 1: creation d’une table indexee par les deux sequences.

A C G G C T A T

0 −2 −4 −6 −8 −10 −12 −14 −16

A −2 2 0 −2 −4 −6 −8 −10 −12

C −4 0 4 2 0 −2 −4 −6 −8

T −6 −2 2 3 1 −1 0 −2 −4

G −8 −4 0 4 5 3 1 −1 −3

T −10 −6 −2 2 3 4 5 3 1

A −12 −8 −4 0 1 2 3 7 5

G −14 −10 −6 −2 −1 0 4 5 6

Cas de base - initialisationaa

I Etape 1: creation d’une table indexee par les deux sequences.

A C G G C T A T

0 −2 −4 −6 −8 −10 −12 −14 −16

A −2 2 0 −2 −4 −6 −8 −10 −12

C −4 0 4 2 0 −2 −4 −6 −8

T −6 −2 2 3 1 −1 0 −2 −4

G −8 −4 0 4 5 3 1 −1 −3

T −10 −6 −2 2 3 4 5 3 1

A −12 −8 −4 0 1 2 3 7 5

G −14 −10 −6 −2 −1 0 4 5 6

Remplissage ligne par ligneaa

I Etape 1: creation d’une table indexee par les deux sequences.

A C G G C T A T

0 −2 −4 −6 −8 −10 −12 −14 −16

A −2 2 0 −2 −4 −6 −8 −10 −12

C −4 0 4 2 0 −2 −4 −6 −8

T −6 −2 2 3 1 −1 0 −2 −4

G −8 −4 0 4 5 3 1 −1 −3

T −10 −6 −2 2 3 4 5 3 1

A −12 −8 −4 0 1 2 3 7 5

G −14 −10 −6 −2 −1 0 4 5 6

Remplissage ligne par ligneaa

I Etape 2 : recherche du chemin optimal dans la matrice.

A C G G C T A T

0 −2 −4 −6 −8 −10 −12 −14 −16

A −2 2 0 −2 −4 −6 −8 −10 −12

C −4 0 4 2 0 −2 −4 −6 −8

T −6 −2 2 3 1 −1 0 −2 −4

G −8 −4 0 4 5 3 1 −1 −3

T −10 −6 −2 2 3 4 5 3 1

A −12 −8 −4 0 1 2 3 7 5

G −14 −10 −6 −2 −1 0 4 5 6

I Etape 3 : construction de l’alignementSur le chemin des scores maximaux, on regarde quelle est l’operationcorrespondante.

insertion deletionsubstitution

ouidentite

I Resultat

A C G G C T A T

| | | | |

A C T G - T A G

Algorithme de Needleman & WunschAnalyse de la complexite

I Pour le calcul du score d’alignement (etape 1)

I O(n ×m) en tempsI O(min{n,m}) en espace

Au lieu de conserver toute la matrice de programmation dynamique, ontravaille sur deux vecteurs : la derniere ligne calculee, et la lignecourante.

I Pour la construction de l’alignement (etapes 1, 2 et 3)I O(n ×m) en temps et en espace

Alignement avec espace lineaire (Hirschberg)

I L’algorithme de Hirschberg permet de calculer le score du meilleuralignement avec un espace lineaire

I Plus fort: On sait calculer le score entre U et tous les prefixes de Ven temps quadratique et avec un espace lineaire

Alignement avec espace lineaire

I Methode de type Diviser pour regner

I A: alignement optimal entre deux sequences

I Que peut-il se passer pour U(i) ?

1. U(i) est aligne avec un certain V (j) (j ∈ [1..n])

A

(U(1..i − 1)V (1..j − 1)

)&

(U(i)V (j)

)&A

(U(i + 1..m)V (j + 1..n)

)2. U(i) est delete : U(i) est aligne avec un -, situe entre V (j) et

V (j + 1) (j ∈ [0..n])

A

(U(1..i − 1)V (1..j)

)&

(U(i)−

)&A

(U(1..i + 1)V (j + 1..n)

)

I Comment determiner le bon cas, 1 ou 2 ?

I Comment determiner la bonne valeur de j ?

Alignement avec espace lineaire

I Similarite entre U(1..i − 1) et tous les prefixes de VCalculable en espace lineaire

I Similarite entre U(i + 1..m) et tous les suffixes de VProbleme symetrique au precedent

Score(S,T:in Sequence,I:in Natural,

J:out Natural,Cas:out Boolean)

Calcule les scores d’alignement de U(1..i − 1) avec tous les prefixes de Vet les scores d’alignement de U(i + 1..n) avec tous les suffixes de V .Cas : Vrai, si l’alignement optimal correspond au cas 1,

Faux, s’il correspond au cas 2.

J : indice correspondant dans T

Alignement avec espace lineaireRecapitulation

I Division du probleme d’alignement entre U et V en deuxsous-alignements, suivant U(i) et V (j)

I i est fixe et j est determine en fonction de i

I Conclusion avec deux appels recursifs

I Quel indice choisir pour i ?

7-2 Lecture 7: September 30, 2004

Space-E!cient Sequence Alignment

The space complexity of the algorithms we have seen previously is proportional to the number of vertices in the edit graph, i.e. O(nm). Observe however that the only values needed to compute the alignment scores in column j in the DP table are the scores in column j ! 1. Therefore only two columns worth of space are required to compute the best score which is O(n). However, recall that we use the b matrix to store backtracking pointers in order to reconstruct the longest path in the edit graph. b is an nxm matrix, so some clever insight is needed to bring the space needs down.

Consider the edit graph. Any optimal alignment from (0, 0) to (n, m) must pass through the middle column m . We will show that we can find the point i at which

2 i, m

2the optimal alignment passes through the middle column, i.e. the point ( ) without knowing the longest path in the edit graph.

i, m 2 (i

, i, m 2 (i

(i, m 2

Vertex ( ) partitions the edit graph into two optimal paths: pref ix ) which is the optimal path from (0 0) to ( ) and suf f ix ) which is the optimal path from

) to (n, m). This is shown graphically in Figure 7.1.

Note that the optimal alignment is simply pref ix(i) + suf f ix(i). pref ix(i) can be

m

mm/2

Prefix(i)

Suffix(i)

(i, m/2)

Adapted from Figure 7.1: Linear-Space Sequence Alignment

7-3 Lecture 7: September 30, 2004

mcomputed by finding the score si, , i.e. we compute the score in linear space as shown 2

earlier for just the first half of the graph. To compute the suf f ix, we rely on the fact that in a DAG we can flip the direction of the edges and reverse the computation.

mThus, for the second half of the edit graph (nx 2 ), we can reverse edges and compute

the score from (n, m) to (i, m 2 ).

Combining pref ix(i) + suf f ix(i) gives the score of optimal alignment that passes through (i, m

2 ). Because the space-e!cient alignment score computation maintains column vectors, it is easy to determine max0!i!n (pref ix(i) + suf f ix(i)). This in turn gives the optimal i which defines the optimal midpoint.

This process can be repeated by continual halving and computing the midpoint as shown in Figure 7.2. By iteratively halving and computing the optimal alignment midpoints we can reconstruct the complete optimal alignment. Note that after each halving we’ve reduced the time complexity of the subproblem in proportion to the area of rectangle defined by the optimal midpoints. Finding the midpoint of each rectangle requires: area + area

4+ area + · · · . Thus, the total time complexity is O(nm).

2

0 m/8 m/4 3m/8 m/2 5m/8 3m/4 7m/8 m

Adapted from Figure 7.2: Iteratively Computing the Optimal Alignment Midpoints

function Align(U,V:Sequence) return Alignement is

M:Natural:=U’Length;

N:Natural:=V’Length;

begin

if M=0 then

return (1..N =>’-’, V);

elsif N=0 then

return (U, 1..M =>’-’);

else

Score(U, V, M/2, J, Cas);

if Cas then -- cas 1: substitution

return Align(U(1..M/2-1),V(1..J-1))

&(U(M/2), V(J))

&Align(U(M/2+1..M),V(J+1..N));

else -- cas 2: deletion

return Align(U(1..M/2-1),V(1..J))

&(U(M/2), ’-’)

&Align(U(M/2+1..M),V(J+1..N));

end if;

end if;

end Align;

Alignement avec espace lineaireAnalyse de la complexite

I En espace

I En temps

Alignement avec gaps affines

I Gap: succession de deletions ou d’insertions

I Un gap correspond a un seul evenement mutationnel

I Ouv : penalite d’ouverture de gap

I Ext : penalite d’extension de gap

T C A G A C G A G T C T C A G A C G A G T C

| | | | | | | | | | | | |

T C G G A - G C - T G T C G G A - - G C T G

Alignement avec gaps affinesAlgorithme

I Trois tables de programmation dynamique

I a(i , j) : score maximal d’un alignement entre U(1..i) et V (1..j) quitermine par la substitution de U(i) en V (j)

I b(i , j): score maximal d’un alignement entre U(1..i) et V (1..j) quitermine par l’insertion de V (j)

I c(i , j): score maximal d’un alignement entre U(1..i) et V (1..j) quitermine par la deletion de U(i)

Alignement avec gaps affinesAlgorithme

I Initialisation

a(0, 0) = 0a(i , 0) = −∞a(0, j) = −∞

b(i , 0) = −∞b(0, j) = Ouv + Ext× j

c(i , 0) = Ouv + Ext× ic(0, j) = −∞

Alignement avec gaps affinesAlgorithme

I Formules de recurrence

a(i , j) = Sub(i , j) + max

a(i − 1, j − 1)b(i − 1, j − 1)c(i − 1, j − 1)

b(i , j) = max

Ouv + Ext + a(i , j − 1)Ext + b(i , j − 1)Ouv + Ext + c(i , j − 1)

c(i , j) = max

Ouv + Ext + a(i − 1, j)Ouv + Ext + b(i − 1, j)Ext + c(i − 1, j)