Displacement-Optimized Tanglegrams for Trees and Networks

Abstract

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 inter-taxon 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 cophylo R-package 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 than NN-tanglegram on networks. Graphical abstract O_FIG O_LINKSMALLFIG WIDTH=200 HEIGHT=127 SRC="FIGDIR/small/690634v1_ufig1.gif" ALT="Figure 1"> View larger version (35K): org.highwire.dtl.DTLVardef@13c9d71org.highwire.dtl.DTLVardef@849fcborg.highwire.dtl.DTLVardef@116ea8borg.highwire.dtl.DTLVardef@1805470_HPS_FORMAT_FIGEXP M_FIG C_FIG