title: Optimal alignments in linear space.
abstract: Space, not time, is often the limiting factor when computing optimal sequence alignments, and a number of recent papers in the biology literature have proposed space-saving strategies. However, a 1975 computer science paper by Hirschberg presented a method that is superior to the new proposals, both in theory and in practice. The goal of this paper is to give Hirschberg's idea the visibility it deserves by developing a linear-space version of Gotoh's algorithm, which accommodates affine gap penalties. A portable C-software package implementing this algorithm is available on the BIONET free of charge.
authors: Department of Computer Science, University of Arizona, Tucson 85721.
authors: E W
authors: EW
authors: Myers
authors: W
authors: W
authors: Miller
mesh_terms: D000465:Algorithms; D001483:Base Sequence; D005075:Biological Evolution; D012689:Sequence Homology, Nucleic Acid; D012984:Software