Hirschberg's Algorithm Pseudocode - 15 August 2011 - BioInformatics Pakistan
Tuesday, 2017-02-21, 1:36 AM
Welcome Guest | RSS

Login form

Statistics
Total online: 1
Guests: 1
Users: 0

Is Online User
Site Search
Main » 2011 » August » 15 » Hirschberg's Algorithm Pseudocode
1:20 PM
Hirschberg's Algorithm Pseudocode


Hirschberg's Algorithm Pseudocode

1. Pseudocode:
   High-level description of the forwards subprogram

  1. Forwards[x,y] is
    
  2.  
    
  3. 1. n = length(x); m = length(y)
    
  4. 2. Edit[Prefix[0,0]] = 0;
    
  5. 3. For all i from 1 to n:
    
  6.  Edit[Prefix[x,i],Prefix[y,0]] = Edit[Prefix[x,i-1],Prefix[y,0]]
     + Del(x_i)
    
  7. 4. For all j from 1 to m:
    
  8.  A. Edit[Prefix[x,0],Prefix[y,j]] = Edit[Prefix[x,0],Prefix[y,j-1]]
     + Ins(y_j)
    
  9.  B. For all i from 1 to n, execute the following steps:
    
  10.  i. Edit[Prefix[x,i],Prefix[y,j]] =
    
  11.  min{Edit[Prefix[x,i-1],Prefix[y,j]] + Del(x_i),
    
  12.  Edit[Prefix[x,i-1],Prefix[y,j-1]] + Sub(x_i,y_j),
    
  13.  Edit[Prefix[x,i],Prefix[y,j-1]] + Ins(y_j)}
    
  14.  ii. Erase Edit[Prefix[x,i-1],Prefix[y,j-1]]
    
  15.  C. Erase Edit[Prefix[x,i-1],Prefix[y,j]]
    
  16. 5. RETURN Edit[x] %% an array of length m+1

   High-level description of the backwards subprogram

  1. Backwards[x,y] is
    
  2.  
    
  3. 1. n = length(x); m = length(y)
    
  4. 2. For all i from 1 to n:
    
  5.  Edit[Suffix[x,i],Suffix[y,0]] = 0
    
  6. 3. For all j from 1 to m:
    
  7.  A. Edit[Suffix[x,0],Suffix[y,j]] = Edit[Suffix[x,n],Suffix[y,j-1]] +
     Ins(y_{m-j+1})
    
  8.  B. For all i from 1 to n:
    
  9.  i. Edit[Suffix[x,i],Suffix[y,j]] =
    
  10.  min{Edit[Suffix[x,i-1],Suffix[y,j]] + Del(x_{n-i-1}),
    
  11.  Edit[Suffix[x,i-1],Suffix[y,j-1]] +
     Sub(x_{n-i-1},y_{m-j+1}),
    
  12.  Edit[Suffix[x,i],Suffix[y,j-1]] + Ins(y_{m-j+1})}
    
  13.  ii. Erase Edit[Suffix[x,i-1],Suffix[y,j-1]]
    
  14.  C. Erase Edit[Suffix[x,i-1],Suffix[y,j]]
    
  15. 4. RETURN Edit[x] %% an array of length m+1

Page 2   

Category: Algorithms | Views: 803 | Added by: Ansari | Rating: 0.0/0
Total comments: 0
Name *:
Email *:
Code *:
Tag Board
Your Ads
Site friends

Copyright MyCorp © 2017
Free website builderuCoz