untangle_step_rotate_both_side: Stepwise untangle two trees at the same time

Description

This is a greedy forward selection algorithm for rotating the tree and looking for a better match.

This is useful for finding good trees for a tanglegram.

It goes through simultaneously rotating branches of dend1 and dend2 until a locally optimal solution is found.

Step 1: The algorithm begins by executing the 'step2side' operation on the pair of dendograms.

Step 2: The algorithm generates new alternative tanglegrams by simultaneously rotating one branch from tree 1 and one branch from tree 2. This rotation is applied to every possible combination of branches between tree 1 and tree 2, resulting in a set of new alternative tanglegrams. The tanglegram with the lowest entanglement is retained.

Step 3: Steps 1 and 2 are repeated until either a locally optimal solution is found or the maximum number of iterations is reached.

Usage

untangle_step_rotate_both_side(
  dend1,
  dend2,
  L = 1.5,
  max_n_iterations = 10L,
  print_times = dendextend_options("warn"),
  ...
)

Value

A list with two dendrograms (dend1/dend2), after they are rotated to best fit one another.

Arguments

dend1: a dendrogram object. The one we will rotate to best fit dend2.
dend2: a dendrogram object. The one we will rotate to best fit dend1.
L: the distance norm to use for measuring the distance between the two trees. It can be any positive number, often one will want to use 0, 1, 1.5, 2 (see 'details' in entanglement).
max_n_iterations: integer. The maximal number of times to switch between optimizing one tree with another.
print_times: logical (TRUE), should we print how many times we executed steps 1 and 2?
...: not used

References

Nghia Nguyen, Kurdistan Chawshin, Carl Fredrik Berg, Damiano Varagnolo, Shuffle & untangle: novel untangle methods for solving the tanglegram layout problem, Bioinformatics Advances, Volume 2, Issue 1, 2022, vbac014, https://doi.org/10.1093/bioadv/vbac014

Examples

Run this code


if (FALSE) {
# Figures recreated from 'Shuffle & untangle: novel untangle 
# methods for solving the tanglegram layout problem' (Nguyen et al. 2022)
library(tidyverse)
example_labels <- c("Versicolor 90", "Versicolor 54", "Versicolor 81", 
                  "Versicolor 63", "Versicolor 72", "Versicolor 99", "Virginica 135", 
                  "Virginica 117", "Virginica 126", "Virginica 108", "Virginica 144", 
                  "Setosa 27", "Setosa 18", "Setosa 36", "Setosa 45", "Setosa 9")

iris_modified <- 
  iris %>%
    mutate(Row = row_number()) %>%
    mutate(Label = paste(str_to_title(Species), Row)) %>%
    filter(Label %in% example_labels)
iris_numeric <- iris_modified[,1:4]
rownames(iris_numeric) <- iris_modified$Label

# Single Linkage vs. Complete Linkage comparison (Fig. 1)
dend1 <- as.dendrogram(hclust(dist(iris_numeric), method = "single"))
dend2 <- as.dendrogram(hclust(dist(iris_numeric), method = "complete"))
tanglegram(dend1, dend2, 
           color_lines = TRUE,
           lwd = 2,
           margin_inner = 6) # Good.
entanglement(dend1, dend2, L = 2) # 0.207

# The step2side algorithm (Fig. 2)
result <- untangle_step_rotate_2side(dend1, dend2)
tanglegram(result[[1]], result[[2]], 
          color_lines = TRUE,
          lwd = 2,
          margin_inner = 6) # Better...
entanglement(result[[1]], result[[2]], L = 2) # 0.185

# The stepBothSides algorithm (Fig. 4)
result <- untangle_step_rotate_both_side(dend1, dend2)
tanglegram(result[[1]], result[[2]], 
           color_lines = TRUE,
           lwd = 2,
           margin_inner = 6,
           lty = 1) # PERFECT.
entanglement(result[[1]], result[[2]], L = 2) # 0.000
}