Maximum parsimony: Fitch’s algorithm on a given tree

The parsimony score of a tree is the smallest number of mutations on its edges that explains the alignment. Fitch’s algorithm (1971) finds it for one column at a time: a bottom-up pass assigns every internal node a set of possible states and counts the mutations, and a top-down pass picks one state per node and puts the mutations on edges. Here the states are 0 and 1, and the tree is fixed: there is no search for the best tree. Click a column of the alignment to jump to it; hover a node, a mutation tick or a column for details. Keys: → step, ← back, n next column, f run all, r reset, m switch mode.

1 Alignment and tree

2 Fitch’s algorithm, for each column

  1. Bottom-up, children before parents. A leaf’s set S is its own state. An internal node with children l and r gets S = S(l) ∩ S(r) if the two sets share a state; otherwise S = S(l) ∪ S(r), and the column’s cost goes up by 1.
  2. Top-down, parents before children. The root takes a state from S(root). A child c of node v keeps v’s state if it is in S(c); otherwise c takes the state in S(c), and edge v–c carries a mutation.
  3. The column’s cost is the number of unions, which equals the number of mutations found. The parsimony score of the tree is the sum of the costs over all columns.

A column is informative when each state occurs in at least two sequences. A constant column costs 0 and a column where only one sequence differs costs 1 on every tree, so only informative columns can favour one tree over another.

3 Tree

{0} {1} {0,1} +1 union: the set cost one mutation ● state chosen top-down mutation in this column, in an earlier column (labelled with the column)

4 Alignment, reconstructed ancestors and costs

Red box: the state differs from the parent’s, i.e. a mutation on the edge above. · = not known yet.