Online Lectures on Bioinformatics

Algorithms for SPoptimal multiple alignmentsDivideandConquer AlignmentThe DivideandConquer Alignment [Tö96] [St98] is a a fast heuristic algorithm for multiple sequence alignment which provides neartooptimal results for sufficiently homologous sequences.
The main idea is first to cut the sequences several times
at certain points to reduce the length of the sequences,
second to align the cutted sequences and third to concatenate
the multiple alignments:
The problem is to find the cut positions:
The method needs time in
and space in
.
While time still grows exponentially in the number of sequences,
the space is reduced to quadratic.
There also exist heuristics which relax from the requirement that
is truly minimized which lead to an
time and space algorithm.
exercises Comments are very welcome. luz@molgen.mpg.de 