A Fast Algorithm for the Optimal Alignment of Three Strings

LA home

Also see


Journal of Theoretical Biology, 164(2), pp.261-269, Sept. 1993

L. Allison

School of Computer Science and Software Engineering, Monash University, Clayton, Australia


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.

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


© L. Allison   http://www.allisons.org/ll/   (or as otherwise indicated),
Created with "vi (Linux or Solaris)",  charset=iso-8859-1,  fetched Sunday, 20-May-2018 15:41:18 EDT.

free: Linux, Ubuntu operating-sys, OpenOffice office-suite, The GIMP ~photoshop,
Firefox web-browser, FlashBlock flash on/off.