Suche nach dem optimalen Baum

Wie schon in der Einleitung erwähnt, müßte an sich der Maximum-Likelihood-Wert für jeden möglichen Baum berechnet werden. Der Baum mit dem höchsten Log-Likelihood-Wert ist dann derjenige, der die Entstehung des vorgegebenen Sequenzen durch Evolution unter dem benutzten Modell am besten unterstützt. Aufgrund der hohen Anzahl von möglichen Bäumen ist eine erschöpfende Suche nicht praktikabel. Daher wird der heuristische Ansatz des schrittweisen Hinzufügens gewählt.

Bei diesem Ansatz wird, beginnend bei einem Baum mit drei Sequenzen, die Baumtopologie mit dem höchsten ML-Wert bestimmt. In diesen wird dann die nächste Sequenz in alle Kanten eingefügt und aus diesen Bäumen wieder der mit dem höchsten ML-Wert weiterverwendet. Dies wird so lange wiederholt, bis alle Sequenzen in den Baum eingebunden sind.

Um das Risiko zu mindern, daß man durch den heuristischen Ansatz den besten Baum gar nicht erst findet, wurden bei allen in dieser Diplomarbeit verwendeten Analysen, ab einer Baumgröße von vier Sequenzen, lokale Rearrangements über die Länge einer Kante durchgeführt; d.h. jeder Teilbaum des optimalen Baumes wird herausgeschnitten und in alle benachbarten Kanten eingefügt. Findet sich hierbei ein neuer optimaler Baum, so wird ein erneutes lokales Rearrangement ausgeführt, bis kein neues Optimum mehr gefunden wird. Erst dann wird die nächste Sequenz eingefügt.

  Sind alle Sequenzen in den Baum eingefügt, wird, ausgehend vom gefundenen Optimum, ein globales Rearrangement durchgeführt. Dieses verläuft genau wie das lokale Rearrangement, allerdings mit dem Unterschied, daß die ausgeschnittenen Teilbäume in jede andere Kante eingefügt werden. Auf diese Weise wird eine große Anzahl an potentiellen Bäumen getestet, die eventuell durch die reine Heuristik übersehen worden wären.