Using Hirschberg's Algorithm to Generate Random Alignments of Strings

LA home

also see


Inf. Proc. Lett., 51(5), pp.251-255, Sept. 1994,

L. Allison, Dept. Computer Science, Monash University, Australia 3168

Abstract: Hirschberg gave an alignment algorithm for the longest common subsequence problem that uses O(n2)-time and O(n)-space for two strings of length ~n. A simple modification of the algorithm can sample string alignments at random according to their probability distribution. This is useful for statistical estimation of evolutionary distances of a family of strings, e.g., DNA strings. The algorithm's time and space complexity are unchanged.

[doi:10.1016/0020-0190(94)90004-3], or [].


© L. Allison   (or as otherwise indicated),
Created with "vi (Linux or Solaris)",  charset=iso-8859-1,  fetched Wednesday, 20-Sep-2017 10:42:32 EDT.

free: Linux, Ubuntu operating-sys, OpenOffice office-suite, The GIMP ~photoshop,
Firefox web-browser, FlashBlock flash on/off.