CPSC536a - Assignment 3 (covers Module 3)

handed out Thu, 01/02/16; due Tue, 01/02/27

1 Branch and Bound [10 marks]

The purpose of this problem is to help you understand the branch and bound approach to solving the large parsimony problem.

Following is an example of tree that can be explored by the branch and bound algorithm for finding an optimal parsimony tree. In this example, there are five input sequences, labeled A,B,C,D,E. Correspondingly, the leaves of the branch and bound tree (i.e. the nodes C1.1, C1.2, ..., C3.5) are labeled by possible phylogeny trees with five leaves. The root of the branch and bound tree (also, unfortunately, called A) is labeled by a phylogeny tree with three sequences. The internal nodes of the branch and bound tree, other than the root, (i.e. the nodes B1, B2, and B3) are labeled by phylogeny trees with four sequences.

Part (a): Suppose that the input sequences A,B,C,D, and E are each DNA sequences of length 1, with the following values: Sequence A and C correspond to the nucleotide "T" and sequences B,D, and E correspond to nucleotide "G". Score each of the trees A, B1, B2, B3, C1.1, ..., C1.5, C.2.2, and C.3.3 according to the (Fitch, unweighted) parsimony criterion.

Part (b): One "depth-first" ordering of the nodes of the branch and bound tree is: A, B1, C1.1 C1.2, C1.3, C1.4, C1.5, B2, C2.1, and so on, up to C3.5. Suppose that the branch and bound algorithm explores the nodes of the branch and bound tree in this order, keeping track of all of the best trees found at any point in the exploration, and avoids exploration of nodes at level C of the tree if their parent at level B of the tree already has a score that is higher than the score of the best tree(s) already found. In this case, list which nodes of the branch-and-bound tree are explored by the branch and bound algorithm. Which trees are optimal?

Maximum Likelihood [10 marks]

Calculate the likelihood of the following two (rooted) trees, assuming the Jukes-Cantor model with parameter m = 1/2, and equal distribution of bases at the root. What do you notice?