Displacement-Optimized Tanglegrams for Trees and Networks
Molecular Biology and Evolution · 2026
DOI: 10.1093/molbev/msag066 ↗Kurz gefasst
Fachartikel in der Zeitschrift Molecular Biology and Evolution, 2026. Verfasst von Daniel H Huson. Beteiligte Einrichtung: Institute for Bioinformatics and Medical Informatics, University of Tübingen, Sand 14, Tübingen 72076, Germany. Hauptthemen laut MEDLINE: Phylogeny, Algorithms, Computational Biology. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 21 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: University of Tübingen.
Abstract (Originalsprache)
Phylogenetic trees and networks play a central role in biology, bioinformatics, and mathematical biology, and producing clear, informative visualizations of them is an important task. Tanglegrams, which display two phylogenies side by side with lines connecting shared taxa, are widely used for comparing evolutionary histories, host–parasite associations, and horizontal gene transfer. Existing layout algorithms have largely focused on trees and on minimizing the number of intertaxon edge crossings. We introduce displacement-optimized tanglegrams (DO-tanglegrams), a new approach that applies equally to trees and rooted phylogenetic networks. Our method explicitly minimizes taxon displacement—the vertical misalignment of corresponding taxa across the two sides—and reticulate displacement—the vertical distance spanned by reticulation edges within a network. We formalize one-sided and two-sided optimization problems, show that exact minimization is computationally intractable, and propose a heuristic that combines exhaustive local search with simulated annealing. The algorithm naturally accommodates unresolved nodes (multifurcations or multicombinations) and missing taxa. We have implemented the DO-tanglegram algorithm in SplitsTree. We compare our implementation against the phytools::cophylo R-function on a collection of synthetic trees, and against the NN-tanglegram algorithm in Dendroscope on a collection of synthetic networks. The results indicate that DO-tanglegram performs significantly better than cophylo on trees and then NN-tanglegram on networks.
Schlagwörter
MeSH-Schlagwörter (MEDLINE)
Stichwörter der Autor:innen
Autor:innen und Institutionen
- Institute for Bioinformatics and Medical Informatics, University of Tübingen, Sand 14, Tübingen 72076, Germany.
ORCID-Profile: Daniel H Huson
Förderung
- University of Tübingen
Zitieren
APA
Huson, D. H. (2026). Displacement-Optimized Tanglegrams for Trees and Networks. Molecular Biology and Evolution. https://doi.org/10.1093/molbev/msag066
Vancouver
Huson DH. Displacement-Optimized Tanglegrams for Trees and Networks. Molecular Biology and Evolution. 2026. doi:10.1093/molbev/msag066
BibTeX
@article{Huson2026,
author = {Huson, Daniel H},
title = {Displacement-Optimized Tanglegrams for Trees and Networks},
journal = {Molecular Biology and Evolution},
year = {2026},
doi = {10.1093/molbev/msag066}
}
EUVIMED