SoniaT

I'm a second year student in Eric Alm's and Bruce Tidor's Labs.

This term (Fall06) I'm TA-ing the undergrad computational class 20.181.

Check out the new BE directory!

Temporary notes for 20.181, Lecture 4

---

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

• Consider different weights for different mutations: P(transitions > P(transversions)

1. Lets say that the cost of no mutation is zero, so fill in the diagonal with zeros.
2. Lets say we want the cost of a transversion to cost 2.5 times as much as a transversion
3. 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.
4. If we work down from leaves to root

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