Monday, 2018-02-19
BioInfo Pakistan
Site menu
Section categories
Related Subjects [38]
This category includes brief overview of all related subjects.
Defining BioInformatics [7]
In this section we tried to briefly explain what bioinformatics is ?
Unviersities [30]
This contains information about universities that are offering bioinformatics degree programs.
Resources [24]
Contains information about bioinformatics resources including databases, tools and techniques.
Algorithms [31]
This category includes some of the basic algorithms that are usually used by bioinformaticians.
Our poll
Pakistani Student
Total of answers: 0
Chat Box
Statistics

Total online: 1
Guests: 1
Users: 0
Home » 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: 987 | Added by: Ansari | Rating: 0.0/0
Total comments: 0
Name *:
Email *:
Code *:
Log In

Search
Calendar
«  August 2011  »
SuMoTuWeThFrSa
 123456
78910111213
14151617181920
21222324252627
28293031
Entries archive
Site friends
Copyright MyCorp © 2018
Free website builderuCoz