Using Hirschberg's Algorithm to Generate Random Alignments of Strings
L. Allison, Information Processing Letters, 51(5), pp.251-255, doi:10.1016/0020-0190(94)90004-3, Sept. 1994
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.