Metadata-Version: 2.4
Name: dotanglegram
Version: 1.0.2
Summary: Implementation of the Displacement-Optimized (DO) Tanglegram algorithm for phylogenetic trees
Author: Mathis Lorenzen
License-Expression: GPL-3.0-or-later
Project-URL: Homepage, https://github.com/mathislorenzen/do-tanglegram
Project-URL: Repository, https://github.com/mathislorenzen/do-tanglegram
Keywords: python,tanglegram,dotanglegram,phylogenetics,bioinformatics
Classifier: Programming Language :: Python :: 3
Classifier: Topic :: Scientific/Engineering :: Bio-Informatics
Classifier: Intended Audience :: Science/Research
Requires-Python: >3.10
Description-Content-Type: text/markdown
License-File: LICENSE
Requires-Dist: rpy2
Dynamic: license-file

# 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
```Bash
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.
```Python
from dotanglegram import Tanglegram
```
---
---
Wrap your code in a `main()` function and add an entry point:

```python
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.
```Python
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:
```Python
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:
```Python
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:
```Python
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](https://rpy2.github.io/doc/v3.6.x/html/index.html#).
```Python
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:

```bash
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:

```text
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](https://rpy2.github.io/doc/v3.6.x/html/index.html#).

---

`--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
```Python
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

```bash
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:

```r
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:

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

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