Shuffle & untangle: novel untangle methods for solving the tanglegram layout problem.

Area of Science:

• Computational Biology
• Data Visualization
• Algorithm Development

Background:

• Tanglegrams visualize relationships between two identically labeled trees (e.g., phylogenetic trees, dendrograms).
• The complexity of tanglegrams arises from differing tree topologies, leading to intricate inter-tree edges.
• Existing tanglegram untanglement methods are fast but often fail to find optimal configurations with minimal crossings.

Purpose of the Study:

• To develop new methods for untangling tanglegrams that improve upon existing techniques.
• To address the limitations of computationally efficient but suboptimal tanglegram untanglement algorithms.
• To enhance the visualization and analysis of comparative tree structures.

Main Methods:

• Leveraging existing results to propose novel untanglement algorithms.
• Developing methods with a slower convergence rate compared to current literature.
• Focusing on achieving lower entanglement (fewer edge crossings) in the resulting tanglegrams.

Main Results:

• The proposed untanglement methods produce tanglegrams with significantly lower entanglement.
• Achieved reduced crossing numbers in tanglegrams compared to existing efficient algorithms.
• Demonstrated the effectiveness of the novel approaches in simplifying complex tree comparisons.

Conclusions:

• The developed methods offer a trade-off between convergence speed and entanglement reduction, favoring accuracy.
• These new algorithms provide a valuable tool for researchers needing to visualize and interpret complex comparative tree data.
• An implementation of one algorithm is available in Python for broader accessibility.