Dynamic Programming:   Introduction to Edit Distance

• ``appropriate meaning'' is like ``approximate matching''.   How alike?
  
  
• appropriate  meaning
• approxriate  meaning,     p->x
• approxiiate  meaning,     r->i
• approximate  meaning,     i->m
• approximate  maeaning,     insert a
• approximate  mataning,     e->t
• approximate  matcning,     a->c
• approximate  matching,     n->h
  
  
• 7 changes, edit distance = 7.   Can you do better?

Allowable mutations:

1. Change a letter
   • fred -> feed
     
     
2. Insert a letter
   • fred -> freed
     
     
3. Delete a letter
   • fred -> red
     
     

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

• Edit distance   is also known as Approximate Matching
  
  
• related to Longest Common Sub-Sequence (LCSS) problem.

Is useful in:

• spelling correction
  
  
• DNA sequence searching
  
  
• pattern discovery in time-series
  
  
• file comparison - See Unix command ``diff'' [class: Try ``man diff'']
  
  
• computer screen update problem
  
  

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

• Boundary Conditions
  
  
  • D[0, 0] = 0
    
    
  • D[i, 0] = i,   for all i = 1 .. |A|
    
    
  • D[0, j] = j,   for all j = 1 .. |B|
    
    
• General step,  for all i = 1 .. |A| and j = 1 .. |B|
  
  
  • D[i , j] = min(
    
    

    D[i-1, j-1] + if A[i] = B[j] then 0 else 1 end_if,
    
    

    D[i-1, j] + 1,
    
    

    D[i, j-1] + 1 )
    

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

• Time
  
  
  • O( |A| * |B| ) - time
    
    
• Space
  
  
  • O( |A| * |B| ) - space
    if keep all of D[ , ],   (can find path)
    
    
  • O( |A| ) - space
    if only use two rows   (calculate value of edit distance only)

• Edit Distance is an example of the Dynamic Programming Paradigm, a general problem solving strategy:
  
  
• Some property is true for partial solution
  
  
  • e.g. D[ i, j ] = dist( A[1..i], B[1..j])
    
    
• Increase size (i and j increase) while
  
  
  1. making property true for thelarger size (i and/or j) and
     
     
  2. not invalidating work already done.

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

Dynamic Programming,   Edit Distance:   Summary

• Don't repeat work
  
  
  • e.g. store results in D[ , ] matrix for re-use
    
    
• Don't invalidate work already done
  
  

Also see:

• Hirschberg's algorithm (next)
  
  
• Exact String searching / matching.