Journal of Theoretical Biology 164(2) pp261-269 Sept' 1993
A Fast Algorithm for the Optimal Alignment of Three Strings
Ukkonen's (pair-wise) string alignment technique is
extended to the problem of finding an optimal alignment for
three strings. The resulting algorithm has worst-case time-complexity
O(nd2) and space-complexity O(d3), where the
string lengths are n and d is the three-way edit-distance based on tree-costs.
In practice, the algorithm usually runs in O(n+d3) time.
The algorithm is particularly fast when the strings are similar,
in which case, d<<n.
Three-way alignment is an important special case in string alignment.
Each internal node in an unrooted, binary evolutionary-tree has
three neighbours. The algorithm presented can be used as
an iterative step in a heuristic multiple-alignment program for more
than three strings.
Copyright 1993, 1999 Academic Press
Paper here: [.ps] &