Visualizing geophylogenies : external labeling with modifiable phylogenetic tree constraints

Abstract

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.

A geophylogeny is a structure consisting of a map and a phylogenetic tree, where the leaves of the tree are represented as feature points on the map. It is used in the field of phylogenetics to depict an evolutionary relationship between different taxa and to locate these taxa on a map. Visualizing a geophylogeny in an appealing way is not an easy task. It can be a challenge to do this by hand, especially when there is a large number of taxa to depict. One typical visualization form is external labeling, where the taxa represented in the tree's leaves are connected with the feature points on the map via leader lines. A drawing of a geophylogeny can become convoluted very quickly, especially when leaders cross. In this thesis, we aim to develop solutions that automate the visualization of geophylogenies with external labeling. Additionally, we intend to provide solutions to produce drawings with high visualization quality, characterized by minimal leader crossings. At the cost of losing some phylogenetic information, we introduce methods to modify the phylogenetic tree in a way that further improves the solution quality. We present mixed integer linear programming models to provide exact solutions for these problems, as well as heuristic approaches that are faster but do not always yield optimal solutions. Finally, we evaluate and discuss our results, providing new insights that can serve as stepping stones for future research.