
Journal of Theoretical Biology, 164(2), pp.261269, Sept. 1993
L. Allison
School of Computer Science and Software Engineering,
Monash University, Clayton, Australia
Abstract
Ukkonen's (pairwise) string alignment technique is
extended to the problem of finding an optimal alignment for
three strings. The resulting algorithm has worstcase timecomplexity
O(nd^{2}) and spacecomplexity O(d^{3}), where the
string lengths are n and d is the threeway editdistance based on treecosts.
In practice, the algorithm usually runs in O(n+d^{3}) time.
The algorithm is particularly fast when the strings are similar,
in which case, d<<n.
Threeway alignment is an important special case in string alignment.
Each internal node in an unrooted, binary evolutionarytree has
three neighbours. The algorithm presented can be used as
an iterative step in a heuristic multiplealignment program for more
than three strings.
Paper here:
[doi:10.1006/jtbi.1993.1153][4/'03],
[.ps] &
[sourcecode],
[sciencedirect][4/'02].

