A time-efficient, linear-space local similarity algorithm

Dynamic programming algorithms to determine similar regions of two sequences are useful for analyzing biosequence data. This paper presents a time-efficient algorithm that produces k best non-intersecting local alignments for any chosen k. The algorithm\u27s main strength is that it needs only O(M + N + K) space, where M and N are the lengths of the given sequences and K is the total length of the computed alignments. © 1991