Implementation and Comparison of Algorithms for Constructing and Visualizing Phylogenetic Trees

TEX ist ein Textsatzsystem, das häufig für die Erstellung wissenschaftli-
cher Dokumente eingesetzt wird. Das TEX-Paket TikZ ermöglicht zusätz-
lich die Erzeugung von qualitativ hochwertigen Vektorgraphiken direkt in
einem TEX-Dokument. Das Ziel dieser Arbeit war es, die TikZ-Graph-Draw-
ing-Bibliothek so zu erweitern, dass die Berechnung und Visualisierung phy-
logenetischer Bäume ebenfalls möglich wird.
Phylogenetische Bäume sind Diagramme, die die Phylogenie einer Men-
ge an Taxa in einer baumartigen Struktur darstellt. Die Stammesgeschichte
kann z.B. durch die sogenannten distance-based methods (engl. distanzbasierte
Methoden) berechnet werden, wobei die Phylogenie anhand einer Distanz-
matrix abgeschätzt wird. Es gibt verschiedene distanzbasierte Ansätze, von
denen zwei in dieser Arbeit näher betrachtet werden: der UPGMA- und der
BME-Algorithmus. Während UPGMA eher einfach und dadurch auch leicht
zu implementieren ist, ist BME deutlich überlegen, wenn es um akkurate
Topologie, Zeitkomplexität und Einsetzbarkeit geht. Da die beiden Algo-
rithmen nicht nur die Topologie des Baumes, sondern auch dessen Kan-
tenlängen bestimmen, ist auch ein Algorithmus erforderlich, der mit dem
Zeichnen von Graphen mit festen Kantenlängen umgehen kann. Sowohl die
Algorithmen für die Berechnung phylogenetischer Bäume als auch die für
deren Zeichnung wurden in der Programmiersprache Lua implementiert, da
es LuaTEX ermöglicht, Lua-Code direkt in TEX einzubetten. Die Algorithmen
und ihre Implementierungen werden diskutiert und verglichen, wobei das
implementierte Modul für die Berechnung und Visualisierung einiger bei-
spielhafter phylogenetischer Bäume direkt in diesem Dokument angewandt
wird.