SoniaSandbox

Temporary notes for 20.181, Lecture 4

---

Review of Homework #1

Solutions to the Fibonacci question. Solution/notes on the Parsimony question.

Parsimony Continued

• Why parsimony?
  • that will become more clear later when we go over likelihood
  • this algorithm is sometimes called "model-free" because the model is implicit
  • we can suggest infinite alternative explanations involving increasing numbers of mutations but they become less and less plausible

• One not-optimal way to look for the most parsimonious tree: try all four possibilities at every node. But that would require looking at 4^n possibilities! Using recursion in this problem, we can avoid that.

Down-Pass Algorithm

• Formalizing the idea of what you did by intuition in HW1.

def downPass(tree): #pseudocode!

if tree is a leaf:

return seq

l = downPass(left child)

r = downPass(right child)

i= l <intersect> r

if i==None:

return l <union> r

return i

Sankoff Downpass Algorithm

1. Consider different weights for different mutations: P(transitions > P(transversions)
   • The cost of no mutation will be zero.
   • The cost of a transition we'll set to 1.
   • The cost of a transversion will be 2.5 times as much as a transition.
2. On the leaves we want to do something different from the internal nodes, because we are 100% sure of what the sequence is; it's not a guess.
   • Initialize tree; each leaf has a vector of length 4
   • put a score of zero for the letter that we KNOW it is, put a score of infinite for the other three.
3. If we work down from leaves to root

        example tree: ((C,A),(C,(A,G))