B. Morgenstern, A simple and space-efficient fragment-chaining algorithm for alignment of DNA and protein sequences, APPL MATH L, 15(1), 2002, pp. 11-16
In the segment-based approach to sequence alignment, nucleic acid, and prot
ein sequence alignments are constructed from fragments, i.e., from pairs of
ungapped segments of the input sequences. Given a set F of candidate fragm
ents and a weighting function w : F --> R-0(+), the score of an alignment i
s defined as the sum of weights of the fragments it consists of, and the op
timization problem is to find a consistent collection of pairwise disjoint
fragments with maximum sum of weights. Herein, a sparse dynamic programming
algorithm is described that solves the pairwise segment-alignment problem
in O(L + N-max) space where L is the maximum length of the input sequences
while N-max less than or equal to #F holds. With a recently introduced weig
hting function w, small sets F of candidate fragments are sufficient to obt
ain alignments of high quality, As a result, the proposed algorithm runs in
essentially linear space. (C) 2001 Elsevier Science Ltd. All rights reserv
ed.