.
This exercise, an extension of Exercise 11, provides more details
about the peeling algorithm used to compute probabilities on trees. Consider
the tree with four species and topology given by (((1, 2), 3), 4). Let c denote
the internal node linking species 1 and 2, b denote the node linking c and 3,
and a denote the root node.
a. Write a formula for the probability p of observing particular bases at the
leaves of the tree in the form
{an expression involving the product of 7 terms}
and find this expression.
b. Evaluate the number of addition and multiplication operations needed to
evaluate p.
c. The peeling algorithm is based on the principle of “moving all summation
signs as far to the right as possible.” Write down the corresponding
formula for p and evaluate the number of addition and multiplication
operations needed to calculate it. Comment.
d. Describe in a few sentences how the peeling algorithm works.