Linear-space algorithms that build local alignments from fragments

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 coworkers with a space-saving approach of Hirschberg to obtain a local alignment 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 alignment fragments. Ideas of Huang and Miller are then employed to develop a time- and space-efficient algorithm that computes n best nonintersecting alignments for any n > 1. An example illustrates the utility of these methods.