Requirements

Before diving into this slide deck, we recommend you to have a look at:

• Introduction to Galaxy Analyses

Why build trees?

The main reason we end up building a tree is that searching tree space for an optimal one takes too long when the number of taxa gets large.

Tree space is worse than "space" space

NGC 2207 and IC 2163 galaxies colliding.
Source: https://commons.wikimedia.org/wiki/Commons:Featured_pictures/Astronomy

Why should building work then?

Some parts of a phylogeny can be confidently accepted: when there are two species much more similar to each other than they are to any other species, we can confidently say that they are likely to be each other's closest relatives, in the set of species of interest.

If molecular sequences evolve at a nice steady rate - the "molecular clock" hypothesis - and if there's neither too little nor too much change, this can be good enough.

Distances from trees

Before we talk about building a tree from distances, we need to think about how distances are reflected by trees.

The most natural way to infer distances from trees is by adding the lengths of branches between each pair of nodes.

Such distances are called patristic distances (I don't know why).

Patristic Distances

Rooted binary tree with branch lengths

Patristic Distances

Patristic distance between tips f and g is 0.02 + 0.025 = 0.045

Patristic Distances

Patristic distance between tips g and h is 0.025 + 0.01 + 0.035 = 0.07

Patristic Distances

Patristic distance between tips e and f is 0.02 + 0.015 + 0.02 + 0.01 + 0.02 = 0.085

Tree-like distances are easy

A set of distances between the tips (taxa) that match the patristic distances of some tree is called tree-like.

Given tree-like distances, most tree construction methods will work.

Yes, most - not all!

Clock-like

The easiest possible distance data to work with are those where the distance from the root to every tip is the same.

Such trees (and the distances derived from them) are called ultrametric (that is, they have the same root-to-tip distance for every tip).

Clock-like

For example, suppose this is the true tree relating some species of interest, with actual branch lengths as labelled:

These distances are ultrametric

These distances are ultrametric

These distances are ultrametric

These distances are ultrametric

The general approach

Our distances

• We get distances from molecular sequences once they have been aligned.
• There are various ways to compare aligned sequences to obtain distances:
  • uncorrected "p-distance" -- the proportion of sites that differ between the two sequences;
  • the Jukes-Cantor (JC69) correction, which takes into account of multiple character state changes through time;
  • The Hasegawa-Kishino-Yano (HKY85) model, which also allows for variation in nucleotide frequencies $\pi_{A}, \pi_{C}, \pi_{G}, \pi_{T}$ as well as different transition/transversion rates;
  • and more.

Jukes-Cantor / JC69

This model has one single parameter, assuming that the base frequencies are each 25%: $\pi_{A}=\pi_{G}=\pi_{C}=\pi_{T}=0.25$

The rate matrix looks like this:

where the asterisk is a short-hand to make the row-sums equal 0.

Under this model the expected number of substitutions between two sequences with a p-distance of $p$ is $$\hat{d} = \frac{-3}{4}\ln\left(1-\frac{4}{3}p\right)$$

Hasegawa-Kishino-Yano / HKY85

This model allows for variation in nucleotide frequencies $\pi_{A}, \pi_{G}, \pi_{C}, \pi_{T}$ as well as different transition/transversion rates using parameter $\kappa$:



This model also allows for a correction to turn relative observed numbers of substitutions between the different bases into expected total number of substitutions between two sequences, but it is much more complex.

From alignment to distances

Example

Ultrametric distances

The true tree

Original Distance Matrix

Original Distance Matrix

The distance between f and g D(f,g) is the sum of the branch lengths on the path between them.

Similarly the distances D(f,h) and D(g,h) are the sum of branch lengths.

Therefore:
$$\mathbf{D(c,h)} = \frac{D(f,h)+D(g,h)-D(f,g)}{2}$$

Forming the next Distance Matrix

We need to remove columns and rows f and g, and add new column and row c.

Forming the next Distance Matrix

The entries for D(f,d), D(g,d) etc get dropped.

Forming the next Distance Matrix

We fill in the new entries using the formulae below:

$$D(c,d) = \frac{1}{2}(D(f,d)+D(g,d)-D(f,g)) = \frac{1}{2}(0.1+0.1-0.04) = \mathbf{0.08}$$

Forming the next Distance Matrix

We fill in the new entries using the formulae below:

$$D(c,e) = \frac{1}{2}(D(f,e)+D(g,e)-D(f,g)) = \frac{1}{2}(0.1+0.1-0.04) = \mathbf{0.08}$$

Forming the next Distance Matrix

We fill in the new entries using the formulae below:

$$D(c,h) = \frac{1}{2}(D(f,h)+D(g,h)-D(f,g)) = \frac{1}{2}(0.06+0.06-0.04) = \mathbf{0.04}$$

Forming the next Distance Matrix

Forming the next Distance Matrix

Completed new distance matrix:

Now we have reduced the problem by one taxon / sequence: we repeat until we have just two more taxa to join and that will give us the root!

Non-clocklike trees

Losing the ultrametric property

Not perfectly clock-like

Now suppose this is the true tree relating some species of interest, with actual branch lengths as labelled:

Neighbo[u]r-Joining

Neighbo[u]r-Joining solves this problem by accounting for the net divergence of node from the rest, so if distances are tree-like, even if they're not ultrametric, it will get the tree right.

The formula for net divergence, with n taxa (i.e., an n x n distance matrix) is

$$r_{i} = \frac{1}{n-2}\sum_{j\neq i}D(i,j)$$

And the adjusted distance becomes

$$D^{\ast}(i,j) = D(i,j) - r(i) - r(j)$$

Adjusted distance matrix

Net divergences:

Adjusted Distances:

Realistic data

Losing tree-like distances

• Real data are not tree-like in general.
• We should adjust the final branch lengths that are found.
• One criterion is Minimum Evolution; this minimises the sum of squared differences ("ordinary least squares"; OLS) between the patristic distances, say G, from the tree and the original distances D:
  $$OLS = \sum_{i,j}(D(i,j) - G(i,j))^{2}$$
  This assumes that the estimates are independent of each other, which clearly isn't the case as the distances between tips in the tree often share parts of the paths between them.
  
  Further reading: Denis and Gascuel: doi.org/10.1016/S0166-218X(02)00285-8.

Anolis tree with uncorrected p-distances

Anolis tree with JC69 distances

Anolis tree with HKY85 distances

Limitations

• A tree-building method will always give you a tree, even if the data didn't come from one.
• There is no information on "next best" trees.
• There is no measure of "goodness" for the most part (though you could always quote the least squares error).
• Lastly, there is by default no going back on bad decisions: because NJ is a greedy heuristic, once the tree is finished, we stop. Luckily, we have programs like FastTree to do some adjustment!

Thank you!

Next - estimating trees from alignments

Thank You!

This material is the result of a collaborative work. Thanks to the Galaxy Training Network and all the contributors!

Tutorial Content is licensed under Creative Commons Attribution 4.0 International License.