README

Copyright (c) David Powell <david@drp.id.au>

  This package is provided under he GNU Public License v2 and
  comes with ABSOLUTELY NO WARRANTY, or details see file COPYRIGHT



This package contains 4 programs for aligning sequences
under linear gap costs.  Thats is where gaps of length
k have a cost = a + b * k.  The two dpa_ programs can
have the costs set from the commandline.  While the two ukk_
programs must have the costs set at compile time.  Note that
ukk_ programs must have integer costs, and a match must cost
0.


dpa_linear:
  Calculates the edit cost, and displays an optimal
  alignment between two sequences.  Uses the standard DPA.
  Has time and space complexity of O(n*n).


dpa_lcheckp:
  Calculates the edit cost, and displays an optimal
  alignment between two sequences.  Uses the
  check-pointing(1) to recover the alignment. Has time
  complexity O(n*n), and space complexity O(n).


ukk_linear:
  Calculates the edit cost between two strings, _but_
  does not recover an alignment.  This program uses a
  modification of Ukkonen's algorithm(2).  Has average time
  complexity of O(d*d + n), and space complexity O(d)
  (where d is the edit distance)

  
ukk_lcheckp:
  Calculates the edit cost between two strings, and
  displays an optimal alignment.  This program uses a
  modification of Ukkonen's algorithm(2) with
  check-pointing(1) to recover the alignment.  The average
  time complexity is O(n*log(d) + d*d), and space complexity
  is O(d) (where d is the edit distance)



1:  D. R. Powell, L. Allison and T. I. Dix,
    "A Versatile Divide and Conquer Technique for Optimal String Alignment",
    Information Processing Letters, 1999, 70:3, pp 127-139

2:  E. Ukkonen, "On Approximate String Matching",
    Foundations of Computation Theory, 1983, 158, pp 487-495


-- David Powell <david@drp.id.au>