Variants of the dynamic programming algorithm
Linear in Space AlgorithmThe task of computing an optimal alignment using linear space is solved by means of the concept of
For each residue-pair the Forward-Backward-Matrix specifies the score of the best alignment containing this pair:
figure: The Forward-Backward-Matrix
The computation of the entries of the edit matrix can easily be
done in linear space, as each row of the matrix depends only on
the preceding one.
The Forward-Backward-Matrix may also be used to receive an overview of robust and less robust parts of a global alignment and of alternative solutions (see next section: Suboptimal Alignments).
This document was created by means of the LaTeX2HTML translator Version 98.1p1 release (March 2nd, 1998).
Comments are very welcome.