Iterative Verfahren

Die meisten Methoden für multiples Alignment gehen so vor, daß sie iterativ Alignments von Untermengen der k Strings in ein Alignment der Vereinigungsmenge überführen. Eine mögliche Vorgehensweise ist, mit dem besten paarweisen Alignment zu starten und immer die Sequenz zu dem Alignment hinzuzufügen, welche die minimale Distanz zu einem String im Alignment hat. Dies führt zu dem Alignment, welches konsistent   mit dem MST der Sequenzen ist.

Definition 14   Sei S eine Menge von Strings und T ein Baum, dessen Knoten mit verschiedenen Strings aus S beschriftet sind. Ein multiples Alignment A für S wird konsistent mit T genannt, wenn die projezierten paarweisen Alignments A_i,j optimal sind für alle S_i,S_j die in T durch eine Kante verbunden sind (siehe auch Abbildung 25)

  

Abbildung 25: Ein mit T konsistentes Alignment

Es ist immer möglich, effizient ein zu einem Baum konsistentes Alignment zu finden. In den Übungen soll der folgende Satz bewiesen werden.

Satz 10   Sei S eine Menge von Strings und T ein Baum, dessen Knoten mit verschiedenen Strings aus S beschriftet sind. Dann kann man ein multiples Alignment A von S, welches konsistent mit T ist, effizient finden.

Beweis: Übungen.