Online Lectures on Bioinformatics
Variants of the dynamic programming algorithm
Linear in Space Algorithm
The task of computing an optimal alignment using linear space is solved by means of the concept ofThe Forward-Backward-Matrix
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.
Backtracking and outputting the alignment is managed by
recursively computing the Forward-Backward-Matrix, which can
be done in linear space.
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.
luz@molgen.mpg.de