A Fast Algorithm for the Optimal Alignment of Three Strings

✍ Scribed by Lloyd Allison

• Publisher: Elsevier Science
• Year: 1993
• Tongue: English
• Weight: 272 KB
• Volume: 164
• Category: Article
• ISSN: 0022-5193
• DOI: 10.1006/jtbi.1993.1153

✦ Synopsis

LLOYD ALLISON
Department of Computer Science, Monash University, Australia 3168

(Received on 15 December 1992, Accepted in revised form on 10 March 1993)

Ukkonen's (pair-wise) string alignment technique is extended to the problem of finding an optimal alignment for three strings. The resulting algorithm has worstcase time-complexity (O\left(n d^{2}\right)) and space-complexity (O\left(d^{3}\right)), where the string lengths are (\tilde{n}) and (d) is the three-way edit-distance based on tree-costs. In practice, the algorithm usually runs in (O\left(n+d^{3}\right)) time. The algorithm is particularly fast when the strings are similar, in which case, (d \ll 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.