Online Lectures on Bioinformatics

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 ofThe ForwardBackwardMatrix For each residuepair the ForwardBackwardMatrix specifies the score of the best alignment containing this pair: figure: The ForwardBackwardMatrix
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 ForwardBackwardMatrix 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. luz@molgen.mpg.de 