Maximum ParsimonyBret LargetDepartments of Botany and of StatisticsUniversity of Wisconsin—MadisonSeptember 13, 2011Parsimony 1 / 6Maximum ParsimonyDefinitionThe maximum parsimony tree is the tree that best fits the data in thesense that it can explain the data by requiring the fewest number ofchanges among all trees. For a given data set, there may be multiplemaximum parsimony trees.Parsimony 2 / 6Example Data10 20+ +alligator GTG AAC TTC CAC --- CGT TGA CTC...emu GTG ACA TTC ATT ACT CGA TGA TTT...kiwi GTG ACC TTT ACT ACT CGA TGA CTC...vulture ATG ACA TTC ATC AAT CGA TGA CTA...penguin GTG ACC TTC ATT AAC CGA TGA CTA...Parsimony 3 / 6ExampleE K V P AE V P K AParsimony 4 / 6Fitch Algorithm1Set the score to be 0.2Select the next site.1Each leaf is given the set corresponding to its base (or possible basesfor gaps and ambiguous characters).2For each ancestral node whose children have both been processed, letX represent the intersection of the children sets.3If X is non-empty, the set for the node is X . Otherwise, the set for thenode is the union of the children sets and one is added to the score.4Continue to the root.3Continue until all sites are processed.Parsimony 5 / 6Simulation DescriptionSimulate DNA evolution on two different trees.One tree has all short edges.One tree has some short edges and two long edges at opposite endsof the tree.Pick a base for data at some node (1=A, 2=C, 3=G, 4=T, 5 or 6 =try again).For every edge, roll a die to see if there is a change:Ishort edges: change when a 1 is rolledIlong edges: change when a 1, 2, or 3 is rolledWhen there is a change, pick a different base at random (1 or 2 =first, 3 or 4 = second, 5 or 6 = third).Parsimony 6 /