A space-efficient algorithm for local similarities

Existing dynamic-programming algorithms for identifying similarregions of two sequences require time and space proportionalto the product of the sequence lengths. Often this space requirementis more limiting than the time requirement. We describe a dynamic-programminglocal-similarity algorithm that needs only space proportionalto the sum of the sequence lengths. The method can also findrepeats within a single long sequence. To illustrate the algorithm'spotential, we discuss comparison of a 73 360 nucleotide sequencecontaining the human ß-like globin gene cluster anda corresponding 44 594 nucleotide sequence for rabbit, a problemwell beyond the capabilities of other dynamic-programming software. Received on January 29, 1990; accepted on May 30, 1990