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