Journal of Theoretical Biology 164(2) pp261269 Sept' 1993
A Fast Algorithm for the Optimal Alignment of Three Strings
L. Allison
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.
Copyright 1993, 1999 Academic Press

Paper here: [.ps] &
[code],
[doi:10.1006/jtbi.1993.1153][4/'03],
[sciencedirect][4/'02].
Was:
[idealibrary]['02],
[pdf]['02].
