## A Fast Algorithm for the Optimal Alignment of Three Strings

### Lloyd Allison

#### Journal of Theoretical Biology, 164(2), pp.261-269, doi:10.1006/jtbi.1993.1153, September 1993

**Abstract**
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(nd^{2}) and
space-complexity O(d^{3}), 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+d^{3}) 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

Also see [source code].

(Later, also see:

D. R. Powell, L. Allison and T. I. Dix,
'Fast, Optimal Alignment of Three Sequences Using Linear Gap Cost',
Journal of Theoretical Biology, 207(3), pp.325-336,
doi:10.1006/jtbi.2000.2177,
December 2000.)