[Subject home], [FAQ], [progress],   Bib', Alg's,  C , Java - L.A., Friday, 29-Mar-2024 16:50:19 AEDT
Instructions: Topics discussed in these lecture notes are examinable unless otherwise indicated. You need to follow instructions, take more notes & draw diagrams especially as [indicated] or as done in lectures, work through examples, and do extra reading. Hyper-links not in [square brackets] are mainly for revision, for further reading, and for lecturers of the subject.

Hirschberg:   Introduction

Basic Idea for aligning 2 strings, s1[ ] and s2[ ]

example . . .
  - A C G T A C G T A C G Tfwd
- 0 1 2 ...         
A 1 0           
C 2  0 1         
T ...    1        
A      1       
C       1      
C      ...2...    
  <cut<
rev      ...1...     T
         1     A
          1    C
           1  ... A
           0  2 G
            0 1 T
          ... 2 1 0 -
A C G T A C G T A C G T - 
NB. Have only shown "important" values - L.Allison 2000.

General Case,   | s1 | > 1

Base Case


[lecturer: briefly; class: study at home!]
function Hirschberg(int p1, int p2,  int q1, int q2)
/* align s1[p1..p2) with s2[q1..q2). Strings are global! */
 { int mid, i,  s2mid, sum best;

   if( p2 <= p1 )
      a base case ... s1 is empty, match '' : s2

   else if( q2 <= q1 )
      a base case ... s2 is empty, match s1 : ''

   else if( p2-1 == p1 ) /* s1 is 1 character & s2 is not empty */
      a base case ... find best match for s1[p1] in s2[]

   else /* p2>p1+1, s1 has at least 2 chars, divide s1 & conquer */
    { mid = (p1+p2) / 2;
      fwdDPA(p1, mid, q1, q2, fwd);  /* fwd[] is one row */
      revDPA(mid, p2, q1, q2, rev);  /* rev[] is one row */
      s2mid = q1;
      best = huge_number;
      for( i=q1; i<=q2; i++ ) /* seek cheapest split of s2 */
       { sum = fwd[mid % 2][i] + rev[mid % 2][i];
         if( sum < best ) { best=sum; s2mid=i; }
       }
      Hirschberg(p1,mid, q1,s2mid); /* divide & */
      Hirschberg(mid,p2, s2mid,q2); /* conquer! */
    }
 }/*align*/

Space Complexity

Time Complexity

is O( n2 × ( 1 + 1/2 + 1/4 + . . . )), is O( n2 )   because [______________]
  s2a s2b


s1a

 
s1a : s2a
 
 


s1b

   
s1b : s2b
 
NB. | s1a | = | s1b | +/- 1
continued...
. . . next level in recursion   (1/4 area) . . .
  s2aa s2ab s2ba s2bb
s1aa  
s1aa : s2aa
 
   
s1ab    
s1ab : s2ab
 
s1ba    
s1ba : s2ba
 
 
s1bb    
s1bb : s2bb
 
--L.Allison,2000.

Hirschberg: Summary


Prepare

© L.Allison, Friday, 29-Mar-2024 16:50:19 AEDT users.monash.edu.au/~lloyd/tilde/CSC2/CSE2304/Notes/08hirsch.shtml
Computer Science, Software Engineering, Science (Computer Science).