Hirschberg's Algorithm Pseudocode 2 - 15 August 2011 - BioInformatics Pakistan
Thursday, 2017-03-30, 5:30 PM
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 2
2:39 PM
Hirschberg's Algorithm Pseudocode 2


Hirschberg's Algorithm Pseudocode

1. Pseudocode:

High level description of Hirschberg's algorithm:

  1. Hirschberg(x,y) is 
  2. 1. n = length(x); m = length(y)
    
  3. 2. If n <= 1 or m <= 1:
    
  4.  OUTPUT Alignment(x,y) using Needleman-Wunsch.
    
  5.  Else:
    
  6.  A. mid = floor(n/2)
    
  7.  B. x_left = Prefix[x,mid]
    
  8.  C. x_right = Suffix[x,n-mid]
    
  9.  D. Edit[x_left] = Forwards(x_left,y)
     %% an array of length m+1
    
  10.  E. Edit[x_right] = Backwards(x_right,y)
     %% an array of length m+1
    
  11.  F. cut = ArgMin{Edit[x_left,Prefix[y,j]] +
     Edit[x_right,Suffix[y,m-j]]} %% j ranges from 1 to m-1
    
  12.  G. Hirschberg(x_left,Prefix[y,cut])
    
  13.  H. Hirschberg(x_right,Suffix[y,m-cut])

Page 1


Category: Algorithms | Views: 962 | 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