Normalizing
The maximum value of most tree distance metrics scales with the size of the trees being compared. Typically, the resolution of the trees also impacts the range of possible values. As such, it can be difficult to interpret the tree distance value without suitable context.
Normalizing a distance metric is one way to render its meaning more obvious. Selecting an appropriate normalizing constant may require careful consideration of the purpose to which a tree distance metric is being put.
The default normalization behaviour of each function when
normalize = TRUE is listed in the function reference, or can be viewed
by typing ?FunctionName in the R terminal.
Nye et al. tree similarity
Let’s work through a simple example using the Nye et al. (2006) similarity metric to compare two imperfectly-resolved trees.
library("TreeDist")
tree1 <- ape::read.tree(text = '(A, ((B, ((C, D), (E, F))), (G, (H, (I, J, K)))));')
tree2 <- ape::read.tree(text = '(A, (B, (C, D, E, (J, K)), (F, (G, H, I))));')
VisualizeMatching(NyeSimilarity, tree1, tree2,
Plot = TreeDistPlot, matchZeros = FALSE)
This is a nice metric to start with, because the maximum similarity between each pair of splits is defined as one. (Astute readers might worry that the minimum similarity is greater than zero – that’s a harder problem to overcome.)
As such, the maximum similarity possible between two 11-leaf trees is
NSplits(11)
= 8.
Normalizing against this value tells us how similar the two trees are, compared to two identical eleven-leaf binary trees.
## [1] 0.2744048## [1] 0.2744048This approach will result in a similarity score less than one if two
trees are identical, but not fully resolved (i.e. binary).
As such, we might prefer to compare the tree similarity to the maximum
score possible for two trees of the specified resolution. This value is
given by the number of splits in the least resolved of the two
trees:
## [1] 0.5488095More concisely, we can provide a normalizing function:
## [1] 0.2744048This approach will produce a similarity of one if one tree is a less-resolved version of another (and thus not identical).
If we are comparing lists of trees, this best value will depend on
the number of splits in each pair of trees. We can use the function
pmin() to select the less resolved of each pair of
trees:
## [,1] [,2]
## [1,] 0.8750000 0.2744048
## [2,] 0.2744048 0.5000000To avoid these limitations, we may instead opt to normalize against
the average number of splits in the two trees. This is the default
normalization method for NyeSimilarity():
## [1] 0.3991342Finally, if tree1 is a “target” tree – perhaps one that
has been used to simulate data from, or which is independently known to
be true or virtuous – we may wish to normalize against the best possible
match to that tree.
In that case, the best possible score is
## [1] 7and our normalized score will be
## [1] 0.3136054Normalizing to random similarity
The diameter (maximum possible distance) of the Nye et al.
tree similarity metric is easy to calculate, but this is not the case
for all metrics. For example, the clustering information distance metric
(Smith, 2020) ranges in principle from
zero to the total clustering entropy present in a pair of trees. But
with even a modest number of leaves, no pairs of trees exist in which
every split in one tree is perfectly contradicted by every other split
in the other; as such, any pair of trees will necessarily have some
degree of similarity.
In such a context, it can be relevant to normalize tree similarity
against the expected distance between a pair of random trees,
rather than a maximum value (see Vinh, Epps,
& Bailey, 2010). On this measure, distances greater than one
denote trees that are more different than expected by chance, whereas a
distance of zero denotes identity.
With the quartet divergence, the expected tree distance is readily calculated: any given quartet has a one in three chance of matching by chance.
library("Quartet", exclude = "RobinsonFoulds")
expectedQD <- 2 / 3
normalizedQD <- QuartetDivergence(QuartetStatus(tree1, tree2),
similarity = FALSE) / expectedQDThe expected distance is more difficult to calculate for other metrics, but can be approximated by sampling random pairs of trees. Measured distances between 10 000 pairs of random bifurcating trees with up to 200 leaves are available in the data package ‘TreeDistData’. We can view (normalized) distances for a selection of methods:
if (requireNamespace("TreeDistData", quietly = TRUE)) {
library("TreeDistData", exclude = "PairwiseDistances")
data("randomTreeDistances", package = "TreeDistData")
methods <- c("pid", "cid", "nye", "qd")
methodCol <- c(pid = "#e15659", cid = "#58a14e", nye = "#edc949",
qd = "#af7aa1")
oldPar <- par(cex = 0.7, mar = c(5, 5, 0.01, 0.01))
nLeaves <- as.integer(dimnames(randomTreeDistances)[[3]])
plot(nLeaves, type = "n", randomTreeDistances["pid", "mean", ],
ylim = c(0.54, 1),
xlab = "Number of leaves",
ylab = "Normalized distance between random tree pairs")
for (method in methods) {
dat <- randomTreeDistances[method, , ]
lines(nLeaves, dat["50%", ], pch = 1, col = methodCol[method])
polygon(c(nLeaves, rev(nLeaves)), c(dat["25%", ], rev(dat["75%", ])),
border = NA, col = paste0(methodCol[method], "55"))
}
text(202, randomTreeDistances[methods, "50%", "200"] + 0.02,
c("Different phylogenetic information",
"Clustering information distance",
expression(paste(plain("Nye "), italic("et al."))),
"Quartet divergence"
), col = methodCol[methods], pos = 2)
par(oldPar)
}or use these calculated values to normalize our tree distance:
