Character Methods: Maximum Parsimony

Distance methods collapse each pair of sequences into a single number, discarding the column-by-column signal in the alignment. Character methods such as maximum parsimony keep every aligned site and ask how well a tree explains the observed pattern of states. A tree's parsimony score, or length, is the minimum number of substitutions needed to account for all sites, and the most parsimonious tree is the one that minimizes it.

The Fitch Algorithm

Fitch's algorithm solves this scoring problem for a fixed topology in a single post-order pass from the leaves to the root. Each leaf starts as the singleton set of its observed state; at each internal node you intersect the two child sets, keeping the intersection at no cost when it is nonempty, or taking the union and adding one substitution when it is empty. Summing that count across every site gives the tree length.

def fitch(tree, states):
    # leaf: return its state set with zero cost
    if isinstance(tree, str):
        return states[tree], 0
    left, right = tree
    sl, cl = fitch(left, states)
    sr, cr = fitch(right, states)
    inter = sl & sr
    if inter:                       # intersection non-empty: no change
        return inter, cl + cr
    return sl | sr, cl + cr + 1     # empty: union, one substitution

tree = (("A", "B"), ("C", "D"))
site = {"A": {"A"}, "B": {"G"}, "C": {"A"}, "D": {"G"}}
root_set, length = fitch(tree, site)
print("root set:", sorted(root_set))   # sort for a stable, ordered printout
print("parsimony length:", length)

root set: ['A', 'G']
parsimony length: 2

Searching Tree Space

That same site costs only one step on the topology ((A,C),(B,D)), so the score depends on the tree and you must search for the best one. The number of unrooted binary trees explodes as (2n-5)!!, making exhaustive scoring hopeless past about a dozen taxa, though branch-and-bound stays exact for small sets. Larger problems use heuristic search: build a starting tree by stepwise addition, then rearrange it with nearest-neighbor interchange (NNI), subtree pruning and regrafting (SPR), or tree bisection and reconnection (TBR), keeping any swap that shortens the tree.

# infer_MP_nucleotide.mao holds the MP analysis settings; make it once with the
# MEGA prototyper (megaproto), or reuse the shipped template. PAUP* users would
# instead run: set criterion=parsimony; hsearch swap=tbr addseq=random nreps=100;
megacc -a infer_MP_nucleotide.mao -d alignment.meg -o mp_out

# the search writes a Newick tree you can inspect or hand to a plotter
cat mp_out.nwk

MEGA-CC 11.0.13
Reading data file 'alignment.meg' ... 24 taxa, 1041 sites (312 parsimony-informative)
Analysis: Maximum Parsimony  (search: SPR, level 3; initial trees: 100)
Searching tree space .......... done
Most parsimonious tree length = 487   (CI = 0.690, RI = 0.788)
Trees written to: mp_out.nwk

((Gorilla,(Homo,Pan)),Pongo,(Hylobates,Symphalangus));

Long-Branch Attraction

Long-branch attraction is parsimony's signature failure: when two unrelated lineages pile up many changes on long branches, independent substitutions coincide by chance and parsimony misreads them as shared derived states, pulling the long branches together. Felsenstein showed this makes parsimony statistically inconsistent, so adding more sites can converge confidently on the wrong tree. Because the fix is to correct for unseen multiple substitutions with an explicit substitution model, long-branch attraction is a major reason the field moved on to model-based maximum likelihood and Bayesian methods.