Document Open Access Logo

Visualizing Geophylogenies - Internal and External Labeling with Phylogenetic Tree Constraints

Authors Jonathan Klawitter , Felix Klesen , Joris Y. Scholl, Thomas C. van Dijk , Alexander Zaft

PDF
Thumbnail PDF

File

LIPIcs.GIScience.2023.5.pdf
  • Filesize: 3.2 MB
  • 16 pages

Document Identifiers

Author Details

Jonathan Klawitter
  • University of Auckland, New Zealand
Felix Klesen
  • Universität Würzburg, Germany
Joris Y. Scholl
  • Ruhr-Universität Bochum, Germany
Thomas C. van Dijk
  • Ruhr-Universität Bochum, Germany
Alexander Zaft
  • Universität Würzburg, Germany

Funding

  • Klawitter, Jonathan: Beyond Prediction Data Science Research Programme (MBIE grant UOAX1932).
  • van Dijk, Thomas C.: DFG grant Di2161/2-1.

Cite As Get BibTex

Jonathan Klawitter, Felix Klesen, Joris Y. Scholl, Thomas C. van Dijk, and Alexander Zaft. Visualizing Geophylogenies - Internal and External Labeling with Phylogenetic Tree Constraints. In 12th International Conference on Geographic Information Science (GIScience 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 277, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.GIScience.2023.5

Abstract

A geophylogeny is a phylogenetic tree where each leaf (biological taxon) has an associated geographic location (site). To clearly visualize a geophylogeny, the tree is typically represented as a crossing-free drawing next to a map. The correspondence between the taxa and the sites is either shown with matching labels on the map (internal labeling) or with leaders that connect each site to the corresponding leaf of the tree (external labeling). In both cases, a good order of the leaves is paramount for understanding the association between sites and taxa. We define several quality measures for internal labeling and give an efficient algorithm for optimizing them. In contrast, minimizing the number of leader crossings in an external labeling is NP-hard. We show nonetheless that optimal solutions can be found in a matter of seconds on realistic instances using integer linear programming. Finally, we provide several efficient heuristic algorithms and experimentally show them to be near optimal on real-world and synthetic instances.

Subject Classification

ACM Subject Classification
  • Human-centered computing → Geographic visualization
  • Applied computing → Biological networks
  • Theory of computation → Discrete optimization
Keywords
  • geophylogeny
  • boundary labeling
  • external labeling
  • algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

Supplementary Materials

References

  1. Lukas Barth, Andreas Gemsa, Benjamin Niedermann, and Martin Nöllenburg. On the readability of leaders in boundary labeling. Information Visualization, 18(1), 2019. URL: https://doi.org/10.1177/1473871618799500.
  2. Michael A. Bekos, Sabine Cornelsen, Martin Fink, Seok-Hee Hong, Michael Kaufmann, Martin Nöllenburg, Ignaz Rutter, and Antonios Symvonis. Many-to-one boundary labeling with backbones. Journal of Graph Algorithms and Applications, 19(3):779-816, 2015. URL: https://doi.org/10.7155/jgaa.00379.
  3. Michael A. Bekos, Michael Kaufmann, Dimitrios Papadopoulos, and Antonios Symvonis. Combining traditional map labeling with boundary labeling. In Ivana Cerná, Tibor Gyimóthy, Juraj Hromkovic, Keith G. Jeffery, Rastislav Královic, Marko Vukolic, and Stefan Wolf, editors, SOFSEM 2011, volume 6543 of LNCS, pages 111-122. Springer, 2011. URL: https://doi.org/10.1007/978-3-642-18381-2_9.
  4. Michael A. Bekos, Michael Kaufmann, Katerina Potika, and Antonios Symvonis. Area-feature boundary labeling. The Computer Journal, 53(6):827-841, 2010. URL: https://doi.org/10.1093/comjnl/bxp087.
  5. Michael A. Bekos, Benjamin Niedermann, and Martin Nöllenburg. External labeling techniques: A taxonomy and survey. Computer Graphics Forum, 38(3):833-860, 2019. URL: https://doi.org/10.1111/cgf.13729.
  6. R Alexander Bentley, William R Moritz, Damian J Ruck, and Michael J O’Brien. Evolution of initiation rites during the austronesian dispersal. Science Progress, 104(3):00368504211031364, 2021. URL: https://doi.org/10.1177/00368504211031364.
  7. Tyler K Chafin, Marlis R Douglas, Whitney JB Anthonysamy, Brian K Sullivan, James M Walker, James E Cordes, and Michael E Douglas. Taxonomic hypotheses and the biogeography of speciation in the tiger whiptail complex. Frontiers, 13(2), 2021. URL: https://doi.org/10.21425/F5FBG49120.
  8. Zachary Charlop-Powers and Sean F. Brady. phylogeo: an R package for geographic analysis and visualization of microbiome data. Bioinformatics, 31(17):2909-2911, 2015. URL: https://doi.org/10.1093/bioinformatics/btv269.
  9. Yi Chen, Lei Zhao, Huajing Teng, Chengmin Shi, Quansheng Liu, Jianxu Zhang, and Yaohua Zhang. Population genomics reveal rapid genetic differentiation in a recently invasive population of rattus norvegicus. Frontiers in Zoology, 18(1):6, 2021. URL: https://doi.org/10.1186/s12983-021-00387-z.
  10. Gajaba Ellepola, Jayampathi Herath, Kelum Manamendra-Arachchi, Nayana Wijayathilaka, Gayani Senevirathne, Rohan Pethiyagoda, and Madhava Meegaskumbura. Molecular species delimitation of shrub frogs of the genus pseudophilautus (anura, rhacophoridae). PLOS ONE, 16(10):1-17, 2021. URL: https://doi.org/10.1371/journal.pone.0258594.
  11. Henning Fernau, Michael Kaufmann, and Mathias Poths. Comparing trees via crossing minimization. Journal of Computer and System Sciences, 76(7):593-608, 2010. URL: https://doi.org/10.1016/j.jcss.2009.10.014.
  12. Philip-Sebastian Gehring, Maciej Pabijan, Jasmin E. Randrianirina, Frank Glaw, and Miguel Vences. The influence of riverine barriers on phylogeographic patterns of malagasy reed frogs (heterixalus). Molecular Phylogenetics and Evolution, 64(3):618-632, 2012. URL: https://doi.org/10.1016/j.ympev.2012.05.018.
  13. Robin-Tobias Jauss, Nadiné Solf, Sree Rohit Raj Kolora, Stefan Schaffer, Ronny Wolf, Klaus Henle, Uwe Fritz, and Martin Schlegel. Mitogenome evolution in the lacerta viridis complex (lacertidae, squamata) reveals phylogeny of diverging clades. Systematics and Biodiversity, 19(7):682-692, 2021. URL: https://doi.org/10.1080/14772000.2021.1912205.
  14. Monika Karmin, Rodrigo Flores, Lauri Saag, Georgi Hudjashov, Nicolas Brucato, Chelzie Crenna-Darusallam, Maximilian Larena, Phillip L Endicott, Mattias Jakobsson, J Stephen Lansing, Herawati Sudoyo, Matthew Leavesley, Mait Metspalu, François-Xavier Ricaut, and Murray P Cox. Episodes of Diversification and Isolation in Island Southeast Asian and Near Oceanian Male Lineages. Molecular Biology and Evolution, 39(3), 2022. URL: https://doi.org/10.1093/molbev/msac045.
  15. David M. Kidd and Xianhua Liu. geophylobuilder 1.0: an arcgis extension for creating "geophylogenies". Molecular Ecology Resources, 8(1):88-91, 2008. URL: https://doi.org/10.1111/j.1471-8286.2007.01925.x.
  16. Jonathan Klawitter, Felix Klesen, Joris Y. Scholl, Thomas C. van Dijk, and Alexander Zaft. Visualizing geophylogenies - internal and external labeling with phylogenetic tree constraints. CoRR, abs/2306.17348, 2023. URL: https://arxiv.org/abs/2306.17348.
  17. Chun-Cheng Lin, Hao-Jen Kao, and Hsu-Chun Yen. Many-to-one boundary labeling. Journal of Graph Algorithms and Applications, 12(3):319-356, 2008. URL: https://doi.org/10.7155/jgaa.00169.
  18. Gabriele Neyer. Map labeling with application to graph drawing. In Michael Kaufmann and Dorothea Wagner, editors, Drawing Graphs: Methods and Models, pages 247-273. Springer, 2001. URL: https://doi.org/10.1007/3-540-44969-8_10.
  19. Benjamin Niedermann, Martin Nöllenburg, and Ignaz Rutter. Radial contour labeling with straight leaders. In Daniel Weiskopf, Yingcai Wu, and Tim Dwyer, editors, IEEE Pacific Visualization Symposium, pages 295-304. IEEE Computer Society, 2017. URL: https://doi.org/10.1109/PACIFICVIS.2017.8031608.
  20. Roderic Page. Visualising geophylogenies in web maps using geojson. PLOS Currents, 7, 2015. URL: https://doi.org/10.1371/currents.tol.8f3c6526c49b136b98ec28e00b570a1e.
  21. Da Pan, Boyang Shi, Shiyu Du, Tianyu Gu, Ruxiao Wang, Yuhui Xing, Zhan Zhang, Jiajia Chen, Neil Cumberlidge, and Hongying Sun. Mitogenome phylogeny reveals Indochina Peninsula origin and spatiotemporal diversification of freshwater crabs (Potamidae: Potamiscinae) in China. Cladistics, 38(1):1-12, 2022. URL: https://doi.org/10.1111/cla.12475.
  22. Donovan H. Parks, Timothy Mankowski, Somayyeh Zangooei, Michael S. Porter, David G. Armanini, Donald J. Baird, Morgan G. I. Langille, and Robert G. Beiko. GenGIS 2: geospatial analysis of traditional and genetic biodiversity, with new gradient algorithms and an extensible plugin framework. PLoS ONE, 8(7):1-10, 2013. URL: https://doi.org/10.1371/journal.pone.0069885.
  23. Donovan H. Parks, Michael Porter, Sylvia Churcher, Suwen Wang, Christian Blouin, Jacqueline Whalley, Stephen Brooks, and Robert G. Beiko. GenGIS: A geospatial information system for genomic data. Genome Research, 19(10):1896-1904, 2009. URL: https://doi.org/10.1101/gr.095612.109.
  24. Liam J. Revell. phytools: an r package for phylogenetic comparative biology (and other things). Methods in Ecology and Evolution, 3(2):217-223, 2012. URL: https://doi.org/0.1111/j.2041-210X.2011.00169.x.
  25. Mike Steel. Phylogeny: Discrete and Random Processes in Evolution. Society for Industrial and Applied Mathematics, 2016. URL: https://doi.org/10.1137/1.9781611974485.
  26. Ray Tobler, Adam Rohrlach, Julien Soubrier, Pere Bover, Bastien Llamas, Jonathan Tuke, Nigel Bean, Ali Abdullah-Highfold, Shane Agius, Amy O’Donoghue, Isabel O'Loughlin, Peter Sutton, Fran Zilio, Keryn Walshe, Alan N. Williams, Chris S M Turney, Matthew Williams, Stephen M Richards, Robert J Mitchell, Emma Kowal, John R Stephen, Lesley Williams, Wolfgang Haak, and Alan Cooper. Aboriginal mitogenomes reveal 50,000 years of regionalism in australia. Nature, 544(7649):180-184, 2017. URL: https://doi.org/10.1038/nature21416.
  27. Jason T. Weir, Oliver Haddrath, Hugh A. Robertson, Rogan M. Colbourne, and Allan J. Baker. Explosive ice age diversification of kiwi. Proceedings of the National Academy of Sciences, 113(38):E5580-E5587, 2016. URL: https://doi.org/10.1073/pnas.1603795113.
  28. Trevor J. Williams and Jerald B. Johnson. History predicts contemporary community diversity within a biogeographic province of freshwater fish. Journal of Biogeography, 49(5):809-821, 2022. URL: https://doi.org/10.1111/jbi.14316.
  29. Xuhua Xia. Pgt: Visualizing temporal and spatial biogeographic patterns. Global Ecology and Biogeography, 28(8):1195-1199, 2019. URL: https://doi.org/10.1111/geb.12914.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact