Algorithme d'Alignement avec gap

• S1 = ACCGTGCCACAT ... S2 = GGACGTACCAGCG

• 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   0  0  0  0  0  0  0  0  0  0  0  0            

    1  G  0   0  0  0  2  0  2  0  0  0  0  0  0
    2  G  0   0  0  0  2  1  2  1  0  0  0  0  0
    3  A  0   2  0  0  0  1  0  0  0  2  0  2  0
    4  C  0   0  4  2  0  0  0  2  2  0  4  0  0
    5  G  0   0  1  3  4  1  2  0  1  1  2  3  0
    6  T  0   0  0  0  2  6  3  1  0  0  0  0  2
    7  A  0   2  0  0  0  3  5  2  0  2  0  2  0
    8  C  0   0  4  2  0  0  2  7  1  0  4  1  1
    9  C  0   0  2  6  3  0  0  4  9  6  3  3  0
   10  A  0   2  0  3  5  2  0  1  6 11  8  5  2
   11  G  0   0  1  0  2  4  4  0  3  8 10  7  6
   12  C  0   0  2  3  0  3  3  6  3  5 10  9  6
   13  G  0   0  0  0  5  0  5  3  5  2  7  9  8

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