A versatile divide and conquer technique for optimal string alignment

LA home
Computing
Publications
 IPL99
 software

Also see
Bioinformatics
 Alignment

Information Processing Letters, 70(3) pp.127-139, 1999

D. R. Powell, L. Allison and T. I. Dix,
Department of Computer Science, Monash University, Clayton, VIC 3168, Australia

Abstract

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

Links:
[DOI:10.1016/S0020-0190(99)00053-8][2/'03], [sciencedirect][2/'03].

(The flexible D&C technique can also be applied to the alignment of three sequences, even with linear gap-costs and when combined in a fast greedy algorithm [Powell et al].)

www:


© L. Allison   http://www.allisons.org/ll/   (or as otherwise indicated),
Created with "vi (Linux or Solaris)",  charset=iso-8859-1,  fetched Wednesday, 20-Sep-2017 10:41:26 EDT.

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