IAE Academy

FOR CORE AND IT JOBS · CHAPTER 4 OF 7

Multiple alignment and phylogenetic trees

This chapter explains how many sequences are aligned at once, how an evolutionary tree is written and built from distances, and how trees are judged. An engineer who reads or builds sequence pipelines needs it to know what a tree figure claims.

Updated 30 Oct 2026

What you will be able to do

You will align several sequences at once and say which columns are conserved. You will read and write a tree in Newick format. You will build a tree from a distance table with UPGMA, step by step. You will say what parsimony, likelihood and bootstrap values each claim.

Before you start

  1. Chapter 2, Pairwise sequence alignment

  2. Averages and simple fractions

  3. Factorials, and the double factorial m!! = m(m-2)(m-4)...1 for odd m

  4. Probability: independent events multiply; P(x | y) is the probability of x given y

  5. Logarithms: the log of a product is the sum of the logs

Aligning many sequences at once

A multiple sequence alignment (MSA) stacks three or more sequences so that each column holds residues believed to descend from one ancestral position. Sequences are written 5' to 3', the direction in which a strand is built, DNA in capitals ACGT; a dash is a gap. Selection tends to remove harmful changes, so a column unchanged across distant sequences probably holds a residue the molecule needs. Across close sequences it may be unchanged by chance.

S1  ACGTTGCA
S2  ACGTAGCA
S3  ACCTTGCA
S4  ATGT-GCA

Counting from the left, columns 1, 4, 6, 7 and 8 hold the same residue in every row: five of eight columns are conserved. Columns 2, 3 and 5 vary.

Exact MSA is too costly: the dynamic programming table of Chapter 2 gains one dimension per sequence, so sequences of length need about cells. Progressive alignment instead aligns every pair as in Chapter 2 and takes as their distance the share of gap-free aligned positions that differ, per 100 sites. These distances give a guide tree, a rough tree of the kind described next, with the closest sequences side by side. The closest pair is aligned first, then the other sequences or groups are added in the tree's order, tips to root.

WATCH OUT FOR

Plain progressive alignment never revisits a choice. Test: can a later step move a gap already placed? No, so a poor guide tree or a wrong early pair carries into the final MSA.

Trees and the Newick format

A phylogenetic tree shows how sequences are related. Leaves are the sequences, internal nodes are inferred common ancestors, and branch lengths measure change, here in substitutions per 100 sites. A clade is an ancestor with all the leaves descended from it. A rooted tree has a root, the common ancestor of every leaf, which can be placed with an outgroup: a sequence known to have branched off before the others split. An unrooted tree shows only relationships: each branch splits the leaves into two groups.

The trees here are binary: each internal node of an unrooted tree joins three branches. Three leaves give one tree with 3 branches. Each added leaf splits a branch and adds its own, 2 more, so leaves give branches. Leaf can attach to any of the branches of a tree on leaves, multiplying the count by . A rooted tree on leaves is an unrooted tree on leaves with the extra leaf taken as the root.

NUMBER OF POSSIBLE TREES

For binary trees on n ≥ 3 labelled leaves. The rooted count is the unrooted one with n+1 in place of n; n = 4 gives 3 unrooted and 15 rooted trees.

  1. Newick writes a tree as nested brackets: (A,B) is a clade of two leaves; commas separate siblings.

  2. A colon and a number after a node give the length of its branch to its parent.

  3. A semicolon ends the tree, as in ((A:1,B:1):2,C:3);

  4. An unrooted tree is often written with three groups at the top: (A,B,(C,D)); splits A and B from C and D.

WORKED EXAMPLE

Read the Newick tree ((A:1,B:1):2,C:3); with lengths in substitutions per 100 sites, and find the tree distance from A to B and from A to C.

Solution
  1. The outer brackets hold the two children of the root: the clade (A,B) on a branch of length 2, and C on a branch of length 3.

  2. A and B share the clade's node, so the path from A to B uses only their own branches, 1 and 1.

  3. A to C must leave the clade: up from A (1), up the clade's branch to the root (2), then down to C (3).

  4. The tree distance between two leaves is the sum of the branch lengths on the one path joining them: 1+1 = 2, and 1+2+3 = 6.

Answer: d(A,B) = 2 and d(A,C) = 6 substitutions per 100 sites.

Building a tree from distances

Distance methods build a tree from the table of pairwise distances alone, using the distance defined above. A cluster is a group of sequences already joined; at the start each sequence is its own cluster. UPGMA joins the two closest clusters into one, recomputes the distances to the new cluster and repeats until one cluster is left. It assumes the same rate of change in every lineage, so its tree is rooted with every leaf at the same distance from the root.

UPGMA DISTANCE TO A NEW CLUSTER

Z is any other cluster, and |X| is the number of original sequences in X. The result is the average of all original distances between the two groups.

UPGMA NODE HEIGHT AND BRANCH LENGTH

d(X,Y) is the join distance, h the new node's height above the leaves and h_X the height of X (0 for a single sequence), all in the table's units.

Sequence

A

B

C

B

4

C

8

10

D

12

12

6

WORKED EXAMPLE

Build the UPGMA tree for the distance table above (differences per 100 sites between the row and column sequences). Give the joins as a table and the tree in Newick format.

Solution
  1. UPGMA joins the closest pair, and the smallest entry is d(A,B) = 4. The node sits halfway, at height 4/2 = 2, and leaves have height 0, so each branch is 2.

  2. Average the new cluster's distances, each sequence counting once: d(AB,C) = (8+10)/2 = 9 and d(AB,D) = (12+12)/2 = 12. d(C,D) = 6 does not involve AB, so it stays.

  3. Of 9, 12 and 6 the smallest is d(C,D) = 6, so C and D join at height 3, each branch 3.

  4. With |C| = |D| = 1, d(AB,CD) = (9+12)/2 = 10.5, the average of the four original distances 8, 12, 10 and 12.

  5. The last join is at height 10.5/2 = 5.25. Subtract each cluster's height: AB gets 5.25 - 2 = 3.25 and CD gets 5.25 - 3 = 2.25.

Answer: ((A:2,B:2):3.25,(C:3,D:3):2.25); with the joins in the table below. A and C end up 2+3.25+2.25+3 = 10.5 apart, not the observed 8, because UPGMA puts every leaf at the same distance from the root.

Join

Clusters joined

Join distance

Node height

Branch lengths

1

A and B

4

2

A 2, B 2

2

C and D

6

3

C 3, D 3

3

AB and CD

10.5

5.25

AB 3.25, CD 2.25

Neighbour joining drops the equal-rate assumption. With current clusters it joins the pair with the lowest below: close to each other, far from the rest. They become a new node on branches and , and for each other cluster . At three clusters every pair has the same : join any pair, then link the last two clusters by a branch equal to their distance. The tree is unrooted.

NEIGHBOUR JOINING SCORE AND BRANCH LENGTHS

For n ≥ 3 current clusters. d is the current distance table, and r_i is the sum of d_ik over all current clusters k. Branch lengths are in the table's units.

Judging trees: parsimony, likelihood, bootstrap

Character methods score a tree against the alignment columns directly. Parsimony prefers the tree needing the fewest residue changes, summed over columns. Only informative columns separate trees: one residue in at least two leaves and another in at least two others. Any other column costs the same on every tree. In the informative column below, A and B hold G, and C and D hold T.

Unrooted tree

Changes needed

(A,B,(C,D));

1

(A,C,(B,D));

2

(A,D,(B,C));

2

On (A,B,(C,D)); one change, on the branch between the pairs, explains the column; the other trees need two, one in each pair. Maximum likelihood adds a substitution model: the probability that one residue changes to another along a branch of given length. A column's likelihood sums over the unknown ancestral residues. Columns are treated as independent, so their probabilities multiply, and the tree and lengths with the highest likelihood win.

LIKELIHOOD OF A TREE

Valid when columns evolve independently under the model. S is the number of columns, T the tree, ℓ its branch lengths; P(column s | T, ℓ, model) is the probability of column s given them, so ln L ≤ 0. Summing logs avoids a product of tiny numbers that a computer could round to zero.

Bootstrap support asks how stable a clade is. Resample the columns with replacement to the original length, so some appear twice and others not at all. Build a tree from each resample by the same method, N times, and count the trees that contain the clade.

BOOTSTRAP SUPPORT

k is the number of the N resampled trees that contain the clade, so 0 ≤ k ≤ N, and B is its support in percent. A clade with k = 90 of N = 100 has B = 90.

WATCH OUT FOR

B is not the probability that the clade is true. Test: ask what was resampled. Only the columns were, with one method, so B says how consistently the data support the clade under that method.

Check yourself

CHECK YOURSELF 1

How many distinct binary rooted trees exist for 5 labelled leaves?

  1. (A)

    15

  2. (B)

    24

  3. (C)

    105

  4. (D)

    120

Answer and solution

Answer: (C)

  1. Use the rooted count (2n-3)!! with n = 5.

  2. 2n-3 = 7, so 7!! = 7 x 5 x 3 x 1 = 105. (15 is the unrooted count, 5!!.)

CHECK YOURSELF 2

With d(P,Q) = 6, d(P,R) = 10 and d(Q,R) = 14, in differences per 100 sites, UPGMA joins P and Q first. What is d(PQ,R), in the same units?

Answer and solution

Answer: (accepted range )

  1. P and Q are single sequences, so each has weight 1 in the average.

  2. d(PQ,R) = (10 + 14)/2 = 12.

CHECK YOURSELF 3One or more options are correct

Which statements about plain progressive alignment, with no later refinement, are correct?

  1. (A)

    A guide tree is built from pairwise distances.

  2. (B)

    An early misplaced gap is corrected later.

  3. (C)

    The closest sequences are aligned first.

  4. (D)

    The result is guaranteed to be optimal.

Answer and solution

Answer: (A), (C)

  1. A and C describe the method.

  2. B is false: earlier choices are never revisited.

  3. D is false: errors made early stay, so optimality is not guaranteed.

CHECK YOURSELF 4

A clade has a bootstrap value of 80 from 100 replicates. What does this mean?

  1. (A)

    The clade is true with probability 0.8.

  2. (B)

    The clade appeared in 80 of the 100 trees built from resampled columns.

  3. (C)

    80 percent of the sequences are in the clade.

  4. (D)

    The branch to the clade has length 0.8.

Answer and solution

Answer: (B)

  1. Bootstrap support is k/N x 100, the share of resampled trees containing the clade: 80/100 x 100 = 80.

  2. It does not state the probability that the clade is true.