This paper presents practical algorithms for building an alignment of
two long sequences from a collection of ''alignment fragments,'' such
as all occurrences of identical 5-tuples in each of two DNA sequences.
We first combine a time-efficient algorithm developed by Galil and co
workers with a space-saving approach of Hirschberg to obtain a local a
lignment algorithm that uses O((M + N + F log N) log M) time and O(M N) space to align sequences of lengths M and N from a pool of F align
ment fragments. Ideas of Huang and Miller are then employed to develop
a time- and space-efficient algorithm that computes n best noninterse
cting alignments for any n > 1. An example illustrates the utility of
these methods.