1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
|
% Generated by roxygen2: do not edit by hand
% Please edit documentation in R/untangle.R
\name{untangle_step_rotate_both_side}
\alias{untangle_step_rotate_both_side}
\title{Stepwise untangle two trees at the same time}
\usage{
untangle_step_rotate_both_side(
dend1,
dend2,
L = 1.5,
max_n_iterations = 10L,
print_times = dendextend_options("warn"),
...
)
}
\arguments{
\item{dend1}{a dendrogram object. The one we will rotate to best fit
dend2.}
\item{dend2}{a dendrogram object. The one we will rotate to best fit
dend1.}
\item{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 \link{entanglement}).}
\item{max_n_iterations}{integer. The maximal number of times to switch between optimizing one tree with another.}
\item{print_times}{logical (TRUE), should we print how many times we executed steps 1 and 2?}
\item{...}{not used}
}
\value{
A list with two dendrograms (dend1/dend2),
after they are rotated to best fit one another.
}
\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 \link{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.
}
\examples{
\dontrun{
# 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
}
}
\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
}
\seealso{
\link{tanglegram}, \link{match_order_by_labels},
\link{entanglement}, \link{flip_leaves}, \link{all_couple_rotations_at_k}.
\link{untangle_step_rotate_1side}, \link{untangle_step_rotate_2side}.
}
|
