Friday, 2024-03-29
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 Students Should Join Bio-Informatics
Total of answers: 36
Chat Box
Statistics

Total online: 1
Guests: 1
Users: 0
Home » 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: 2130 | 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 © 2024
Free website builderuCoz