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 [].

www #ad:

↑ © L. Allison,   (or as otherwise indicated).
Created with "vi (Linux)",  charset=iso-8859-1,   fetched Tuesday, 21-Sep-2021 22:37:14 EDT.

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