Sequence alignment using FastLSA

Abstract

Abstract 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 mn to compute. The time actually consists of two parts: computing the score of the best align-ment (calculating (m+1)(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 2m, but doubles the cost of computing and extract-ing 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.