Online Lectures on Bioinformatics

Algorithms for SPoptimal multiple alignmentsSaving spaceComputing an optimal alignment between two sequences can be done in linear instead of quadratic space by means of the forwardbackwardmatrix (see previous section). Computing an SPoptimal multiple alignment by recursively applying the concept of the forwardbackwardmatrix to one dimension of the ndimensional editgraph leads to time complexity and needs space in .Comments are very welcome. luz@molgen.mpg.de 