Optimal alignments in linear space
Eugene Wimberly Myers, Webb Miller · Computer applications in the biosciences · 1988
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.
Cited by 1,235 works. doi:10.1093/bioinformatics/4.1.11
Authors
References
- The String-to-String Correction Problem
- Some biological sequence metrics
- An improved algorithm for matching biological sequences
- Comparative biosequence metrics
- AnO(ND) difference algorithm and its variations
- Algorithms for approximate string matching
- A faster algorithm computing string edit distances
- Sequence comparison with concave weighting functions
- A file comparison program
- A fast homology program for aligning biological sequences