Visualizing Geophylogenies - External Labeling with Modifiable Phylogenetic Tree Constraints

Eine Geophylogenie setzt sich aus einer Karte und einem phylogenetischen Baum zusammen, wo die Blätter des Baumes als Merkmalspunkte auf der Karte repräsentiert sind. Sie wird in der Phylogenetik eingesetzt, um evolutionäre Beziehungen zwischen verschiedenen Taxa herzustellen und diese auf einer Landkarte lokalisieren zu können. Das Visualisieren einer Geophylogenie in einer ansprechenden Weise ist keine einfache Aufgabe. Dies per Hand zu machen kann eine Herausforderung sein, besonders wenn eine große Menge an Taxa dargestellt werden soll. Eine übliche Visualisierungsart ist die Form der sogenannten externen Beschriftung, wo die Taxa, welche als die Blätter des Baumes repräsentiert werden, mit den Merkmalspunkten auf der Karte mit Führungslinien verbunden werden. Eine Zeichnung einer Geophylogenie kann sehr schnell unübersichtlich werden, speziell, wenn sich Führungslinien kreuzen. Das Ziel dieser Diplomarbeit ist es Lösungen bereitzustellen die das Visualisieren von Geophylogenien mittels externen Beschriftungen automatisiert ermöglichen sollen. Zusätzlich ist es unser Ziel Zeichnungen mit einer hohen Visualisierungsqualität bereitzustellen, definiert durch minimale Führungslinienkreuzungen. Wir stellen Methoden vor, welche den phylogenetischen Baum modifizieren, wodurch zwar phylogenetische Information verloren geht, jedoch die Lösungsqualität noch weiter verbessert wird. Wir präsentieren gemischt ganzzahlige lineare Optimierungsmodelle, um exakte Lösungen für diese Probleme bereitzustellen, sowie auch heuristische Ansätze, welche schneller sind aber nicht immer zu optimalen Lösungen führen. Abschließend evaluieren und diskutieren wir unsere Ergebnisse und stellen neue Erkenntnisse bereit, die als Ausgangspunkt für neue Forschung herangezogen werden können.