Information Processing Letters, 70(3) pp127-139, 1999
A versatile divide and conquer technique for
optimal string alignment
D. R. Powell, L. Allison and T. I. Dix,
Department of Computer Science, Monash University,
Clayton, VIC 3168,
Common string alignment algorithms such as the
dynamic programming algorithm (DPA) and the
time efficient Ukkonen algorithm use quadratic space to
determine an alignment between two strings.
In this paper we present a technique that can be applied to these
algorithms to obtain an alignment using only linear space,
while having little or no effect on the time complexity.
This new technique has several advantages over previous methods for
determining alignments in linear space, such as: simplicity,
the ability to use essentially the same technique when
using different cost functions, and the practical advantage of
easily being able to trade available memory for running time.
Keyword: Algorithms, sequence alignment, dynamic programming, edit distance
Copyright 2001, Elsevier Science, All rights reserved.