DO-Tanglegram (Python)

This repository contains a Python implementation of the Displacement-Optimized (DO) Tanglegram algorithm for comparing phylogenetic trees.

The implementation was developed by Mathis Lorenzen as part of his Bachelor thesis in Bioinformatics under the supervision of Daniel H. Huson. It is an independent re-implementation of the published algorithm and is not a direct translation of the original Java source code.

The software is based on the algorithm described in:

Huson DH. Displacement-Optimized Tanglegrams for Trees and Networks. Molecular Biology and Evolution. 2026;43(3):msag066. https://doi.org/10.1093/molbev/msag066

While the original publication presents a general framework for displacement-optimized tanglegrams for both trees and phylogenetic networks, this implementation focuses specifically on the tree case. In addition, it extends the original algorithm by supporting many-to-many correspondences between leaves of the two input trees, allowing more general mappings than the one-to-one taxon correspondences considered in the original formulation.

The goal of the project is to provide a clear, accessible, and extensible Python implementation that can serve both as a practical tool for phylogenetic tree comparison and as a basis for further research on tanglegram optimization and visualization.

If you use this software in scientific work, please cite the original publication describing the displacement-optimized tanglegram algorithm.

Installation

pip install dotanglegram

This installs both the library as well as the CLI tool into your environment.

Usage

As a library

First import the Tanglegram class from the dotanglegram library.

from dotanglegram import Tanglegram

---

---

Wrap your code in a main() function and add an entry point:

def main():
    # your code goes here

if __name__ == "__main__":
    main()

This is required because dotanglegram uses Python's multiprocessing module. On platforms that use the spawn start method (such as Windows and macOS), each child process starts a new Python interpreter and imports the main module. Without the if __name__ == "__main__": guard, the module would be re-imported recursively, causing an infinite process creation loop.

---

---

Next create a Tanglegram instance.

tanglegram = Tanglegram(
    tree1_newick,
    tree2_newick,
    mapping=None,
    )

Parameters

---

tree1_newick (str, required):

The first tree in Newick format.

---

tree2_newick (str, required):

The second tree in Newick format.

The extended Newick format is not supported. Any comments in square brackets ([...]) will be removed from the reordered Newick strings. Both trees may contain duplicate taxa and unresolved nodes.

---

mapping (list[tuple[str, str]], optional):

Defines a mapping between taxa in the two trees. Each tuple must have the form:

(tree1-taxon-name, tree2-taxon-name)

Every taxon in the first tree with the specified name is connected to every taxon with the corresponding name in the second tree.

Every tuple that contains names not present in their respective tree is ignored. If none of the tuples are valid or if no mapping is provided, a mapping is generated automatically by connecting taxa with identical names.

---

---

You can now untangle the two trees:

tanglegram.untangle(
    use_nn=True,
    runs=32,
    processes=5,
    fix_tree=None,
    objective="displacement"
    )

Parameters

---

use_nn (bool, optional, default=True):

Whether to presort the trees using a nearest-neighbor circular ordering before performing the exhaustive optimization.

---

runs (int, optional, default=32):

The number of optimization runs to perform.

Each run starts from a different randomized ordering of the two trees. After all runs have completed, the ordering with the lowest number of crossings is returned.

The default value of 32 is usually sufficient to find a near-optimal ordering. Increasing this value may improve the result at the cost of longer computation times.

---

processes (int, optional, default=os.cpu_count()):

The number of worker processes used to perform the optimization runs.

The actual number of processes is the minimum of the specified value, the number of runs, and the number of available CPU cores.

If processes is set to 0 or a negative value, the specified value is ignored, and the number of processes is automatically set to the minimum of the number of runs and the number of available CPU cores.

---

fix_tree (int, optional, default=None):

Can be used to fix tree 1 or tree 2 and only reorder the other tree.

If only one tree is reordered, the nn presort step is skipped.

---

objective (str, optional, default="displacement"):

Can be used to change how the best result is chosen. Either "displacement" or "crossings"

If "displacement" is chosen, the optimal layout is determined by the smallest displacement. If "crossings" is chosen, the optimal layout is determined by the smallest number of crossings.

Each individual change in the ordering is evaluated based on the taxon displacement inside each run. This decision is made among the results of all runs.

---

---

Once the optimization is finished, retrieve the result:

result = tanglegram.get_result()

This returns a TanglegramResult object with the following fields:

• tree1_newick (str) - the reordered first tree in Newick format
• tree2_newick (str) - the reordered second tree in Newick format
• mapping (list[tuple[str, str]]) - the mapping between taxa used for the optimization
• displacement (int) - the total taxon displacement of the final ordering
• crossings (int) - the number of crossings of the final ordering

These fields can be accessed directly as object attributes:

t1 = result.tree1_newick
...
cx = result.crossings

---

---

You can also generate an SVG visualization of the tanglegram.

Before using this feature, make sure you have R 4.5 or later installed, along with phytools 2.5-2 or later.

If you encounter issues related to R in combination with rpy2, please refer to the official rpy2 documentation.

tanglegram.plot(
    output_path="plot.svg",
    width=7,
    height=7,
)

Parameters

---

output_path (str, required):

The path to the output SVG file.

---

width (int, optional, default=7):

The width of the generated SVG in inches.

---

height (int, optional, default=7):

The height of the generated SVG in inches.

As a CLI tool

The package also installs the dotanglegram command-line tool.

The simplest usage is:

dotanglegram tree1.nwk tree2.nwk -v tanglegram.svg

This reads the two trees, untangles them, and plots the tanglegram to the SVG file.

Arguments

---

tree1 (str, required):

Path to the first tree in Newick format.

---

tree2 (str, required):

Path to the second tree in Newick format.

---

-m, --mapping (str, optional):

Path to a mapping file. The file should contain one mapping per line in the format:

tree1_taxon tree2_taxon

---

-n, --nn (bool, optional, default=True):

Whether to presort the trees using a nearest-neighbor circular ordering.

---

-r, --runs (int, optional, default=32):

The number of optimization runs to perform.

---

-p, --processes (int, optional, default=os.cpu_count()):

The number of worker processes used to perform the optimization runs.

---

-f, --fix (int, optional, default=None):

Keep the given tree fixed and only reorder the other one.

---

--objective (str, optional, default="displacement"):

Objective to optimize. This is only used to determine the optimal result among all runs, the optimization itself always uses displacement as objective function.

---

-o, --output (str, optional):

Write the result as a JSON file.

The generated JSON contains the following fields:

• tree1_newick (str) - the reordered first tree in Newick format
• tree2_newick (str) - the reordered second tree in Newick format
• mapping (list[list[str]]) - the mapping used during the optimization
• displacement (int) - the total taxon displacement of the final ordering
• crossings (int) - the number of crossings in the final ordering

---

-v, --visualize (str, optional):

Generate an SVG visualization of the final tanglegram. The argument specifies the output path of the SVG file.

Before using this feature, make sure you have R 4.5 or later installed, along with ape 5.7 or later and phytools 2.5-2 or later.

If you encounter issues related to R in combination with rpy2, please refer to the official rpy2 documentation.

---

--height (int, optional, default=7):

The height in inches of the generated SVG.

---

--width (int, optional, default=7):

The width in inches of the generated SVG.

Examples

As a library

from dotanglegram import Tanglegram

def main():
    tree1_newick = "(A,B,(C,D));"
    tree2_newick = "((B,A),(C,D));"
    mapping = [("A", "D"),
               ("A", "C"),
               ("B", "B"),
               ("C", "A"),
               ("D", "A")
               ]

    tanglegram = Tanglegram(tree1_newick, tree2_newick, mapping)
    tanglegram.untangle()
    tanglegram.plot("tanglegram.svg")

    result = tanglegram.get_result()

    print(f"TD={result.displacement}, CX={result.crossings}")

if __name__ == "__main__":
    main()

As a CLI tool

dotanglegram \
    tree1.nwk \
    tree2.nwk \
    --mapping mapping.txt \
    --runs 50 \
    --processes 8 \
    --output result.json \
    --visualize tanglegram.svg \
    --height 10 \
    --width 10

Use inside of R

You can also use dotanglegram from R via the reticulate package. The following example is equivalent to the Python example:

library(reticulate)

dotanglegram <- import("dotanglegram")

tree1 <- "(A,B,(C,D));"
tree2 <- "((B,A),(C,D));"

mapping <- list(
  c("A", "D"),
  c("A", "C"),
  c("B", "B"),
  c("C", "A"),
  c("D", "A")
)

tanglegram <- dotanglegram$Tanglegram(tree1, tree2, mapping)
tanglegram$untangle()
tanglegram$plot("tanglegram.svg")

result <- tanglegram$get_result()

cat(sprintf("TD=%s, CX=%s\n", result$displacement, result$crossings))

If you use the plot() function, make sure you have phytools 2.5-2 or later installed.

When passing integer arguments (for example, runs, processes, width, or height), wrap them in as.integer() to ensure they are passed to Python as integers:

tanglegram$untangle(
  runs = as.integer(30),
  processes = as.integer(8)
)

tanglegram$plot(
  "tanglegram.svg",
  width = as.integer(10),
  height = as.integer(8)
)