Using Hirschberg's Algorithm to Generate Random Alignments of Strings

LA home
Computing
Publications
 IPL

also see
JME

Bioinformatics
 alignment
 multiple
 trees

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

www:


© L. Allison   http://www.allisons.org/ll/   (or as otherwise indicated),
Created with "vi (Linux or Solaris)",  charset=iso-8859-1,  fetched Friday, 24-Nov-2017 04:31:42 EST.

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