Bio E 241 pruning lab

Model

• Kimura model (see BioE241 substitution lab)
• Phylogenetic tree

Goals

• Write code to implement the Felsenstein pruning algorithm to calculate the (log-)likelihood of a multiple sequence alignment under the Kimura 2-parameter model.
  • At this stage, you can represent tree and alignment as internal data structures; the next step involves writing parsers, but that's a bit more involved
  • You should allow for
    1. ambiguous character symbols - see e.g. http://www.chick.manchester.ac.uk/SiteSeer/IUPAC_codes.html
    2. gap characters (treat as missing data)

• Write code, or leverage existing code, to parse the following inputs into data structures, thus extending your program to allow user-specification of alignment & tree
  • Arbitrary Newick format phylogenetic tree
  • Arbitrary Gapped FASTA format multiple sequence alignment

• Write a program that simulates the Kimura model on a given (user-supplied) tree

-- IanHolmes - 05 Feb 2010