Algorithme d'Alignement avec gap

• S1 = ACCGTGCCACAT ... S2 = AGACGTACCAGCG

• GAP = 3

  SUB(x,x) = 2 SUB(x,y) = -1

              1   2   3   4   5   6   7   8   9  10  11  12

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

        0    -3  -6  -9 -12 -15 -18 -21 -24 -27 -30 -33 -36

 1  A  -3     2  -1  -4  -7 -10 -13 -16 -19 -22 -25 -28 -31
 2  G  -6    -1   1  -2  -2  -5  -8 -11 -14 -17 -20 -23 -26
 3  A  -9    -4  -2   0  -3  -3  -6  -9 -12 -12 -15 -18 -21
 4  C -12    -7  -2   0  -1  -4  -4  -4  -7 -10 -10 -13 -16 
 5  G -15   -10  -5  -3   2  -1  -2  -5  -5  -8 -11 -11 -14
 6  T -18   -13  -8  -6  -1   4   1  -2  -5  -6  -9 -12  -9
 7  A -21   -16 -11  -9  -4   1   3   0  -3  -3  -6  -7 -10
 8  C -24   -19 -14  -9  -7  -2   0   5   2  -1  -1  -4  -7
 9  C -27   -22 -17 -12 -10  -5  -3   2   7   4   1  -2  -5
10  A -30   -25 -20 -15 -13  -8  -6  -1   4   9   6   3   0
11  G -33   -28 -23 -18 -13 -11  -6  -4   1   6   8   5   2
12  C -36   -31 -26 -21 -16 -14  -9  -4  -2   3   8   7   4
13  G -39   -34 -29 -24 -19 -17 -12  -7  -5   0   5   7   6

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