A space-efficient algorithm for aligning large genomic sequences

In the segment-by-segment approach to sequence alignment, pairwise and mult iple alignments are generated by comparing gap-free segments of the sequenc es under study This method is particularly efficient in detecting local hom ologies, and it has been used to identify functional regions irt large geno mic sequences. Herein, an algorithm is outlined that calculates optimal pai rwise segment-by-segment alignments in essentially linear space.