previous section previous page next page next section
CMB

Online Lectures on Bioinformatics

navigation


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 of

The 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