Displacement-Optimized Tanglegrams for Trees and Networks

Area of Science:

• Computational Biology
• Bioinformatics
• Mathematical Biology

Background:

• Phylogenetic trees and networks are crucial for understanding biological evolution and relationships.
• Tanglegrams are widely used to visualize and compare phylogenies, but existing methods primarily focus on minimizing edge crossings in trees.
• There is a need for improved tanglegram visualization methods that can handle both trees and networks effectively.

Purpose of the Study:

• To introduce a novel tanglegram layout algorithm, displacement-optimized tanglegrams (DO-tanglegrams), designed for both phylogenetic trees and rooted networks.
• To explicitly minimize taxon displacement and reticulate displacement, enhancing the clarity of evolutionary comparisons.
• To develop a computationally tractable heuristic algorithm for optimizing tanglegram layouts.

Main Methods:

• Formalized one-sided and two-sided optimization problems for tanglegram layouts.
• Developed a heuristic algorithm combining exhaustive local search and simulated annealing to minimize displacement.
• Implemented the DO-tanglegram algorithm in SplitsTree, accommodating multifurcations, multicombinations, and missing taxa.

Main Results:

• DO-tanglegrams significantly outperform the phytools::cophylo function on trees by minimizing taxon displacement.
• DO-tanglegrams demonstrate superior performance compared to the NN-tanglegram algorithm on networks, reducing reticulate displacement.
• The heuristic approach effectively handles complex phylogenetic structures and missing data.

Conclusions:

• DO-tanglegrams provide a significant advancement in visualizing and comparing phylogenetic trees and networks.
• The method offers improved accuracy and clarity for analyses of evolutionary histories, host-parasite associations, and gene transfer.
• DO-tanglegrams represent a valuable new tool for researchers in computational biology and bioinformatics.