previous section previous page next page next section

Online Lectures on Bioinformatics


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.