Leaves of a phylogenetic tree represent objects being compared. Objects can be genes, protein, species, etc. Internal nodes are hypothetical ancestral objects. In a rooted tree, the path from root to a node corresponds to a path in evolutionary time. An unrooted tree specifies relationships among objects, but not evolutionary time.

Parsimony is probably the most widely used of all tree building algorithms. It works by finding the tree which can explain the observed sequences with a minimal number of substitutions. Instead of building a tree, it assigns a cost to a given tree, and it is necessary to search through all topologies, or to pursue a more efficient strategy that achieves this effect in order to identify the best tree.

Parsimony takes aligned sequences as input (character data) and outputs a labeled tree which explains the data with a minimal number of changes across edges.

Important Points

• Parsimony does not build trees, it rearranges them
• Parsimony assigns a cost to a given tree
• Parsimony requires a search through all topologies
• Parsimony treats each site of the tree independently

The parsimony algorithm has two important components:

1. compute the cost of a given tree
2. search through all trees to find the tree with the minimal cost

In plain words, we would need to build the tree from the bottom up. At each step, we compute the cost of connect a leaf or node to some site. Site is the node we wish to connect our leaf or node to. We the tree is complete, we calculate the cost of the tree by summing the cost of all connections. We repeat these steps for all possible trees. When we have computed the cost for all trees, we look for the tree which has the minimum cost. This cost is the best solution.

Weighted Parsimony

Weighted parsimony is an extension of traditional parsimony. It uses substitution costs S(a,b) for each substitution of a by b. It reduces to traditional parsimony when S(a,a) = 0 and S(a,b) = 1 ∀ a ≠ b.

Suppose we have the following aligned sequences:

AAG
AAA
GGA
AGA

                    7. A?A

          5. A?A               6. A?A

     1. AAG    2. AGA      3. AAA   4. GGA   

We need to do a post-order traversal to compute the tree. In simple terms, we start from the leaves and work our way up to the node.

When k = {1,2,3,4} which are leaf nodes:

k = 1: S₁(A) = 0, S₁(C) = S₁(G) = S₁(T) = ∞
k = 2: S₁(G) = 0, S₁(C) = S₁(A) = S₁(T) = ∞
k = 3: S₁(A) = 0, S₁(C) = S₁(G) = S₁(T) = ∞
k = 4: S₁(G) = 0, S₁(C) = S₁(A) = S₁(T) = ∞

∞ forces the algorithm to start at the actually observed residue.

k = 5:
S₅(A) = min_b(S₁(b) + S(a,b)) + min_b(S₁(b) + S(a,b))
S₅(A) = S₁(A) + S(a;A) + S₂(G) + S(a;G)
S₅(A) = S(a;A) + S(a;G)

This translates to:

S₅(A) = S(A;A) + S(A;G)
S₅(T) = S(T;A) + S(T;G)
S₅(C) = S(C;A) + S(C;G)
S₅(G) = S(G;A) + S(G;G)

If this were traditional parsimony, we would get:

S₅(A) = 0 + 1 = 1
S₅(T) = 1 + 1 = 2
S₅(C) = 1 + 1 = 2
S₅(G) = 1 + 0 = 1

k = 6: Same as k = 5

k = 7:

S₇(a) = min_b(S₅(b) + S(a,b)) + min_b(S₆(b) + S(a,b))
S₇(a) = 2 min((S₅(A) + S(a;A)); (S₅(T) + S(a; T)); (S₅(C) + S(a;C)); (S₅(G) + S(a;G)); )

If this were traditional parsimony, we would get:

S₇(a) = 2 min((1 + S(a;A)); (2 + S(a; T));(2 + S(a;C)); (1 + S(a;G)))
S₇(A) = 2 min((1 + 0); (2 + 1); (2 + 1); (1 + 1)) = 2
S₇(T) = 2 min((1 + 1); (2 + 0); (2 + 1); (1 + 1)) = 4
S₇(C) = 2 min((1 + 1); (2 + 1); (2 + 0); (1 + 1)) = 4
S₇(G) = 2 min((1 + 1); (2 + 1); (2 + 1); (1 + 0)) = 2

The the minimal cost of tree = min_aS₇(a) = 2

Therefore, the two solutions are:

                  7. AGA
                /        \
          5. AGA          6. AGA
         /     \          /     \
  1. AAG    2. AGA    3. AAA   4. GGA   

                  7. AAA
                /        \
          5. AAA          6. AAA
         /     \          /     \
  1. AAG    2. AGA    3. AAA   4. GGA    

It may sometimes be of interest to keep track of minimizing residues (residue that returned minimal costs) in recursion. By assigning the following pointers to the left and right daughters at the end of each recursion block, we can track the minimizing residues:

l_k(a) = argmin_b(S_i(b) + S(a,b))
r_k(a) = argmin_b(S_j(b) + S(a,b))

To obtain an assignment of ancestral residues, we pick residue a at the root that gives minimal cost, follow pointers, and choose arbitrarily if there are more than one possible targets.

Traditional Parsimony

In traditional parsimony only the number of substitutions is counted. List R_k of minimal cost residues at is kept at each node along with current cost c.

There is a traceback procedure for finding ancestral assignments in traditional parsimony.

1. Choose a residue from the root (R_2n-1) and proceed down the tree.
2. Having chosen a residue in R_k, pick the same residue in R_i and R_j if possible, otherwise at random.

An assignment not obtained by traceback with R_k can be found by keeping a set Q_k of residues at node k where cost is one more than that of the residues in R_k at Q_k is set to one higher than R_k.

So far, we only looked at parsimony for rooted trees. The minimum cost for traditional parsimony is independent of root location. Minimum cost for weighted parsimony is independent of root location if S(a,b) is metric:

S(a,a) = 0
S(a,b) = S(b,a)
S(a,c) ≤ S(a,b) + S(b,c)

When cost is independent of root location, we economize in terms of number of possible topologies.

Branch and Bound

In parsimony, the number of possible topologies increases rapidly as the number of leaves increase. Therefore, a more efficient strategy is required. There are several search strategies which are quite efficient but they do not guarantee to find the best tree. Branch and bound is an algorithm which guarantees to find the best tree. The idea is to systematically enumerate trees while abandoning a search venue when the incomplete tree is more expensive than the complete tree.

The tree can be enumerated like an odometer.

[i₃] lists the possible edges, where a new edge for x⁴ can be added.
[i₅] lists the possible edges, where a new edge for x⁵ can be added.
[i_2n-5] lists the possible edges, where a new edge for xⁿ can be added.

Accessing tree with bootstrap

Once a tree is build using an algorithm of choice, how much to trust it? How can we access its accuracy? Bootstrap is a method which allows us to access the significance of a phylogenetic feature.

1. Dataset is an alignment of sequences
2. Generate artificial dataset by selecting columns with replacement
3. Build tree for artificial dataset
4. Repeat the previous 2 steps about a 1000 times
5. Frequency of appearance of a feature is the measure of confidence in this feature

Source

[1] Durbin
[2] Haari Jaalinoja's slides