College of Engineering

Tanglegrams are a tool to infer joint evolution of species. Tanglegrams are widely used in ecology to study joint evolution history of parasitic or symbiotically linked species.  Visually, a tanglegram is a pair of evolutionary trees drawn with the leaves facing at each other. One species at the leaf of one trees is related ecologically to a species at a leaf of another tree. Related species from the two trees are connected by an edge. The number of crossings between the edges joining the leaves indicate the relatedness of the trees.        Earlier work on tanglegrams considered the same number of leaves on both the trees and one edge between the leaves of the two trees. In this paper we consider multiple edges from a leaf in the trees. These edges correspond to ecological events like duplication, host switching etc. We generalize the definition of tanglegrams to admit multiple edges between the leaves. We show integer programs for optimizing the number of crossings. The integer program has an XOR formulation very similar to the formulation for the tanglegrams. We also show how the ideas for distance minimization on tanglegrams can be extended for the generalized tanglegrams.  We show that the tanglegram drawings used in ecology can be improved to have fewer crossings using our integer programs.