Building phylogenetic trees

Concept

Building phylogenetic trees

T-108Home BU-401Threads information · systems

Statement

Distance and likelihood methods.

Why it matters

sequence-alignment already established how to detect homology between sequences and score their similarity position by position; this result addresses the next problem — converting a whole collection of pairwise similarity or distance scores among many aligned, homologous sequences into a single branching hypothesis of evolutionary relationships. blast-database-search finds candidate homologs rapidly across huge databases and hidden-markov-models locate genes and motifs probabilistically, but neither, by itself, produces a tree; tree construction is the distinct combinatorial and statistical problem this result solves, and it underlies comparative genomics, taxonomy, and tracing the origin and spread of pathogens.

expression-clustering, also in this unit, solves a structurally similar problem — grouping objects by similarity — using closely related clustering algorithms, though applied to expression profiles rather than sequence divergence.

Hypotheses

The sequences being compared are genuinely homologous and have been correctly aligned (sequence-alignment).Tree-building methods only produce a meaningful topology when applied to correctly aligned, homologous positions; misaligned or non-homologous input sequences yield a tree with no evolutionary interpretation, however internally consistent the algorithm's output looks. A stated substitution model reasonably approximates the true mutation process converting observed sequence divergence into an estimate of evolutionary distance.Raw percent-difference between two sequences undercounts true divergence at highly diverged sites, since multiple substitutions can occur at the same position without leaving distinct evidence (saturation); a corrected distance model is used instead of raw percent difference for exactly this reason. UPGMA specifically assumes a constant substitution rate across all lineages (a strict molecular clock); neighbour-joining and maximum-likelihood methods relax this and allow different lineages to evolve at different rates.

Proof

\text{Compute a pairwise distance matrix } D_{ij} \text{ from the aligned, corrected sequence divergence between every pair of taxa}

Distance-based methods begin by reducing each pair of aligned sequences to a single number estimating evolutionary distance since divergence, discarding position-by-position detail in exchange for tractable matrix algebra. A

\text{UPGMA: repeatedly join the closest pair of taxa/clusters, averaging distances to the merged cluster}

UPGMA builds a rooted tree by iteratively merging the two nearest items and treating the new cluster's distance to every other item as an average of its members' distances, producing an ultrametric tree (all tips equidistant from the root); this is only valid if the constant-rate assumption (Hypotheses) genuinely holds across all included lineages. A

\text{Neighbour-joining minimises total tree branch length across all pairwise distances, without assuming a molecular clock}

Rather than simply pairing the nearest two items at each step, neighbour-joining corrects for unequal rates among lineages by choosing merges that minimise the overall tree's total branch length, producing an unrooted tree that must subsequently be rooted separately, typically using an outgroup known to lie outside the group of interest. B

\text{Maximum likelihood: for each candidate tree topology and branch-length set, compute } \Pr(\text{data}\mid\text{tree, model}); \text{ search for the maximising topology}

Likelihood methods treat the aligned sequence data as the observed outcome of an explicit stochastic substitution process running along the tree's branches, evaluating how probable the data would be under each candidate tree; this uses the full column-by-column sequence information that distance methods discard at Step 1, at substantially greater computational cost. B

\text{Bootstrap: resample alignment columns with replacement, rebuild the tree many times, and record the fraction of replicates supporting each observed clade}

Bootstrapping supplies a statistical confidence value for each branch of the final tree, addressing the fact that any single tree, built from one particular dataset, could in principle reflect chance groupings rather than genuine evolutionary signal. A

Result

D_{ij}\ \xrightarrow{\text{UPGMA / neighbour-joining}}\ \text{tree}, \qquad \text{alignment}\ \xrightarrow{\text{maximum likelihood}}\ \text{tree maximising } \Pr(\text{data}\mid\text{tree})

Reading. Two broad families of method turn aligned sequence data into a tree: distance methods (fast, reducing the data to a matrix before building, e.g. UPGMA and neighbour-joining), and character-based likelihood methods (slower, using the full sequence data directly, generally more accurate for deep or rate-heterogeneous divergences).

Scope. Distance methods scale to very large datasets and give a fast, approximate topology; likelihood (and Bayesian) methods are the modern standard for publication-quality trees, particularly where lineages evolve at markedly unequal rates (Fails without).

Corollaries & converses

expression-clustering's agglomerative clustering of gene-expression profiles is structurally the same algorithm as UPGMA (Step 2), applied to a different kind of distance matrix, since both solve the same core problem of grouping objects by pairwise similarity.
Trees built by different methods on the same alignment typically agree on well-supported clades but can disagree on deep or weakly supported branches; bootstrap values (Step 5) are the standard tool for identifying which parts of a given tree to trust.
Converse: a clade recovered with high bootstrap support by multiple independent methods (distance-based and likelihood-based alike) is strong evidence that the grouping reflects genuine shared ancestry rather than a method-specific artefact.

Fails without

Drop the homology/correct-alignment assumption (Hypotheses): building a tree from misaligned or non-homologous sequences produces a topology with no evolutionary meaning at all — any distances or likelihoods computed afterward are computed over meaningless position-by-position correspondences, regardless of how sophisticated the tree-building algorithm itself is.
Drop the molecular-clock assumption specifically for UPGMA: if lineages genuinely evolve at different rates — common, for instance, between a fast-evolving parasite lineage and its slower-evolving host — UPGMA can recover a demonstrably incorrect topology, since it forces an ultrametric tree regardless of actual rate variation; neighbour-joining or maximum likelihood, which do not assume a clock, are used instead in exactly this situation.

Common errors

Assuming greater sequence similarity always implies closer evolutionary relationship, ignoring the possibility of long-branch attraction, where two fast-evolving, actually-distantly-related lineages are spuriously grouped together because both independently accumulated many changes, some coincidentally identical.
Treating raw percent sequence difference as true evolutionary distance without a substitution-model correction, which systematically underestimates distance between highly diverged sequences (Hypotheses).
Interpreting a low bootstrap value as proof a clade is wrong, rather than as a signal of insufficient statistical support given the current data; it often simply reflects too few informative sites, not necessarily an incorrect grouping.
Reading branch lengths on an unrooted, non-clock (e.g. neighbour-joining or maximum-likelihood) tree as if they directly represented elapsed time, when they in fact represent estimated amount of sequence change.

Discussion

UPGMA was originally developed by Sokal and Michener in 1958 for phenetic taxonomy, before molecular sequence data existed; neighbour-joining, introduced by Saitou and Nei in 1987, was developed specifically to address UPGMA's dependence on a strict molecular clock. Maximum-likelihood phylogenetics was developed largely by Joseph Felsenstein through the 1980s, and Bayesian phylogenetic methods using Markov-chain Monte Carlo became computationally practical through the 1990s and 2000s as computing power grew.

Long-branch attraction, a well-known failure mode particularly for parsimony and, to a lesser degree, distance methods, is one of the main motivations for the shift toward explicit likelihood-based models: because likelihood methods model the substitution process directly, they can, in principle, account for the possibility of multiple, unobserved substitutions at a single site far better than a simple distance or parsimony count can.

Common misconception: that a phylogenetic tree, once built, is uniquely and permanently "the" true tree. Different methods, models, or genes can yield different topologies, and a single-gene tree need not even match the true species tree, owing to complications such as incomplete lineage sorting — a reminder that any given tree is a hypothesis supported to a stated confidence level (Step 5), not a settled fact.

Worked examples

\text{UPGMA on } D(A,B)=2,\ D(A,C)=4,\ D(B,C)=4

The smallest pairwise distance is \(D(A,B)=2\), so \(A\) and \(B\) are joined first, at a merge height of \(2/2=1\) (half the distance, since UPGMA assumes equal divergence from the ancestor on both branches); the new \(AB\) cluster's distance to \(C\) is then the average of \(D(A,C)\) and \(D(B,C)\), here \((4+4)/2=4\). A

\text{Number of unrooted binary tree topologies for } n \text{ taxa} = (2n-5)!!

For \(n=4\): \((2\times4-5)!!=3!!=3\). For \(n=10\): \((2\times10-5)!!=15!!=15\times13\times11\times9\times7\times5\times3\times1\approx2{,}027{,}025\). The count grows combinatorially, which is exactly why exhaustive search over all possible topologies is only feasible for very small numbers of taxa, and heuristic search (used by both neighbour-joining and maximum-likelihood implementations) is required beyond that. A

n=4:\ 3\text{ topologies}; \qquad n=10:\ \approx2{,}027{,}025\text{ topologies}

Reading. Even a modest increase in the number of taxa produces an astronomically larger space of candidate tree topologies, which is why practical tree-building software relies on heuristic search strategies rather than exhaustive enumeration for any realistically sized dataset.

Scope. The same combinatorial growth applies regardless of which method (distance or likelihood) is ultimately used to score and select a topology.

Problems

Given \(D(A,B)=2\), \(D(A,C)=8\), \(D(B,C)=8\), use UPGMA to determine which two taxa merge first and at what height.
Solution
The smallest distance is \(D(A,B)=2\), so \(A\) and \(B\) merge first, at height \(2/2=1\) (Step 1's logic).
Explain why neighbour-joining is generally preferred over UPGMA when lineages are suspected to evolve at markedly different rates, referencing Fails without.
Solution
UPGMA forces an ultrametric tree, implicitly assuming all lineages have accumulated the same amount of change since their common ancestor (a strict molecular clock); when rates genuinely differ between lineages, this assumption is violated and UPGMA can recover an incorrect topology. Neighbour-joining minimises total tree length without assuming equal rates (Step 3), so it correctly accommodates lineages evolving at different speeds.
For \(n=6\) taxa, compute the number of distinct unrooted binary tree topologies using \((2n-5)!!\), and comment on the practicality of exhaustive search at this scale.
Solution
\((2\times6-5)!!=7!!=7\times5\times3\times1=105\). This is still small enough for exhaustive search to be practical, but the rapid combinatorial growth demonstrated in Worked Example 2 (over two million topologies already at \(n=10\)) means exhaustive search quickly becomes infeasible as datasets grow, which is why most real maximum-likelihood analyses rely on heuristic topology search instead.