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

MOTIVATION: A tanglegram is a plot of two-tree-like diagrams, one facing the other, and having their labels connected by inter-tree edges. These two trees, which could be both phylogenetic trees and dendrograms stemming from hierarchical clusterings, have thus identically labelled leaves but different topologies. As a result, the inter-tree edges of a tanglegram can be intricately tangled and difficult to be analysed and explained by human readers. To better visualize the tanglegram (and thus compare the two dendrograms) one may try to untangle it, i.e. search for that series of flippings of the various branches of the two trees that minimizes the number of crossings among the inter-tree edges. The untanglement problem has received significant interest in the past decade, and several techniques have been proposed to address it. These techniques are computationally efficient but tend to fail at finding the global optimum configuration generating the least tangly tanglegram. RESULTS: We leverage the existing results to propose untanglement methods that are characterized by an overall slower convergence method than the ones in the literature, but that produce tanglegrams with lower entanglements. AVAILABILITY AND IMPLEMENTATION: One of the algorithms is implemented in Python, and available from https://github.com/schlegelp/tanglegram.