Iterative versus simultaneous multiple sequence alignment

Dress A. Iterative versus simultaneous multiple sequence alignment. In: Apostolico A, Hein J, eds. Combinatorial Pattern Matching. 8th Annual Symposium, CPM 97 Aarhus, Denmark, June 30–July 2, 1997 Proceedings. Lecture Notes in Computer Science. Vol 1264. Berlin: Springer; 1997: 275-275.Due to unsurmountable time requirements, straight-forward dynamical-programming approaches to multiple sequence alignment were abandoned a long time ago in favour of iterative procedures. Some of those have been elaborated to great perfection, using many years of experience regarding the optimal adjustment of biologically relevant aligment parameters. The situation changed somewhat with the availability of “MSA”-a program which is based on some clever “branch bound” procedures to reduce, by several orders of magnitude, the enormous search space one has to cope with. This way, MSA is able to compute optimal multiple sequence aligments with regard to appropriately defined “sum of pairs scores” for, say, up to six protein sequences of modest length (up to, say, 300 amino acids) and sufficiently high sequence homology. Still, many biologically important sequence families turned out to be by far too complex to be aligned simultaneously by MSA. Here, the new DIVIDE &: CONQUER multiple sequence alignment algorithm “DCA” can now be invoked to find (almost) optimal simultaneous alignments in situations where formerly the construction of such alignments was out of question. In the lecture, the workings of DCA will be explained shortly, some applications to biologically relevant data sets will be discussed and the potential of this new approach regarding some basic problems in sequence alignment will be evaluated. © Springer-Verlag Berlin Heidelberg 199