[Subject home], [FAQ], [progress],   Bib', Alg's,  C , Java - L.A., Saturday, 30-Mar-2024 02:37:02 AEDT
Instructions: Topics discussed in these lecture notes are examinable unless otherwise indicated. You need to follow instructions, take more notes & draw diagrams especially as [indicated] or as done in lectures, work through examples, and do extra reading. Hyper-links not in [square brackets] are mainly for revision, for further reading, and for lecturers of the subject.

Dynamic Programming:   Introduction to Edit Distance

Allowable mutations:

  1. Change a letter
  2. Insert a letter
  3. Delete a letter

(A variation on E.D. also allows transposition of two adjacent letters as a single op..)

©
L
.
A
l
l
i
s
o
n

Is useful in:

(Incidentally, here's some DNA.)
Edit Distance example
    0 1 2 3 4 5 6 7 8 9 10 11 12
    - A C G T A C G T A C G T
0 -.............
1 A.............
2 C.............
3 T.............
4 A.............
5 C.............
6 C.............
7 T.............
8 A.............
9 C.............
10 A.............
11 G.............
12 T.............
D[ i , j ] = dist( A[ 1 .. i ], B[ 1 .. j ] )
Edit Distance example continued
      1 2 3 4 5 6 7 8 9 10 11 12
    - A C G T A C G T A C G T
  - 0 1 2 3 4 5 6 7 8 9 10 11 12
1 A.............
2 C.............
3 T.............
4 A.............
5 C.............
6 C.............
7 T.............
8 A.............
9 C.............
10 A.............
11 G.............
12 T.............
D[ i , j ] = dist( A[ 1 .. i ], B[ 1 .. j ] )
Edit Distance example continued
      1 2 3 4 5 6 7 8 9 10 11 12
    - A C G T A C G T A C G T
  - 0 1 2 3 4 5 6 7 8 9 10 11 12
1 A 1 0 1 2 3 4 5 6 7 8 9 10 11
2 C.............
3 T.............
4 A.............
5 C.............
6 C.............
7 T.............
8 A.............
9 C.............
10 A.............
11 G.............
12 T.............
D[ i , j ] = dist( A[ 1 .. i ], B[ 1 .. j ] )
Edit Distance  only the important entries:-
      1 2 3 4 5 6 7 8 9 10 11 12
    - A C G T A C G T A C G T
  - 0............
1 A. 0...........
2 C.. 0 1.........
3 T.... 1........
4 A..... 1.......
5 C...... 1......
6 C....... 2.....
7 T........ 2....
8 A......... 2...
9 C.......... 2..
10 A.......... 3..
11 G........... 3.
12 T............ 3
   A C G T A C G T A C - G T
   | |   | | |   | | |   | |
   A C - T A C C T A C A G T
The general step:

 

  . . .

 

NW: D[i-1, j-1] N: D[i, j-1]

. . .

W: D[i-1, j] D[i, j] = f(NW, N, W)
f(NW, N, W) = min(NW + either 0 or 1, N+1, W+1)
["the" dynamic programming algorithm (DPA) code; class: study this at home!]
D[0][0] = 0; // boundary condition

for(j=1; j <= length of B; j++)
   D[0][j] = D[0][j-1] + 1;   // boundary condition

for(i=1; i <= length of A; i++)
 { D[i][0] = D[i-1][0] + 1;   // boundary condition

   for(j=1; j <= length of B; j++)
    { var diag = D[i-1][j-1];
      if( A[i] != B[j] ) diag++;         //diag = 0 or 1
      
      D[i][j] = min(diag,                //match or change
                    min( D[i-1][j] + 1,  //deletion
                         D[i][j-1] + 1)) //insertion
    }//for j
 }//for i

Properties of Edit Distance Algorithm

Other examples in, e.g. graph algorithms (later).

Dynamic Programming,   Edit Distance:   Summary

Also see:

© L.Allison, Saturday, 30-Mar-2024 02:37:02 AEDT users.monash.edu.au/~lloyd/tilde/CSC2/CSE2304/Notes/07edit.shtml
Computer Science, Software Engineering, Science (Computer Science).