
Inf. Proc. Lett., 51(5), pp.251255, 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(n^{2})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/00200190(94)900043],
or [preprint.ps].

