2000metmbs Kevin Charter, Jonathan Schaeffer, Duane Szafron, Sequence Alignment using FastLSA, Proceedings of The 2000 International Conference on Mathematics and Engineering Techniques in Medicine and Biological Sciences (METMBS'2000), June 2000, Las Vegas, Nevada, pp 239-245. abstract or pdf

For two strings of length m and n ( m <= n ), optimal sequence alignment (as a function of the alignment scoring function) takes time and space proportional to m x n to compute. The time actually consists of two parts: computing the score of the best alignment (calculating (m +1) x ( n +1) values), and then extracting the alignment (by reading the computed values). The space requirement is usually prohibitive. Hirschberg's algorithm reduces the space needs to roughly 2 x m, but doubles the cost of computing and extracting the alignment. This paper introduces the FastLSA algorithm that is adaptive to the amount of space available. At one extreme, it uses linear space, while at the other it uses quadratic space. Based on the memory resources available, the algorithm saves the maximum amount of information to achieve the lowest extraction cost. The algorithm is shown to be analytically and experimentally superior to Hirschberg's algorithm.