Optimal alignments in linear space

Space, not time, is often the limiting factor when computingoptimal sequence alignments, and a number of recent papers inthe biology literature have proposed space-saving strategies.However, a 1975 computer science paper by Hirschberg presenteda method that is superior to the new proposals, both in theoryand in practice. The goal of this paper is to give Hirschberg'sidea the visibility it deserves by developing a linear-spaceversion of Gotoh's algorithm, which accommodates affine gappenalties. A portable C-software package implementing this algorithmis available on the BIONET free of charge. Received on October 14, 1987; accepted on December 19, 1987