Fitch's Algorithm

Tree and Leaf States

Small parsimony scores observed states on a fixed tree.

highlighted = computed this step

The data are states at the leaves

The running tree has 4 observed leaves at one site. Parsimony asks for the fewest mutations that explain those leaf states on this given tree.

leaves=4\text{leaves}=4
Observed leaf statesLeaf states are read from the fixed tree.Leaf nodeObserved state0A1C3A4G

The topology is fixed before scoring

Fitch's algorithm scores this topology; it does not discover the true tree. The post-order traversal gives 7 node ids.

nodes=7\text{nodes}=7
Post-order node structureChildren columns make the fixed topology readable.NodeKindChildrenState0leaf·A1leaf·C2internal0, 1·3leaf·A4leaf·G5internal3, 4·6internal2, 5·