Abstract
Consider two strings A and B of lengths n and m respectively, with n ≪ m. The problem of computing global and local alignments between A and all m 2 substrings of B can be solved by the classical Needleman-Wunsch and Smith-Waterman algorithms, respectively, which takes O(m 2 n) time and O(m 2 ) space. This paper proposes faster algorithms that take O(mn 2 ) time and O(mn) space. The improvement stems from a compact way to represent all the alignment scores. © Springer-Verlag Berlin Heidelberg 2003.