Online Lectures on Bioinformatics

navigation

Algorithms for SP-optimal multiple alignments

Saving space

Computing an optimal alignment between two sequences can be done in linear instead of quadratic space by means of the forward-backward-matrix (see previous section). Computing an SP-optimal multiple alignment by recursively applying the concept of the forward-backward-matrix to one dimension of the n-dimensional edit-graph leads to time complexity $\mathcal{O}(L^n2^n)$ and needs space in $\mathcal{O}(L^{n-1})$ .

Comments are very welcome.
luz@molgen.mpg.de