Divide-and-Conquer Verfahren

Dieser klassische Ansatz wurde erst vor kurzem erfolgreich implementiert. Die Idee liegt darin, die k Sequenzen ``durchzuschneiden'', die beiden entstehenden Teilprobleme rekursiv zu lösen und die Lösungen wieder trivial zusammenzusetzen. Ab einer gewissen Problemgröße werden die Probleme optimal gelöst. Man kann sich überlegen, daß es optimale Positionen zum Zerschneiden gibt, und wie man die Positionen möglichst gut wählt (siehe auch Abbildung 27). Triviale Ansätze zum Zerschneiden der Sequenzen scheitern bei diesem Ansatz meist direkt.

  

Abbildung 27: Schematische Darstellung von Divide-and-Conquer Alignment