---
title: "Tree distance metrics"
author: "Martin R. Smith"
date: "`r Sys.Date()`"
output: 
  bookdown::pdf_document2:
    includes:
      in_header: ../inst/preamble.tex
  rmarkdown::html_document:
bibliography: ../inst/REFERENCES.bib
csl: https://raw.githubusercontent.com/citation-style-language/styles/master/apa-old-doi-prefix.csl

vignette: >
  %\VignetteIndexEntry{Tree distance metrics}
  %\VignetteEngine{knitr::rmarkdown}
  %\VignetteEncoding{UTF-8}
---

```{r PhangornDistLinker, echo=FALSE}
PhangornDist <- function (linkText) {
  paste0('[`', linkText, '`](https://www.rdocumentation.org/packages/phangorn/topics/treedist])')
}
```

# Tree distance metrics

A number of metrics area available to quantify the similarity between two undirected
topologies (i.e. unrooted trees with no edge lengths), many of which are
implemented in the `phangorn` function `r PhangornDist('treedist')`.

## SPR metric
The subtree pruning and regrafting (SPR) distance [@Penny1985; 
`r PhangornDist('SPR.dist')`] counts the 
number of SPR rearrangements necessary to transform Tree A into Tree B.

## Path difference metric
The length of a path from one tip to another in a tree is the number of edges
within the tree that must be crossed to navigate from one tip to the other.

Given two trees, is possible to calculate the difference in path length between
each pair of tips.

The path difference metric [@Steel1993; `r PhangornDist('path.dist')`] is the 
square root of the sum of squares of each of these differences.

The related nodal distance [@Bluis2003] is not considered further here.

## Partition metric
The Robinson-Foulds (RF or 'partition') metric [@Robinson1981; @Steel1993;
phangorn's `r PhangornDist('RF.dist')` or this package's `RobinsonFoulds`]
measures the symmetric difference between two trees by adding
the number of splits that are present in tree A (but not tree B)
to the number of splits present in tree B (but not tree A).  

It is most useful when the trees to be compared are very similar; it has
a low range of integer values, limiting its ability to distinguish between
trees [@Steel1993].

## Quartet metric
Instead of partitions, symmetric differences can be measured by counting the 
number of four-taxon statements (quartets) that differ between two trees
[@Estabrook1985;@Day1986].

For any four tips A, B, C and D, a split on a bifurcating tree will separate
tip A and either B, C or D from the other two tips.  That is to say, removing
all other tips from the tree will leave one of these three trees:

```{R Three-four-taxon-trees, echo=FALSE, cache=TRUE, fig.width=6, fig.asp=1/3, out.width='66%', fig.align='center'}
par(mfrow=c(1, 3), mar=c(0.5, 1, 0.5, 1), cex=1)
plot(ape::read.tree(text='((A, B), (C, D));'),
     tip.color=Ternary::cbPalette8[c(1, 4, 7, 5)], font=2)
plot(ape::read.tree(text='((A, C), (B, D));'),
     tip.color=Ternary::cbPalette8[c(1, 7, 4, 5)], font=2)
plot(ape::read.tree(text='((A, D), (C, B));'),
     tip.color=Ternary::cbPalette8[c(1, 5, 7, 4)], font=2)
```

Thus two of the random trees below share the quartet `(A, B), (C, D)`, whereas 
the third does not; these four tips are divided into `(A, D), (B, C)`.

```{R Plot-a-quartet, echo=FALSE, cache=TRUE, fig.asp=1.3/3, fig.width=6, out.width='80%', fig.align='center'}
par(mfrow=c(1, 3))
suppressWarnings(RNGversion("3.5.0")) # Stopgap until R 3.6.0 is widely available 
set.seed(7)
trees7 <- lapply(logical(3), function (X) {
    tr <- ape::rtree(7, br=NULL)
    tr$edge.length <- rep(1, 12)
    tr$tip.label <- LETTERS[1:7]
    tr
  })
Quartet::PlotQuartet(trees7, LETTERS[1:4], cex=1.4, font=2)
```

There are $\binom{n}{4}$ groups of four taxa in a tree with $n$ tips;
for each of these groups, one of the three trees above will be consistent with
a given tree.  As such, two identical trees will have a quartet distance of
0, and a random pair of trees will have an expected $\binom{n}{4} / 3$
quartets in common. Because quartets are not independent of one another,
no pair of trees with six or more tips can have all $\binom{n}{4}$ quartets in
common [@Steel1993].

# References
 