title: A fast algorithm for the optimal alignment of three strings.
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(nd2) and space-complexity O(d3), where the string lengths are ñ 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.
authors.affiliation: Department of Computer Science, Monash University, Australia.
authors.forename: L
authors.initials: L
authors.lastname: Allison
mesh_terms: D000465:Algorithms; D004247:DNA; D046911:Macromolecular Substances; D011506:Proteins; D016415:Sequence Alignment
chemical_list: D046911:Macromolecular Substances; D011506:Proteins; D004247:DNA